Question

(a) the number 561 factors as 3 · 11 · 17. first use fermat's little theorem to prove that a561 ≡ a (mod 3), a561 ≡ a (mod 11), and a561 ≡ a (mod 17) for every value of
a. then explain why these three congruences imply that a561 ≡ a (mod 561) for every value of
a.

Answer 1

LFT says that for any prime modulus $p$ and any integer $n$, we have

$n^p\equiv n\pmod p$

From this we immediately know that

$a^{561}\equiv a^{3\times11\times17}\equiv\begin{cases}(a^{11\times17})^3\pmod3\\(a^{3\times17})^{11}\pmod{11}\\(a^{3\times11})^{17}\pmod{17}\end{cases}\equiv\begin{cases}a^{11\times17}\pmod3\\a^{3\times17}\pmod{11}\\a^{3\times11}\pmod{17}\end{cases}$

Now we apply the Euclidean algorithm. Outlining one step at a time, we have in the first case $11\times17=187=62\times3+1$, so

$a^{11\times17}\equiv a^{62\times3+1}\equiv (a^{62})^3\times a\stackrel{\mathrm{LFT}}\equiv a^{62}\times a\equiv a^{63}\pmod3$

Next, $63=21\times3$, so

$a^{63}\equiv a^{21\times3}=(a^{21})^3\stackrel{\mathrm{LFT}}\equiv a^{21}\pmod3$

Next, $21=7\times3$, so

$a^{21}\equiv a^{7\times3}\equiv(a^7)^3\stackrel{\mathrm{LFT}}\equiv a^7\pmod3$

Finally, $7=2\times3+1$, so

$a^7\equiv a^{2\times3+1}\equiv (a^2)^3\times a\stackrel{\mathrm{LFT}}\equiv a^2\times a\equiv a^3\stackrel{\mathrm{LFT}}\equiv a\pmod3$

We do the same thing for the remaining two cases:

$3\times17=51=4\times11+7\implies a^{51}\equiv a^{4+7}\equiv a\pmod{11}$

$3\times11=33=1\times17+16\implies a^{33}\equiv a^{1+16}\equiv a\pmod{17}$

Now recall the Chinese remainder theorem, which says if $x\equiv a\pmod n$ and $x\equiv b\pmod m$, with $m,n$ relatively prime, then $x\equiv b{m_n}^{-1}m+a{n_m}^{-1}n\pmod{mn}$, where ${m_n}^{-1}$ denotes $m^{-1}\pmod n$.

For this problem, the CRT is saying that, since $a^{561}\equiv a\pmod3$ and $a^{561}\equiv a\pmod{11}$, it follows that

$a^{561}\equiv a\times{11_3}^{-1}\times11+a\times{3_{11}}^{-1}\times3\pmod{3\times11}$
$\implies a^{561}\equiv a\times2\times11+a\times4\times3\pmod{33}$
$\implies a^{561}\equiv 34a\equiv a\pmod{33}$

And since $a^{561}\equiv a\pmod{17}$, we also have

$a^{561}\equiv a\times{17_{33}}^{-1}\times17+a\times{33_{17}}^{-1}\times33\pmod{17\times33}$
$\implies a^{561}\equiv a\times2\times17+a\times16\times33\pmod{561}$
$\implies a^{561}\equiv562a\equiv a\pmod{561}$