2
$\begingroup$

$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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Henning Makholm Nov 2 '15 at 1:14
  • $\begingroup$ Did you try all "any" numbers ? $\endgroup$ – Yves Daoust Nov 5 '15 at 14:54
2
$\begingroup$

$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.

$\endgroup$
  • $\begingroup$ Am I right in thinking this result is similar to proving when the sum of three consecutive integers is divisible by 6?? $\endgroup$ – Freelancer Nov 5 '15 at 15:24
  • 1
    $\begingroup$ 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. $\endgroup$ – fleablood Nov 5 '15 at 16:41
  • $\begingroup$ 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.... $\endgroup$ – Freelancer Nov 5 '15 at 17:07
  • 1
    $\begingroup$ Any 3 consecutive integers. Don't need to be greater than 6. $\endgroup$ – fleablood Nov 5 '15 at 17:14
  • 1
    $\begingroup$ 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. $\endgroup$ – fleablood Nov 5 '15 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.