username53983805
Badges: 9
Rep:
?
#1
Report Thread starter 1 week ago
#1
First I had to prove that n^{5}-n\equiv0 (\mathrm{mod}\ 6), which was fine, however proving n^{5}-n\equiv0 (\mathrm{mod}\ 30) I found not so straightforward. I first tried considering the case when n is even, and then supposed that n-1 \equiv0 (\mathrm{mod}\ 3) and wanted to then prove that (n+1)(n^{2}+1)\equiv0 (\mathrm{mod}\ 5), but this is not true (via counterexample).

Could I have a hint to a better way of approaching this problem?
Last edited by username53983805; 1 week ago
0
reply
ghostwalker
  • Study Helper
Badges: 17
?
#2
Report 1 week ago
#2
(Original post by username53983805)
First I had to prove that n^{5}-n\equiv0 (\mathrm{mod}\ 6), which was fine, however proving n^{5}-n\equiv0 (\mathrm{mod}\ 30) I found not so straightforward. I first tried considering the case when n is even, and then supposed that n-1 \equiv0 (\mathrm{mod}\ 3) and wanted to then prove that (n+1)(n^{2}+1)\equiv0 (\mathrm{mod}\ 5), but this is not true (via counterexample).

Could I have a hint to a better way of approaching this problem?
Since you've proven it for mod 6, if you could prove it for mod 5, then mod 30 follows immediately.
0
reply
username53983805
Badges: 9
Rep:
?
#3
Report Thread starter 1 week ago
#3
(Original post by ghostwalker)
Since you've proven it for mod 6, if you could prove it for mod 5, then mod 30 follows immediately.
Aha, I think I've got it. So n^{5}-n=n(n-1)(n+1)(n^{2}+1), and n^{2}+1=(n-2)(n+2)+5 \implies n^{5}-n=n(n-1)(n+1)(n-2)(n+2)+5n(n-1)(n+1), and as n-2,n-1,n,n+1,n+2 describes a set of 5 consecutive integers, at least one must be a multiple of 5. Therefore n^{5}-n=5k+5m=5(k+m)\equiv0 (\mathrm{mod}\ 5) for k \in \mathbb{Z},\ m \in \mathbb{Z}, and so the fact that n^{5}-n \equiv0 (\mathrm{mod}\ 30) follows immediately!
Last edited by username53983805; 1 week ago
1
reply
ghostwalker
  • Study Helper
Badges: 17
?
#4
Report 1 week ago
#4
(Original post by username53983805)
Aha, I think I've got it. So n^{5}-n=n(n-1)(n+1)(n^{2}+1), and n^{2}+1=(n-2)(n+2)+5 \implies n^{5}-n=n(n-1)(n+1)(n-2)(n+2)+5n(n-1)(n+1), and as n-2,n-1,n,n+1,n+2 describes a set of 5 consecutive integers, at least one must be a multiple of 5. Therefore n^{5}-n=5k+5m=5(k+m)\equiv0 (\mathrm{mod}\ 5) for k \in \mathbb{Z},\ m \in \mathbb{Z}, and so the fact that n^{5}-n \equiv0 (\mathrm{mod}\ 30) follows immediately!
Very nice.

For a more simplistic approach, since you're working mod 5, all you need to do is check one example from each of the equivalance classes mod 5. I.e. 0,1,2,3,4. If it's true for them, then it's true for all n.
Last edited by ghostwalker; 1 week ago
0
reply
mqb2766
Badges: 19
Rep:
?
#5
Report 1 week ago
#5
Another (less elegant, but with a nice insight) way would be via bog standard induction, so prove the difference in successive terms is divisible by 5. Looking at the ()^5 row of pascals triangle
https://en.wikipedia.org/wiki/Pascal%27s_triangle
5 10 10 5, all the terms are divisible by 5 and the start and end 1s are knocked off, so its divisible by 5.

The nice insight is that this happens for all odd powers, so 3 3 is divislbe by 3 and 7, 21, 35, ... is divisible by 7 etc so
n^k - n
is divisble by k for odd k (edited - prime)
Last edited by mqb2766; 1 week ago
1
reply
username53983805
Badges: 9
Rep:
?
#6
Report Thread starter 1 week ago
#6
(Original post by ghostwalker)
Very nice.

For a more simplistic approach, since you're working mod 5, all you need to do is check one example from each of the equivalance classes mod 5. I.e. 0,1,2,3,4. If it's true for them, then it's true for all n.
Thanks

Oh yes, that seems a much more consistent and systematical method for a correct solution.
0
reply
Cs115
Badges: 10
Rep:
?
#7
Report 1 week ago
#7
(Original post by mqb2766)
Another (less elegant, but with a nice insight) way would be via bog standard induction, so prove the difference in successive terms is divisible by 5. Looking at the ()^5 row of pascals triangle
https://en.wikipedia.org/wiki/Pascal%27s_triangle
5 10 10 5, all the terms are divisible by 5 and the start and end 1s are knocked off, so its divisible by 5.

