Show that 16^560 = 1 (mod 561) even though 561 is not a prime

a) Show that $\displaystyle 16^{560} \equiv 1 \pmod{561}$ even though 561 is not prime. (This shows that the converse of Fermat's Theorem is false.)

b) (Harder) Show that $\displaystyle a^{561} \equiv a \pmod{561}$ for all integers $\displaystyle a$.

a) $\displaystyle \phi(561) = 320$ and $\displaystyle gcd(16, 561) = 1$, then according to Euler's Theorem $\displaystyle 16^{560} = 16^{320} 16^{240} = 16^{240} \pmod{561}$. I do not know what to do next.

Re: Show that 16^560 = 1 (mod 561) even though 561 is not a prime

In case : $\displaystyle \gcd(a,561)=1$ it is sufficient to show that $\displaystyle 561$ is a Carmichael number using Korselt's criterion

Re: Show that 16^560 = 1 (mod 561) even though 561 is not a prime

Thanks. But my class hasn't covered Carmichael number. There must be another way to solve this.

Re: Show that 16^560 = 1 (mod 561) even though 561 is not a prime

For part (a), you need to show that $\displaystyle 16^{240} \equiv 1 \pmod {561}$ to complete the proof. Hint: Show that

$\displaystyle 16^{240} \equiv 1 \pmod{3}$

$\displaystyle 16^{240} \equiv 1 \pmod{11}$

$\displaystyle 16^{240} \equiv 1 \pmod{17}$

and then argue why this implies the needed congruence. For part (b), try to apply the above hint, modified as necessary.

Re: Show that 16^560 = 1 (mod 561) even though 561 is not a prime

Thank you.

If $\displaystyle gcd(a,b) = 1$ and $\displaystyle a | n$ and $\displaystyle b | n$, then $\displaystyle ab | m$.

We have $\displaystyle ax + by = 1$ for some integers $\displaystyle x,y$ due to Bezout's identity. Multiply both sides by $\displaystyle n$ we get $\displaystyle axm + bym = m$. The LHS can be divided by $\displaystyle ab$.