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

• Apr 17th 2012, 04:34 AM
math2011
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.
• Apr 20th 2012, 12:28 AM
princeps
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
• Apr 21st 2012, 08:35 AM
math2011
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.
• Apr 21st 2012, 12:25 PM
Petek
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.
• Apr 23rd 2012, 04:58 AM
math2011
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$.