## Math 417 Homework 10: Due Friday April 25

Instructions: You can discuss these problems with others, but write up your solutions on your own (i.e., don't just copy someone else's solutions, else the feedback I give you won't help you much). Please be neat and write in full sentences.

• [1] Let 1 < a < b be relatively prime integers. If gcd(phi(a), phi(b)) > 1, show that U(ab) is not cyclic. [Hint: Apply Cauchy's Theorem.]

• [2] Let n > 1 be an integer.
• (a) Show that Aut(Zn) is not cyclic if n is divisible by two different odd primes. [Hint: Apply problem 1.]
• (b) Show that Aut(Zn) is not cyclic if n is divisible by both an odd prime and by 4.

• [3] If n = 2r for an integer r > 0, show that Aut(Zn) is cyclic if and only if r is 1 or 2.

• [4] Show that if Aut(Zn) is cyclic, then one of the following is true:
• (a) n is 1, 2 or 4, or
• (b) n is ps or 2ps for an odd prime p and a positive integer s.

Aside: It is known that Aut(Zn) is cyclic in each of the cases listed in 4(a) and 4(b), so this gives a complete determination of those n for which Aut(Zn) is cyclic.

[Aside: It is easy to solve the quadratic equation x2 mod p = 1. There are two solutions in Zp, namely x = 0 and x = p-1. The next problem concerns solving x2 mod p = p - 1 in Zp. To do it, you may assume that Aut(Zp) is cyclic whenever p is a prime.]

• [5] Let p be a prime.
• (a) Show that x2 mod p = p - 1 has a solution if and only if either p = 2 or p - 1 is divisible by 4. [Hint: Think of x as being in U(p); then rephrase the problem in terms of |x|.]
• (b) Find all solutions x to x2 mod p = p - 1 when p is 5, 13, 17 and 29.