Recall that a Carmichael number is a composite number that passes the (bogus) primality test suggested by Fermat’s Little Theorem. In other words, a Carmichael number n is an integer that is composite...

Recall that a Carmichael number is a composite number that passes the (bogus) primality test suggested by Fermat’s Little Theorem. In other words, a Carmichael number n is an integer that is composite but such that, for any a ∈ Zn that’s relatively prime to n, we have aⁿ⁻¹
mod n = 1.

programming required) Write a program to verify that 561 is (a) not prime, but (b) satisfies a 560 mod 561 = 1 for every a ∈ {1, . . . , 560} that’s relatively prime to 561. (That is, verify that 561 is a Carmichael number.)