1. ## Fermat's little theorem

Use Fermat's theorem to show that for any positive integer n, the integer $\displaystyle 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, $\displaystyle n^{36} \equiv 1\ (mod\ 37)$. If, however, 37 divides n, then $\displaystyle n \equiv 0\ (mod\ 37)$. Thus in any case, $\displaystyle n^{37} \equiv n\ (mod\ 37)$.

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

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

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

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

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

Combining these 6 congruences, we get

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

2. ## Re: Fermat's little theorem

Originally Posted by alexmahone
Use Fermat's theorem to show that for any positive integer n, the integer $\displaystyle 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, $\displaystyle n^{36} \equiv 1\ (mod\ 37)$. If, however, 37 divides n, then $\displaystyle n \equiv 0\ (mod\ 37)$. Thus in any case, $\displaystyle n^{37} \equiv n\ (mod\ 37)$.

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

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

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

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

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

Combining these 6 congruences, we get

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

Correct!

Edit: Perhaps you need to mention the use of Chinese reminder theorem in the last stage.

3. ## Re: Fermat's little theorem

A little prove for Fermat's theorem:Consider$\displaystyle (Z_p^*,\cdot)$ is a group with p-1 elements so from a corollary of Lagrange's theorem $\displaystyle \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 $\displaystyle a^p$ strings .If we throw away the monocolour strings we have $\displaystyle 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 $\displaystyle \frac{a^p-a}{p}$ different necklaces hence the conclusion.