show that $a^{13} \equiv a\mod 35$ using Fermat's little theorem. Use Fermat's little theorem with primes 5 and 7.

$a^7 \equiv a (mod 7$) and

$a^5 \equiv a (mod 5$)

  • 2
    $\begingroup$ Yes? That sounds like a good plan. $\endgroup$ – Henning Makholm Apr 7 '14 at 12:11

If $p$ is a prime, either $p|a$ or $(p,a)=1$

If $\displaystyle p|a, p$ will divide $\displaystyle a^n-a=a(a^{n-1}-1)$ for integer $n-1\ge0$

For $\displaystyle(p,a)=1, a^{p-1}-1\equiv0\pmod p$ by Fermat's Little Theorem

So, $p$ will divide $\displaystyle a(a^m-1)$ for all integer $a$ if $(p-1)|m$

If $p=5,$ we need $4|m$

If $p=7,$ we need $6|m$

So, if $m$ is divisible by lcm$(4,6)=12;$ $5$ and $7$ will individually divide $a(a^m-1)$

Again as $(5,7)=1,$ it implies lcm$(5,7)=35$ will divide $a(a^m-1)$ if $12|m$

  • $\begingroup$ "as 5 is prime"? What am I missing? Why does $b$ is prime have to be true for $b|a\implies b|(a^k-a)$? $\endgroup$ – Guy Apr 7 '14 at 12:14
  • $\begingroup$ if i apply the little theorem i can have 2 congruence relations with mod 5 and mod 7. How can i maketwo mod relations together/ $\endgroup$ – srimali Apr 7 '14 at 12:17
  • $\begingroup$ @user139296, please find the edited version $\endgroup$ – lab bhattacharjee Apr 7 '14 at 14:40
  • $\begingroup$ @Sabyasachi, please find the edited version $\endgroup$ – lab bhattacharjee Apr 7 '14 at 14:42
  • $\begingroup$ @labbhattacharjee oh okay. Lot clearer now. Thanks. $\endgroup$ – Guy Apr 7 '14 at 14:45

Hint $\ $ Let $\,p,q\,$ be distinct primes. Then by Fermat's little Theorem $\,\color{#c00}{\rm F\ell T}$ we deduce

$\qquad n = (p\!-\!1)k\,\Rightarrow\,{\rm mod}\ p\!:\ a^{1+n} = a (a^{p-1})^k\overset{\color{#c00}{\rm F\ell T}}\equiv a\,\ $ [note it is clear if $\,a\equiv 0$]

Thus $\,p\!-\!1,q\!-\!1\mid n\,\Rightarrow\, p,q\mid a^{1+n}-a\,\Rightarrow\,pq\mid a^{1+n}-a,\ $ by $\ {\rm lcm}(p,q) = pq$

Thus $\,p,q=5,7\,\Rightarrow\, 4,6\mid 12\,\Rightarrow\,a^{\large 1+12}\equiv a\pmod{5\cdot 7}$


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.