(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.

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



From this we immediately know that



Now we apply the Euclidean algorithm. Outlining one step at a time, we have in the first case , so



Next, , so



Next, , so



Finally, , so



We do the same thing for the remaining two cases:





Now recall the Chinese remainder theorem, which says if and , with relatively prime, then , where denotes .

For this problem, the CRT is saying that, since and , it follows that





And since , we also have