# Prove n^5-n≡0 (mod 30)

Watch
Announcements
#1
First I had to prove that , which was fine, however proving I found not so straightforward. I first tried considering the case when n is even, and then supposed that and wanted to then prove that , 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
1 week ago
#2
Since you've proven it for mod 6, if you could prove it for mod 5, then mod 30 follows immediately.
0
#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 , and , and as describes a set of 5 consecutive integers, at least one must be a multiple of 5. Therefore for , and so the fact that follows immediately!
Last edited by username53983805; 1 week ago
1
1 week ago
#4
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
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
#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
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
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
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
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
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 , the only way the denominator is divisible by p is if k = 0 or k = p.
Last edited by DFranklin; 1 week ago
0
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 , 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
X

new posts Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

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

### Poll

Join the discussion

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%