The nice insight is that this happens for all odd powers, so 3 3 is divislbe by 3 and 7, 21, 35, ... is divisible by 7 etc so
n^k - n
is divisble by k for odd k
Ive done this question before and used this exact same method. For divisibility by 2 and 3 you can factories and show if there are 2 consecutive terms then it must be divisible by 2, and if there are 3 consecutive terms it is divisible by 3. Then induct for divisibility by 5. and if it is divisible by 2,3 and 5 then it is divisible by 30 as 2, 3 and 5 are coprime
1
reply
mqb2766
Badges: 19
Rep:
?
#8
Report 1 week ago
#8
(Original post by Cs115)
Ive done this question before and used this exact same method. For divisibility by 2 and 3 you can factories and show if there are 2 consecutive terms then it must be divisible by 2, and if there are 3 consecutive terms it is divisible by 3. Then induct for divisibility by 5. and if it is divisible by 2,3 and 5 then it is divisible by 30 as 2, 3 and 5 are coprime
Good. As shown above, there are several ways to prove it.

The above factorization is elegant though and for x^7 - x say you have
x(x-1)(x+1)(x^2-x+1)(x^2-x+1)
and using the same trick, you have
(x^2-x+1) = (x^2 - x -6 +7) = (x-3)(x+2) +7
(x^2+x+1) = (x^2 + x - 6 + 7) = (x+3)(x-2) +7
So the same reasoning applies. Id guess it generalizes, though not worked it through and I'd expect it gets a bit harder. The x(x-1)(x+1) which occurs in every term will make it 0 (mod 42) as well.

Spotting the (one of many) patterns in pascals triangle (as part of induction) though makes it possible to guess the property. Though its clearly related to the roots of unity etc.
Last edited by mqb2766; 1 week ago
0
reply
DFranklin
Badges: 18
Rep:
?
#9
Report 1 week ago
#9
(Original post by mqb2766)
Another (less elegant, but with a nice insight) way would be via bog standard induction, so prove the difference in successive terms is divisible by 5. Looking at the ()^5 row of pascals triangle
https://en.wikipedia.org/wiki/Pascal%27s_triangle
5 10 10 5, all the terms are divisible by 5 and the start and end 1s are knocked off, so its divisible by 5.

The nice insight is that this happens for all odd powers, so 3 3 is divislbe by 3 and 7, 21, 35, ... is divisible by 7 etc so
n^k - n
is divisble by k for odd k
Something's not right in your last paragraph.

2^9 - 2 = 510 is not divisible by 9
2^15 - 2 = 32766 is not divisible by 15.

(It *is* true for k prime, (even for k = 2)).
0
reply
mqb2766
Badges: 19
Rep:
?
#10
Report 1 week ago
#10
(Original post by DFranklin)
Something's not right in your last paragraph.

2^9 - 2 = 510 is not divisible by 9
2^15 - 2 = 32766 is not divisible by 15.

(It *is* true for k prime, (even for k = 2)).
Yes, the nCr part fails. I'd guess its related to it being prime (or not). Bit too quick with hoping a pattern extends (too much).
And yes, its related to Fermats little theorem.
Last edited by mqb2766; 1 week ago
0
reply
DFranklin
Badges: 18
Rep:
?
#11
Report 1 week ago
#11
(Original post by mqb2766)
Yes, the nCr part fails. I'd guess its related to it being prime (or not). Bit too quick with hoping a pattern extends (too much).
And yes, its related to Fermats little theorem.
One quite nice route is to show (n+1)^p = (n+1) mod p using the binomial theorem. Note in \binom{p}{k} = \frac{p!}{k!(p-k)!}, the only way the denominator is divisible by p is if k = 0 or k = p.
Last edited by DFranklin; 1 week ago
0
reply
mqb2766
Badges: 19
Rep:
?
#12
Report 1 week ago
#12
(Original post by DFranklin)
One quite nice route is to show (n+1)^p = (n+1) mod p using the binomial theorem. Note in \binom{p}{k} = \frac{p!}{k!(p-k)!}, the only way the denominator is divisible by p is if k = 0 or k = p.
I think thats what I alluding to at the start as the k=0/p terms drop out when you consider the difference (induction).
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

Have you made your mind up on your five uni choices?

Yes, and I've sent off my application! (194)
55.11%
I've made my choices but havent sent my application yet (49)
13.92%
I've got a good idea about the choices I want to make (40)
11.36%
I'm researching but still not sure which universities I want to apply to (33)
9.38%
I haven't started researching yet (21)
5.97%
Something else (let us know in the thread!) (15)
4.26%

Watched Threads

View All
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise