Algebraic Number Theory Problems + Solutions 661jr

Spencer Leonardis 5-29-2015 (Late) Homework 7 Math 118 Q1: a. Let p be an odd prime and let a ∈ Z such that (a, p) = 1. Show that if a is a quadratic residue mod p, then a is a quadratic residue modulo p n for any positive integer every n. Proof. Hensel’s Lemma: Let f (x) be a polynomial with integer coefficients, p be a prime, and suppose a is a solution of the congruence f (x) ≡ 0 mod p j such that f 0 (a) 6≡ 0 mod p. Then there exists an integer t (which is unique modulo p) such that a + tp j is a solution to the congruence f (x) ≡ 0 mod p j+1 . Suppose a is quadratic residue modulo p. Then x2 ≡ a mod p =⇒ x2 − a ≡ 0 (mod p). If we apply Hensel’s Lemma to the polynomial x2 − a ≡ 0 mod p, we can raise the powers of p inductively to p2 , p3 ,. . . , p n . In particular, if we have a unique solution modulo p then we are guaranteed a solution modulo p n . So if a is a quadratic residue modulo p2 , it is a quadratic residue p n for every n. In particular, if x2 ≡ a mod p k , one can find y such that (x + p k y)2 ≡ a mod p k+1 . i.e. (x + p k y)2 ≡ x2 + 2p k y mod p k+1 . 2 b. To handle the case when (a, p) 6= 1, solve problem 3.3.12. in the book: Consider the congruence x2 ≡ a mod pα with p a prime, α Ê 1, a = pβ b, (b, p) = 1. Prove that if β Ê α then the congruence is solvable, and that if β < α then the congruence is solvable if and only if β is even and x2 ≡ b mod pα−β is solvable. Proof. Same argument from (a) works here as well, we don’t need to the overly complicated problem to treat this case. c. Using CRT and the first part of this problem, conclude that if m is odd and (a, m) = 1, then a is a quadratic residue mod m if and only if a is a quadratic residue mod p for every prime p dividing m. α α α Proof. Suppose that a is a quadratic residue modulo m. Let m = p 1 1 p 2 2 · · · p k k denote the prime α α decomposition of m. By CRT, we have that Z/mZ ∼ = Z/p 1 1 Z × · · · × Z/p k k Z. Since x2 ≡ a mod m has a α α1 α2 2 solution, it must be the case that x ≡ a mod p 1 p 2 · · · p k k has a solution as well. Hence the system of congruences α x12 ≡ a mod p 1 1 α

x22 ≡ a mod p 2 2 .. . α

x2k ≡ a mod p k k is solvable. By applying Hensel’s Lemma (first part of problem), we can reduce the prime power case of this system to the prime case, proving that a is a quadratic residue modulo m for every p dividing m. 2 d. Using CRT and the first two parts of this problem prove the following. Let m be odd and let a ∈ Z. Prove that the congruence x2 ≡ a mod m has a solution if and only if for each prime p dividing m, one of the following conditions holds, where pα || m and pβ || a (this means that pα is the largest power of p dividing m and similarly for pβ and a): - β Ê α; - β < α, β is even, and a/pβ is a quadratic residue mod p. α Proof. The first direction is clear: A solution modulo m is also a solution modulo p i i . For the other α direction, for each i let x i be such that x2i ≡ a (mod p i i ). By the Chinese Remainder Theorem, there is αi an x such that x ≡ x i (mod p i ) for all i from 1 to t. This x is a solution of the congruence x2 ≡ a (mod m). So now it is sufficient to prove the result for m = pα , where p is prime. Let pβ be the largest power of p that divides a. We need to show that the congruence has a solution if and only if one of the two conditions of the post holds. The case β Ê α is easy, since x = 0 is a solution. Suppose now that β < α. Assume that x2 ≡ a (mod pα ). and let pγ be the largest power of p that divides x. Then unless γ = β/2, 1

x2 − a cannot be divisible by pα . So β = 2γ must be even. Let x = pβ/2 y. Then pβ y2 ≡ a (mod pα ). Dividing through by pβ we get y2 ≡ a/pβ (mod pα−β ). In particular, since β − α Ê 1, we have

y2 ≡ a/pβ (mod p),

and therefore a/pβ is a quadratic residue of p. Hence showing that a/pβ being a quadratic residue of p is sufficient in the case β < α. The solution of the congruence y2 ≡ a/pβ (mod p) =⇒ y2 − a/pβ ≡ 0 (mod p) can be lifted to a solution modulo any power of p, in particular pα−β by applying Hensel’s Lemma (as proved in the first two parts of the problem). This completes the proof. 2 Q2: 3.3.14. Suppose that p is a prime, p ≡ 1 mod 4, and that a2 + b2 = p with a odd and positive. Show that µ ¶ a = 1. p µ ¶ ³ ´ µ 2 ¶ µ 2¶ a p a + b2 b Proof. Using the laws of quadratic reciprocity, we obtain = = = = 1. 2 p a a a ¶ p µ X n(n + a) . Show that s(0, p) = p − 1. Show that 3.3.17. Let p be an odd prime, and put s(a, p) = p n=1 p X s(a, p) = 0. Show that if (a, p) = 1, then s(a, p) = s(1, p). Conclude that s(a, p) = −1 if (a, p) = 1. n=1

Proof.

Q3: ³p ´ ³p ´ p a. Let Q d = {a + b d : a, b ∈ Q}. Show that every element of Q d has a multiplicative inverse. In ³p ´ particular, Q d is a field. ³p ´ ³p ´ p Proof. Suppose γ ∈ Q d =⇒ γ = a + b d. To prove that Q d contains multiplicative inverses, observe p that for a non-square d and a − b d 6= 0 one has p p 1 b 1 a−b d a − d. = p · p = 2 γ a + b d a − b d a − b 2 d a2 − b 2 d ³p ´ If a, b ∈ Q =⇒ a2 , b2 ∈ Q ⇒ b2 d ∈ Q (since d ∈ Z) =⇒ a2 − b2 d ∈ Q ⇒ a2 −ab2 d , a2 −bb2 d ∈ Q. Thus γ1 ∈ Q d . 2 b. A number α ∈ C is called algebraic if α is algebraic over Q. In particular, a ∈ C ⊃ Q is algebraic if there exists 0 6= f (x) ∈ Q[x] such that f (α) = 0. The minimal polynomial m(x) of an algebraic number α ∈ C is the monic polynomial of smallest with coefficients in Q such that m(α) = 0. What is the minimal ³p degree, ´ p polynomial of α = a + b d ∈ Q d ? p Proof. Let α = a + b d. Then p 2 2 2 2 2 2 2 2 α−a = b d ⇒ ³p(α ´− a) = b d ⇒ α − 2αa + a = b d ⇒ m(x) = x − 2xa + a − b d is the minimal polynomial of Q d . 2 c. Show that if a rational number a ∈ Q satisfies a monic polynomial with integer coefficients, then in fact a ∈ Z. p Proof. Express a = q as a completely reduced rational in Q and assume to the contrary that p

a 6∈ Z =⇒ q 6= ±1. Observe that the rational number q ∈ Q, is a solution to qx − p = 0, where qx − p ∈ Z[x]. n Thus every ³ ´ a³ ∈´Q is algebraic. For an integer monic polynomial 0 = m(x) = x + · · · + a 1 x + a 0 ∈ Z[x], one

has m

p q

=

p n p + · · · + a1 q q

+ a 0 =⇒ p n + · · · + a 1 p + a 0 = 0 =⇒ p n ≡ 0 mod q. Since q 6= ±1 =⇒ q has a

2

prime factor v =⇒ v | a n =⇒ v | a. Thus v is a factor of both p and q contradicting the assumption that is completely reduced. ⇒⇐ 2

p q

