# Find the remainder given the following conditions?

$N$ is a natural number greater than $6$. Find the remainder when $N^7-N$ is divided by $6$. $$\text{(A)}\;\; 0 \quad\quad \text{(B)}\;\; 1 \quad\quad \text{(C)}\;\; 2 \quad\quad \text{(D)}\;\; 3$$

Taking assumption that $N=7$ I get $(7 \times 7 \times 7 \times 7 \times 7 \times 7 \times 7)/6 - 7/6 = 1-1 = 0$. Similarly by taking any number greater than $6$, I get remainder $0$.

Am I right In my approach. Please correct me if I am wrong?

• A fast approach would be to exploit the "metagame" knowledge that the result cannot depend on which $N>6$ you use. So if you choose $N$ to be some multiple of $6$, it is blatantly obvious that $N^7-N$ must be divisible by $6$ too, so (A) is the answer. – Henning Makholm Nov 2 '15 at 1:14
• Did you try all "any" numbers ? – Yves Daoust Nov 5 '15 at 14:54

$N^7 - N = N(N^6 - 1)$

If N = 6k then the remainder will be 0 because 6|N.

If N = 6k +- 1, then $N^6 = (6k)^6 \pm something*(6k)^5 + .... \pm something*(6k) + 1$ so $N^6 - 1 = 6(a\ bunch\ of\ stuff)$ so the remainder will be 0 because $6|N^2 - 1$

If N = 6k +/- 2, the $N^6 = (6k)^6 \pm something*(6k)^5 + .... \pm something*(6k) + 2^6$ so $N^6 - 1 = 6(a\ bunch\ of\ stuff) + 63$. So $N^7 - N = N(N^6 - 1) = (6k \pm 2)(6(a\ bunch\ of\ stuff) + 63) = 6(\ even \ more \ stuff) \pm 126 =6(\ even \ more \ stuff) \pm 21*6$ so the remainder is 0 because $6|N^7 - N$.

== late edit == Just realized the obvious

$M = N^7- N = N(N^3 - 1)(N^3 + 1)= N(N^2 + N + 1)(N - 1)(N^2 - N + 1)(N + 1)=(N-1)N(N+1)(N^2 - N + 1)(N^2 + N + 1)$

Which may or may not make things easier. Let's see.

If $N$ is even then 2 divides $N$. If $N$ is odd then 2 divides $N+1$. So 2 divides $M$.

If 3 divides $N$ then 3 divides $M$. If $N = 3k \pm 1$ then 3 divides $N \mp 1$. So 3 divides $M$.

So $6|M$. In fact 6 divides $N^3 - N$ while $N^7 - N$ = $(N^3 - N)(N^4 + N^2 + 1)$.

In fact, 6 divides the product of any three consecutive integers and $N^3 - N$ can be written as a product of three consecutive integers.

======

In hindsight, I'm a little surprise how weak this question is. To start with it's a multiple choice question so if there is one constant remainder it has to be 0 as N = 6k would have 0 remainder. Second it's a very easy and well, known fact that any 3 consecutive integers are divisible by 6. (I'm kicking myself for not realizing that earlier.) And there so much more to $N^7 - N$ then the division by 6. There's there entire factor $N^4 +N^2 + 1$ which is completely superfluous.

So here's a related not much more difficult puzzle, Prove $N^5 - 5N^3 + 4N$ is divisible by 120.

• Am I right in thinking this result is similar to proving when the sum of three consecutive integers is divisible by 6?? – Freelancer Nov 5 '15 at 15:24
• I think you mean product. 2+3+4 = 9 is not divisible by 6. Yes. If you have 3 consecutive integers one is divisible by 3 and at least one (maybe the same one, maybe not) is divisible by 2. so the product is divisible by 6. – fleablood Nov 5 '15 at 16:41
• Oh!!! Yes ssorry just as typing errors...so this means I can after some modifications use the method you used here to prove that that the product of three consecutive integers greater than 6 is divisible by 6.... – Freelancer Nov 5 '15 at 17:07
• Any 3 consecutive integers. Don't need to be greater than 6. – fleablood Nov 5 '15 at 17:14
• Well, as 0 is divisible by any number it could be any consecutive integers (but say 0*1*2 or -1*0*-1 is divisible by 6 seems like a cheat... but technically it's true.) Actually a far, far, far stronger result is any consecutive n integers is divisible by n! So any 5 consecutive integers is divisible by 120. In hind sight, I'm a little surprised how weak the original question was when there are much stronger results. – fleablood Nov 5 '15 at 19:56