1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Do you know Fermat's Little Theorem? $\endgroup$ – Eleven-Eleven Feb 6 '14 at 3:03
  • $\begingroup$ 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? $\endgroup$ – user112564 Feb 6 '14 at 3:07
  • $\begingroup$ So $ x^{71} \equiv x \mod 71$. But why does that help? $\endgroup$ – user112564 Feb 6 '14 at 3:09
  • $\begingroup$ Hint: the congruence is true modulo $70$ if and only if it is true modulo $2$ and modulo $5$ and modulo $7$. $\endgroup$ – David Feb 6 '14 at 3:19
  • $\begingroup$ as David said, your prime factors of 70 are 2,5,and 7... so by the iff.... $\endgroup$ – Eleven-Eleven Feb 6 '14 at 3:25
3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.