Use Fermat's Little Theorem to prove that $x^{13} \equiv x \mod 70$ for any $x$

Use Fermat's Little Theorem to prove that $$x^{13} \equiv x \mod 70$$ for any $$x$$. Any idea is appreciated.

• Do you know Fermat's Little Theorem? – Eleven-Eleven Feb 6 '14 at 3:03
• yes, I know it says $x^p \equiv x \mod p$ for any prime $p$. So I know $x^{13} \equiv x \mod 13$. But how can I proceed? – user112564 Feb 6 '14 at 3:07
• So $x^{71} \equiv x \mod 71$. But why does that help? – user112564 Feb 6 '14 at 3:09
• Hint: the congruence is true modulo $70$ if and only if it is true modulo $2$ and modulo $5$ and modulo $7$. – David Feb 6 '14 at 3:19
• as David said, your prime factors of 70 are 2,5,and 7... so by the iff.... – Eleven-Eleven Feb 6 '14 at 3:25

Apply the obvious extension of the theorem below to $\,3\,$ primes. In your case we have $\,k=1,\,$ and $\phi=12\,$ is a common multiple of $\phi(2)=1,\,\ \phi(5)=4,\,\ \phi(7)=6.$

Theorem $\ \ \ n^{\large k+\phi}\equiv n^{\large k}\pmod{p^i q^j}\ \$ assuming that $\ \color{#0a0}{\phi(p^i),\phi(q^j)\mid \phi},\,$ $\, i,j \le k,\,\ p\ne q.\ \ \$

Proof $\ \ p\nmid n\,\Rightarrow\, {\rm mod\ }p^i\!:\ n^{ \phi}\equiv 1\,\Rightarrow\, n^{k + \phi}\equiv n^k,\,$ by $\ n^{\Large \color{#0a0}\phi} = (n^{\color{#0a0}{\Large \phi(p^{ i})}})^{\large \color{#0a0}m}\overset{\color{blue}{\rm (E)}}\equiv 1^{\large m}\equiv 1\,$ by Euler $\!\rm\color{blue}{(E)}$.

$\qquad\quad\ \ \color{#c00}{p\mid n}\,\Rightarrow\, {\rm mod\ }p^i\!:\ n^k\equiv 0\,\equiv\, n^{k + \phi}\$ by $\ n^k = n^{k-i} \color{#c00}n^i = n^{k-i} (\color{#c00}{mp})^i$ and $\,k\ge i.$

So $\ p^i\mid n^{k+\phi}\!-n^k.\,$ By symmetry $\,q^j$ divides it too, so their lcm $= p^iq^j\,$ divides it too. $\$ QED

Remark $\$ Obviously the proof immediately extends to an arbitrary number of primes. This leads the way to Carmichael's Lambda function, a generalization of Euler's phi function.

• Thank you so much for your help! – user112564 Feb 6 '14 at 7:52