1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Colm Bhandal Dec 3 '15 at 13:30
  • $\begingroup$ Yes it is a duplicate. Oh well I've already posted my answer $\endgroup$ – Colm Bhandal Dec 3 '15 at 13:43
  • $\begingroup$ Oh sorry I forgot to check it first, what can I do $\endgroup$ – Wongsakorn Dec 3 '15 at 13:50
2
$\begingroup$

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

$\endgroup$

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