# Use Fermat's Little Theorem to show [duplicate]

Show, with the help of Fermat’s little theorem, that if $n$ is a positive integer, then $42$ divides $n^{7} − n$.

I don't really know how to show Fermat is about primes. I have a slightly idea about numbers $42-1$ and $7$, but no idea what to do with it. This is my exam practice question that prof. gave to me with no answer provided.

• Just to start you off: Fermat's little theorem gives you that $n^7 - n$ is an integer multiple of $7$. So now you have to show that it divides $2$ and $3$. – Colm Bhandal Dec 3 '15 at 13:30
• Yes it is a duplicate. Oh well I've already posted my answer – Colm Bhandal Dec 3 '15 at 13:43
• Oh sorry I forgot to check it first, what can I do – Wongsakorn Dec 3 '15 at 13:50

To start you off: Fermat's little theorem gives you that $n^7 - n$ is an integer multiple of $7$. So now you have to show that it is divisible by $2$ and $3$. To show that $2$ divides $n^7 - n$, rearrange to $n(n^6 - 1)$. If $n$ is even, we're done. Else $n^6 -1$ is even, and we're done. So all we're left with is divisibility by $3$. In this case, $n^3$ is either of the form $3k + 1$ or $3k - 1$. Notice though, that:
$$(3k + 1)^2 = 3(3k^2 + 2k) + 1$$ and $$(3k - 1)^2 = 3(3k^2 - 2k) + 1$$
Both are of the form $3r + 1$, for some $r$. So $n^6$ will always be of the form $3u + 1$, and in turn $n^6 - 1$ will be of the form $3u$, proving divisibility by 3. So to gather it all together, our number is divisible by $7$ by Fermat's little theorem, and is divisible by $2$ and $3$ by the above, and so a factor of our number is $42 = 2 \times 3 \times 7$.