## 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.

Do four of the five problems. Justify your answers.

- [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(
**Z**_{n})
is not cyclic if n is divisible by two different odd primes.
[Hint: Apply problem 1.]
- (b) Show that Aut(
**Z**_{n})
is not cyclic if n is divisible by both an odd prime and by 4.

- [3] If n = 2
^{r} for an integer r > 0, show that
Aut(**Z**_{n}) is cyclic if and only if r is 1 or 2.

- [4] Show that if Aut(
**Z**_{n})
is cyclic, then one of the following is true:
- (a) n is 1, 2 or 4, or
- (b) n is p
^{s} or 2p^{s} for an odd
prime p and a positive integer s.

Aside: It is known that Aut(**Z**_{n}) 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(**Z**_{n}) is cyclic.

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

- [5] Let p be a prime.
- (a) Show that x
^{2} 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 x
^{2} mod p = p - 1
when p is 5, 13, 17 and 29.