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*11*17)\equiv\begin{cases}(a^(11*17))^3\pmod3\\(a^(3*17))^(11)\pmod{11}\\(a^(3*11))^(17)\pmod{17}\end{cases}\equiv\begin{cases}a^(11*17)\pmod3\\a^(3*17)\pmod{11}\\a^(3*11)\pmod{17}\end{cases}`

Now we apply the Euclidean algorithm. Outlining one step at a time, we have in the first case
`11*17=187=62*3+1`, so


`a^(11*17)\equiv a^(62*3+1)\equiv (a^(62))^3* a\stackrel{\mathrm{LFT}}\equiv a^(62)* a\equiv a^(63)\pmod3`

Next,
`63=21*3`, so


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

Next,
`21=7*3`, so


`a^(21)\equiv a^(7*3)\equiv(a^7)^3\stackrel{\mathrm{LFT}}\equiv a^7\pmod3`

Finally,
`7=2*3+1`, so


`a^7\equiv a^(2*3+1)\equiv (a^2)^3* a\stackrel{\mathrm{LFT}}\equiv a^2* a\equiv a^3\stackrel{\mathrm{LFT}}\equiv a\pmod3`

We do the same thing for the remaining two cases:


`3*17=51=4*11+7\implies a^(51)\equiv a^(4+7)\equiv a\pmod{11}`


`3*11=33=1*17+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*{11_3}^(-1)*11+a*{3_(11)}^(-1)*3\pmod{3*11}`

`\implies a^(561)\equiv a*2*11+a*4*3\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*{17_(33)}^(-1)*17+a*{33_(17)}^(-1)*33\pmod{17*33}`

`\implies a^(561)\equiv a*2*17+a*16*33\pmod{561}`

`\implies a^(561)\equiv562a\equiv a\pmod{561}`