Math 620  Problem Set #5  Due Mon., Oct. 15, 2001

1. Let K be a field, with multiplicative group K^{∗}. Let G be a finite subgroup of K^{∗}, of order n. Give a new proof that G is cyclic, as follows:

a) For m ≥ 1, let ψ(m) be the number of elements of K^{∗} having order exactly m. Show that if ψ(m) > 0 then the solutions in K to x^{m} − 1 = 0 are precisely the m elements 1, α, α^{2}, …, α^{m−1}, for some α ∈ K^{∗} of order m. Deduce that ψ(m) = ϕ(m) whenever ψ(m) ≠ 0.

b) Show directly that ψ(m) = 0 for all m not dividing n, and that ∑_{d=1}^{n} ψ(d) = n.

c) Deduce that ψ(d) = ϕ(d) for all d|n. [Hint: part (b) and PS4#3.]

d) Conclude that G is cyclic. [Hint: Set d = n.]

2. a) Show that if a_{1}, …, a_{n} ∈ ℝ with a_{i} > 0 for i > 1, and if P_{i} and Q_{i} are defined inductively by P_{i} = a_{i}P_{i−1} + P_{i−2} and Q_{i} = a_{i}Q_{i−1} + Q_{i−2}, with P_{−1} = Q_{0} = 0 and P_{0} = Q_{−1} = 1, then [a_{1}, …, a_{i}] = P_{i}/Q_{i}. [Hint: Induction.]

b) Deduce that the determinant of ( \begin{matrix}p_{i} & p_{i+1} \\ q_{i} & q_{i+1} \end{matrix} ) is ±1, with the sign alternating.

c) Now assume that all a_{i} ∈ ℤ. Show that P_{i}/Q_{i} is in lowest terms. Also show that if P_{i−1}/Q_{i−1} < P_{i}/Q_{i} then P_{i}/Q_{i} > P_{i+1}/Q_{i+1}, and similarly with the signs reversed.

d) Find |1/Q_{n}Q_{n+1}|, and show that consecutive convergents are consecutive Farey fractions (in some Farey sequence).

e) Use (c) and (d) to show that if α_{i} = [a_{1}, …, a_{i}] and α = α_{n}, then

α_{1} ≤ α_{3} ≤ α_{5} ≤ ⋯ ≤ α ≤ ⋯ ≤ α_{6} ≤ α_{4} ≤ α_{2}.

f) With the above notation, show that |α_{i} − α| < 1/Q_{i}^{2}.

g) Show that α_{i} is the best approximation to α (in terms of absolute value of the difference) among fractions with denominator ≤ Q_{i}. [Hint: Use part (d).]

3. Suppose that a_{1}, a_{2}, … ∈ ℤ with a_{i} > 0 for i > 0. Let α_{i} = [a_{1}, …, a_{i}]. Show that the sequence {α_{i}}_{i=0}^{∞} converges to a positive real number α. Also show that α uniquely determines the sequence {α_{i}}.

4. a) Find the infinite continued fractions [a_{1}, a_{2}, …] for α = \sqrt{2}, \sqrt{3}, \sqrt{5}, \frac{1 + \sqrt{5}}{2}, \sqrt{7}.

Conjectures? Now try ^{3} \sqrt{2}.

b) Calculate the first several successive convergents of the infinite continued fractions in part (a), both as fractions and as decimals. What patterns do you see? Conjectures? Proofs?

5. For n > 1, let P_{n} be the set of primes ≤ n; let S_{n} ⊂ P_{n} be the set of primes that split in ℤ[i]; let S′_{n} ⊂ P_{n} be the set of primes that remain prime in ℤ[i]; and let R_{n} ⊂ P_{n} be the set of primes that ramify in ℤ[i]. Compute |S_{n}|/|P_{n}|, |S′_{n}|/|P_{n}|, and |R_{n}|/|P_{n}| for n = 20, 50, 100. Conjectures?

6. For each of the following n, find the structure of the abelian group U_{n} = (ℤ/n)^{∗}. For those that are cyclic, find a primitive root (i.e. generator of U_{n}). n = 50, 64, 48, 99.