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.
 A: 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.
