# application of Fermat's little theorem

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$)

• Yes? That sounds like a good plan. – 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$

• "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)$? – Guy Apr 7 '14 at 12:14
• 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/ – srimali Apr 7 '14 at 12:17
• @user139296, please find the edited version – lab bhattacharjee Apr 7 '14 at 14:40
• @Sabyasachi, please find the edited version – lab bhattacharjee Apr 7 '14 at 14:42
• @labbhattacharjee oh okay. Lot clearer now. Thanks. – 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}$