# 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 $\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.
• Apr 20th 2012, 12:28 AM
princeps
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
• 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 $\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.
• 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 $\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$.