d. (Quite difficult and therefore optional.) An element α ∈ C is called an algebraic integer if the coefficients of its minimal polynomial f (x) lie in Z. Generalizing part 3c, show that if α ∈ C satisfies a monic polynomial with integer coefficients, then in fact α is an algebraic integer. We won’t need this, but it is a very important fact. Proof. p ( ³p ´ Z[ 2dp] if d is even e. Show that the set of algebraic integers in Q d is equal to the ring O d = 1+ d Z[ 2 ] if d is odd. ³p ´ p 2 2 Proof. Let α = x + y d ∈ Q d . This is identical to 2x ∈ Z and x − d y ∈ Z. The first condition means x is half of an ordinary integer, so either x ∈ Z or x is half an odd number. If x ∈ Z then x2 ∈ Z, so d y2 ∈ Z. Then y ∈ Z because d is squarefree. (If y has a prime factor in its denominator, the square of that prime wouldn’t be cancelled by d, and then d y2 6∈ Z.) Therefore α has the necessary form, with a = x and b = y if d 6≡ 1 mod 4, or a = x − y and b = 2y if d ≡ 1 mod 4, or a = x − y and b = 2y if d ≡ 1 mod 4. If x is half an odd number, write x = a/2 with a odd. Then N(α) = x2 − d y2 = a2 /4 − d y2 , so multiplying through by 4 implies a2 − d(2y)2 ∈ 4Z In particular, d(2y)2 ∈ Z. Because d is squarefree, 2y is in Z so either y is in Z or is half an odd number. If y ∈ Z then a2 − d(2y)2 = a2 − 4d y2 is odd. ⇒⇐ it must be the case that à Therefore p ! p p 1+ d a b a−b y = b/2 with b an odd number, so α = x + y d = + +b which has the necessary d= 2 2 2 2 form because a − b is divisible by 2 ⇒

a− b 2

∈ Z. Hence the set of algebraic integers is the ring O d .

f. Let I be an ideal of O d . Show that I = { x : x ∈ I } is also an ideal of O d . Proof. Clearly 0 ∈ I. Note that for α, β ∈ I =⇒ α + β ∈ I, so for every α, β ∈ I, one has α + β = α + β ∈ I. Since for every α ∈ I we have −α ∈ I, it follows that for every α ∈ I, one has −α ∈ I. Hence I is an additive subgroup of O d . What is left to show is that I is closed under multiplication by ring elements of O d . Observe that for a ∈ O d and for x ∈ I one has ax ∈ I. Thus ax = ax ∈ I. Thus I is closed under multiplication by elements of O d , and combined with the fact that (I, +) É O d , we conclude that I is an ideal. 2 g. Let N(I) be the greatest common divisor in Z of N(x) for all x ∈ I. Since N(x) ∈ I I for x ∈ I, it is clear that (N(I)) ⊂ I I. Hence to prove that (N(I)) = I I, we have to prove the reverse inclusion. Thus, let α, β ∈ I; we will prove that αβ ∈ (N(I)) as follows: (i). First, prove that the polynomial f (x) = x2 − (αβ + αβ)x + ααββ has coefficients in Z and that αβ is a root. Proof (i). Let α, β ∈ I. Clearly 1 ∈ Z. We need to show that αβ + αβ and p ααββ are in Z. Observe that αα and ββ are both in Z because multiplying by the conjugate removes d in the middle . Thus ααββ ∈ Z. For the other element,pwe make an explicit calculation (the cancellation is less obvious). If α p is an element of the form a 1 + b 1 d and β is anpelement of p the form a 2 +p b 2 d we have p that αβ + αβ = (a 1 + b 1 d)(a d) + (a 1 − b 1 d)(a 2 + b 2 pd) p 2 − b2 p p = a1 a2 −a1 b2 d + b1 a2 d − b1 b2 d +a1 a2 +a1 b2 d − b1 a2 d − b1 b2 d = a1 a2 − b1 b2 d + a1 a2 − b1 b2 d Since a 1 , a 2 , b 1 , b 2 , d ∈ Z it follows that h p i a 1 a 2 − b 1 b 2 d + a 1 a 2 − b 1 b 2 d = αβ + αβ ∈ Z also. The same argument works for the ring Z

1+ d 2

. Hence f (x) ∈ Z[x]. Now observe that

f (αβ) = (αβ)2 − (αβ + αβ)(αβ) + ααββ = (αβ)2 − (αβ)2 − ααββ + ααββ = 0. Hence αβ is a root. (ii). Second, using the fact that N(I) divides the integers N(α + β), N(α), and N(β), prove that N(I) divides the coefficient of x in f (x), and that N(I)2 divides the constant coefficient.

3

2

Proof (ii). Since N(I) is the greatest common divisor in Z of N(x) for all x ∈ I, it follows that N(I) divides N(α + β) = αα + αβ + αβ + ββ, N(α) = αα, and N(β) = ββ. Thus N(I) | αβ + αβ. Since N(I) | N(α) and N(I) | N(β), it follows that N(I)2 | N(α)N(β) = ααββ. Thus N(I) divides the coefficient of x in f (x) and N(I)2 divides the constant coefficient. 2 1 f (x · N(I)) is a monic polynomial in Z[x], and note that (iii). Conclude that the polynomial g(x) = N(I)2 αβ the element is a root. N(I) Ã ! αβ 1 Proof (iii). We have that g(x) is integer monic since ∈ Z and since f (x) ∈ Z[x]. Clearly g = 0. N(I) N(I)2 (iv). Now consider two cases: either αβ is rational and thus an integer by part 3c. Otherwise g(x) is the αβ minimal polynomial of , and hence this number is an algebraic integer. Therefore it lies in O d by N(I) part 3e. αβ ∈ O d , so αβ ∈ (N(I)) as desired. Thus I I ⊂ O d , and combined with the fact that In either case, N(I) I I ⊃ O d , we conclude I I = O d . 2

4