# Fermat's little theorem

• Jul 16th 2011, 03:40 PM
alexmahone
Fermat's little theorem
Use Fermat's theorem to show that for any positive integer n, the integer $n^{37}-n$ is divisible by 383838.

My attempt:

383838=(37)(19)(13)(7)(3)(2)

If 37 does not divide n, then by FLT, $n^{36} \equiv 1\ (mod\ 37)$. If, however, 37 divides n, then $n \equiv 0\ (mod\ 37)$. Thus in any case, $n^{37} \equiv n\ (mod\ 37)$.

If 19 does not divide p, then by FLT, $n^{18} \equiv 1\ (mod\ 19)\implies n^{36} \equiv 1\ (mod\ 19)$. If, however, 19 divides n, then $n \equiv 0\ (mod\ 19)$. Thus in any case, $n^{37} \equiv n\ (mod\ 19)$.

If 13 does not divide p, then by FLT, $n^{12} \equiv 1\ (mod\ 13)\implies n^{36} \equiv 1\ (mod\ 13)$. If, however, 37 divides n, then $n \equiv 0\ (mod\ 13)$. Thus in any case, $n^{37} \equiv n\ (mod\ 13)$.

If 7 does not divide p, then by FLT, $n^6 \equiv 1\ (mod\ 13)\implies n^{36} \equiv 1\ (mod\ 7)$. If, however, 7 divides n, then $n \equiv 0\ (mod\ 7)$. Thus in any case, $n^{37} \equiv n\ (mod\ 7)$.

If 3 does not divide p, then by FLT, $n^2 \equiv 1\ (mod\ 3)\implies n^{36} \equiv 1\ (mod\ 3)$. If, however, 3 divides n, then $n \equiv 0\ (mod\ 3)$. Thus in any case, $n^{37} \equiv n\ (mod\ 3)$.

If 2 does not divide p, then by FLT, $n \equiv 1\ (mod\ 2)\implies n^{36} \equiv 1\ (mod\ 2)$. If, however, 2 divides n, then $n \equiv 0\ (mod\ 2)$. Thus in any case, $n^{37} \equiv n\ (mod\ 2)$.

Combining these 6 congruences, we get

$n^{37} \equiv n\ (mod\ 383838)$

• Jul 16th 2011, 05:13 PM
Also sprach Zarathustra
Re: Fermat's little theorem
Quote:

Originally Posted by alexmahone
Use Fermat's theorem to show that for any positive integer n, the integer $n^{37}-n$ is divisible by 383838.

My attempt:

383838=(37)(19)(13)(7)(3)(2)

If 37 does not divide n, then by FLT, $n^{36} \equiv 1\ (mod\ 37)$. If, however, 37 divides n, then $n \equiv 0\ (mod\ 37)$. Thus in any case, $n^{37} \equiv n\ (mod\ 37)$.

If 19 does not divide p, then by FLT, $n^{18} \equiv 1\ (mod\ 19)\implies n^{36} \equiv 1\ (mod\ 19)$. If, however, 19 divides n, then $n \equiv 0\ (mod\ 19)$. Thus in any case, $n^{37} \equiv n\ (mod\ 19)$.

If 13 does not divide p, then by FLT, $n^{12} \equiv 1\ (mod\ 13)\implies n^{36} \equiv 1\ (mod\ 13)$. If, however, 37 divides n, then $n \equiv 0\ (mod\ 13)$. Thus in any case, $n^{37} \equiv n\ (mod\ 13)$.

If 7 does not divide p, then by FLT, $n^6 \equiv 1\ (mod\ 13)\implies n^{36} \equiv 1\ (mod\ 7)$. If, however, 7 divides n, then $n \equiv 0\ (mod\ 7)$. Thus in any case, $n^{37} \equiv n\ (mod\ 7)$.

If 3 does not divide p, then by FLT, $n^2 \equiv 1\ (mod\ 3)\implies n^{36} \equiv 1\ (mod\ 3)$. If, however, 3 divides n, then $n \equiv 0\ (mod\ 3)$. Thus in any case, $n^{37} \equiv n\ (mod\ 3)$.

If 2 does not divide p, then by FLT, $n \equiv 1\ (mod\ 2)\implies n^{36} \equiv 1\ (mod\ 2)$. If, however, 2 divides n, then $n \equiv 0\ (mod\ 2)$. Thus in any case, $n^{37} \equiv n\ (mod\ 2)$.

Combining these 6 congruences, we get

$n^{37} \equiv n\ (mod\ 383838)$

Correct!

Edit: Perhaps you need to mention the use of Chinese reminder theorem in the last stage.
• Jul 17th 2011, 03:09 AM
TheodorMunteanu
Re: Fermat's little theorem
A little prove for Fermat's theorem:Consider $(Z_p^*,\cdot)$ is a group with p-1 elements so from a corollary of Lagrange's theorem $\hat{x}^{p-1}=\hat{1} \Rightarrow x^p\equiv x(modp)$
Another way to prove is considering we have p pearls of a colours and $a^p$ strings .If we throw away the monocolour strings we have $a^p-a$ strings.Now we connect the ends of each string and results a necklace.knowing that a necklace doesn't differ by a rotation we have $\frac{a^p-a}{p}$ different necklaces hence the conclusion.