Homework Assignment 4 Due Wednesday October 23

William Stein

Math 124  Harvard University  Fall 2002

Instructions: Please work with others, and acknowledge who you work with. There are 7 problems.

1. In this exercise (which is taken from Andrew’s Number Theory), we extend the definition of (\frac{a}{m}) to include the case where m is any odd number. If m = p_{1}p_{2} ⋯ p_{r} where the p_{i} are odd primes (not necessarily distinct), then

(\frac{n}{m}) = (\frac{n}{p_{1}} ) (\frac{n}{p_{2}} ) … (\frac{n}{p_{r}} ) .

This extended symbol is called the Jacobi symbol. In each of the following problems, assume what we’ve proved in class and what is in the notes.

(a) (2 points) Compute (\frac{7}{5!}).

(b) (2 points) Prove that if c is odd, then (\frac{ab}{c}) = (\frac{a}{c}) (\frac{b}{c}).

(c) (3 points) Prove that if b and c are odd, then (\frac{a}{bc}) = (\frac{a}{b}) (\frac{a}{c}).

(d) (2 points) Prove that if a ≡ b (mod c), where c is odd, then (\frac{a}{c}) = (\frac{b}{c}).

(e) (3 points) Prove that if c is odd, then (\frac{−1}{c}) = (−1)^{(c−1)/2}.

(f) (4 points) Prove that if a and c are odd and relatively prime, then

(\frac{a}{c}) (\frac{c}{a}) = (−1)^{\frac{1}{4} (a−1)(c−1)}.

(g) (3 points) Is it possible that (\frac{n}{m}) = 1 while the congruence x^{2} ≡ n (mod m) has no solution? Prove your answer.

2. (2 points each) Show how to solve each of the following problems by making intelligent use of MAGMA and the MAGMA documentation. Include the MAGMA code you write in your solution.

(a) Find all pairs (x, y) ∈ ℤ/17 × ℤ/17 such that y^{2} + y = x^{3} + x.

(b) How many positive integers n < 100 have the property that (ℤ/n)^{×} is not cyclic?

(c) The equation x^{2} + 3x + 5 = 0 has two solutions in the ring ℤ_{5} of 5-adic integers. Find each of them to precision O(5^{21}), so your answers should be of the form a_{0} + a_{1}5 + a_{2}5^{2} + ⋯ + a_{20}5^{20} + O(5^{21}). [Hint: If R:=pAdicRing(5), then the command R`SeriesPrinting:=true; switches to printing 5-adics in the form a_{0} + a_{1}5 + a_{2}5^{2} + · · ·.] (d) Find an integer x such that x^{2} + 3x + 5 ≡ 0 (mod 5^{30}).

(e) Find the coefficient of q^{289} in the product

q · ∏_{n=1}^{∞}(1 − q^{n})^{2}(1 − q^{11n})^{2}.

3. (3 points) Find a prime p such that the equation

x^{2} + y^{2} + z^{2} − 7 = 0

has no solution in ℤ_{p}. (Prove your assertion.)

4. (2 points each) Compute the first 5 digits of the 10-adic expansions of the following

rational numbers:

\frac{13}{2}, \frac{1}{389}, \frac{17}{19}, the 4 square roots of 41.

5. (3 points) Let N > 1 be an integer. Prove that the series

∑_{n=1}^{∞}(−1)^{n+1}n! = 1! − 2! + 3! − 4! + 5! − 6! + · · · .

converges in ℚ_{N}.

6. Prove that 9 has a cube root in ℚ_{10} using the following strategy (this is a special case of “Hensel’s Lemma”.)

(a) (2 points) Show that there is α ∈ ℤ such that α^{3} ≡ 9 (mod 10^{3}).

(b) (6 points) Suppose n ≥ 3. Use induction to show that if α_{1} ∈ ℤ and α^{3} ≡ 9 (mod 10^{n}), then there exists α_{2} ∈ ℤ such that α_{2}^{3} ≡ 9 (mod 10^{n+1}). (Hint: Show that there is an integer b such that (α_{1} + b10^{n})^{3} ≡ 9 (mod 10^{n+1}).)

(c) (2 points) Conclude that 9 has a cube root in ℚ_{10}.

7. (2 points each)

(a) Let p and q be distinct primes. Prove that ℚ_{pq} ≅ ℚ_{p} × ℚ_{q}.

(b) Is ℚ_{p^{2}} ismorphic to ℚ_{p} × ℚ_{p} or ℚ_{p}?