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

a) Show that even though 561 is not prime. (This shows that the converse of Fermat's Theorem is false.)

b) (Harder) Show that for all integers .

a) and , then according to Euler's Theorem . 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 : it is sufficient to show that 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 to complete the proof. Hint: Show that

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 and and , then .

We have for some integers due to Bezout's identity. Multiply both sides by we get . The LHS can be divided by .