In case : it is sufficient to show that is a Carmichael number using Korselt's criterion
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.
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.