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

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

a) Show that $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 $a^{561} \equiv a \pmod{561}$ for all integers $a$.

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

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

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

3. ## 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.

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

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

$16^{240} \equiv 1 \pmod{3}$
$16^{240} \equiv 1 \pmod{11}$
$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.

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

Thank you.

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

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