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

Could someone please check my proof? Thanks in advance.