EulerFermatTheorem Intermediate

Problem - 4167

Show that $(2^{1194} + 1)$ is a multiple of $65$.


Because $65$ can be prime factorized into $5\times 13$, it is sufficient to show the given number is both a multiple of $5$ and a multiple of $13$.

By Fermat's little theorem, we have $2^4\equiv 1\pmod{5}$ and $2^{12}\equiv 1\pmod{13}$. Therefore $$ 2^{1194} - 1 \equiv \left(2^4\right)^{298}\times 2^2 + 1 \equiv 0\pmod{5}$$

and $$ 2^{1194} - 1 \equiv \left(2^{12}\right)^{99}\times 2^6 + 1 \equiv 0\pmod{13}$$

Therefore, the claim holds.

report an error