We call an integer m > 1 pseudo prime if m is not a prime and a'=1 mod m for all @ such that ged{a, m) = 1. (a) Prove that pseudo primes are odd. (b) Prove that if m is a pseudo prime and p is a prime, then p? 1 m. (Hint: You can prove this by contradiction. Assume that m is a pseudo prime and P is a prime such that p?|m. Leta = % 1. Prove that ged(m, @) = 1and @ ! = 1 4 p* !, where p Jt and k is the exponent of p in the standard form of m. ) (c) Let m=pi-pP2--Pr, where t > 1 and p1, Dy, - . ., are pairwise distinct odd primes. Prove that m is a pseudao prime if and only if p; 1|m 1 for all~d. (Hint: For one direction use the Chinese reminder theorem to find an @ such that @ is a primitive root for all p;.) (d) Show that m = 561 = 3 - 11 - 17 is a pseudo prime. Background story for this problem: Fermat's primality test Assume that given an m, we would like to decide whether m is a prime or not. One can propose the following method which is called Fermat's primality test. Let us choose @1, @g, - . ., @ uniformly at random from the set {1,2,...,m 1}. We output "m is a prime", if a;"_l =1 mod m for all 4, otherwise we output "m is not a prime". It follows from Fermat's theorem, that if m is a prime, this method always gives the right answer. If m is not a prime, then we might get a wrong answer. However, the probability of error is at most 2% except when m is a pseudo prime. Thus, this method is problematic only for pseudo primes. Unfortunately, pseudo primes exist, as we saw above