Number Theory III
Problems (Michaelmas)

Problems marked \(\star \) are problems I expect everyone to try during the term; there will be around one per lecture. The assignments will be drawn from among these. Problems marked \(\dagger \) are (usually) harder and should be regarded as optional. You should do the remaining problems, but you might save some until the revision period.

1 Introduction

1.

(Exercise 1.2) Show that if \((a,b,c)\) is a primitive Pythagorean triple, then any two of \(a\), \(b\) and \(c\) are coprime.

2.

(Exercise 1.6) Suppose that \((a,b,c)\) is a primitive Pythagorean triple with \(b\) even, written as \[ a = m^{2}-n^{2}, \qquad b = 2mn, \qquad c = m^{2}+n^{2} \] for integers \(m>n>0\) as in Theorem 1.5. Show that \(m\) and \(n\) must be coprime and of opposite parity. Conversely, show that if \(m>n>0\) are coprime integers of opposite parity, then \((m^{2}-n^{2}, 2mn, m^{2}+n^{2})\) is a primitive Pythagorean triple.

3.

\(\star \) Find all integers \(x,y\) such that \[ y^{2}-y=x^{3}. \] (Hint: factorise the left hand side.)

Solution

Clearly \(x=y=0\) and \(x=0\), \(y=1\) are solutions. Write the equation as \[ y(y-1)=x^{3}. \] As \(y\) and \(y-1\) differ by \(1\), they are coprime. If \(y = 0\) or \(y = 1\) then \(x = 0\), giving the solutions above, so suppose that \(y\) and \(y-1\) are non-zero. Since \(\Z \) is a unique factorisation domain, we can write \[ y=\pm \prod _{i=1}^r p_{i}^{a_{i}}\] and \[y-1=\pm \prod _{j=i}^s q_{i}^{b_{i}}, \] where the \(p_{i}\) and \(q_{j}\) are primes, the \(p_{i}\) are pairwise distinct, as are the \(q_i\); all \(a_i\) and \(b_i\) are in \(\N \); and no \(p_{i}\) equals any \(q_{j}\) as \(y\) and \(y-1\) are coprime. Then the product of these is the factorisation of \(x^{3}\) into powers of distinct primes, and by uniqueness of factorisation every \(a_{i}\) and \(b_{j}\) is divisible by \(3\). Thus each term \(p_i^{a_i}\) or \(q_i^{b_i}\) is a cube. As \(-1=(-1)^{3}\), it follows that \(y\) and \(y-1\) are both cubes, say \[ y=u^{3},\qquad y-1=v^{3} \] with \(u,v\in \Z \) and \(u > v\) (as \(y > y-1\)). Then \[ 1=u^{3}-v^{3}=(u-v)(u^{2}+uv+v^{2}), \] and so \(u-v=u^{2}+uv+v^{2}= 1\). Substituting \(u=v + 1\) we obtain \(3v(v+1)=0\), so \(v=0\) or \(v=-1\). But these give only the excluded cases \(y=1\) or \(y=0\).

Therefore the only integer solutions are \(x=y=0\) and \(x=0\), \(y=1\).

2 EDs, PIDs and UFDs

4.

Let \(R=\Z [\sqrt {-13}]\), and set \(\alpha =1+\sqrt {-13}\in R\). Define the norm map \(N:R\rightarrow \Z \) by \(N(a+b\sqrt {-13})=a^{2}+13b^{2}\). As \(N(z) = |z|^2\), \(N\) is multiplicative.

(a)

Show that \(\alpha \bar {\alpha } = 2 \cdot 7\) gives two different factorisations of \(14\) into irreducibles.

(b)

Show that the ideal \((7, \alpha )_R\) is not principal.

5.

Let \(R\) be a Euclidean domain with Euclidean function \(\phi \). Show that:

(a)

\(\phi (a)\geq \phi (1)\) for all \(a\in R\setminus \{0\}\).

(b)

\(\phi (a)=\phi (1)\) if and only if \(a\) is a unit. (Hint: at some point divide \(1\) by \(a\) with remainder.)

(c)

If \(a,b\in R\setminus \{0\}\) and \(b\) is a non-unit, then \(\phi (ab)>\phi (a)\). (Hint: divide \(a\) by \(ab\) with remainder.)

6.

\(\star \) (Exercise 2.5) For \(n\in \N \), let \(N:\Z [\sqrt {-n}]\to \Z \) be the norm \(N(a+b\sqrt {-n})=a^{2}+nb^{2}\).

(a)

Show that \(\Z [\sqrt {-2}]\) is a Euclidean domain with Euclidean function \(N\).

(b)

Show that \(N\) is not a Euclidean function on \(\Z [\sqrt {-n}]\) for any \(n \ge 3\). Hint: consider the remainder of \(1 + \sqrt {-n}\) on division by \(2\).

Solution

(a) This is the same method as for \(\Z [i]\) in Lemma 2.3. Extend \(N\) to \(\Q (\sqrt {-2})\) by the same formula; since \(N(x)=x\bar {x}\), it is multiplicative, and \(N(x)=0\) if and only if \(x=0\).

For the first property, if \(x,y\in R=\Z [\sqrt {-2}]\) are non-zero then \(N(y)\geq 1\), so \(N(xy)=N(x)N(y)\geq N(x)\).

For the second property, let \(x,y\in R\) with \(y\neq 0\). Write \(x/y=a+b\sqrt {-2}\) with \(a,b\in \Q \), and let \(a'\) and \(b'\) be the closest integers to \(a\) and \(b\), so that \(|a-a'|\leq 1/2\) and \(|b-b'|\leq 1/2\). Set \(q=a'+b'\sqrt {-2}\in R\) and \(r=x-qy\in R\). Then \[ r=\left ((a-a')+(b-b')\sqrt {-2}\right )y, \] so \[ N(r)=\left ((a-a')^{2}+2(b-b')^{2}\right )N(y)\leq \left (\tfrac {1}{4}+\tfrac {2}{4}\right )N(y)=\tfrac {3}{4}N(y)<N(y), \] as \(N(y)>0\). So \(x=qy+r\) with \(r=0\) or \(N(r)<N(y)\).

(b) If \(N\) were a Euclidean function then, taking \(x = 1 + \sqrt {-n}\) and \(y = 2\), there would exist \(q\) and \(r\) in \(\Z [\sqrt {-n}]\) with \[1 + \sqrt {-n} = 2q + r\] and \(N(r) < N(2) = 4\). Then \(r\) has the form \(a + b\sqrt {-n}\) with \(a, b\) odd integers and its norm \(N(r)\) is \(a^2 + nb^2\). As \(a\) and \(b\) are odd, \[N(r) \ge 1^2(1+ n) \ge 4,\] contradiction.

(Geometrically: \(\frac {1+\sqrt {-n}}{2}\) is the centre of a rectangle with side lengths \(1\) and \(\sqrt {n}\) in the lattice \(\Z [\sqrt {-n}]\subset \C \), and its distance to the nearest lattice point is \(\frac {\sqrt {1+n}}{2}\geq 1\).)

7.

Let \(N:\Z [\sqrt {2}]\to \Z \) be the function \(N(a+b\sqrt {2})=a^{2}-2b^{2}\). Show that \(\Z [\sqrt {2}]\) is a Euclidean domain with Euclidean function \(|N|\). You may assume that \(N(xy) = N(x)N(y)\).

8.

\(\star \) In the ring \(\Z [i]\), we have \[ (1+3i)(1-3i)=10=2\cdot 5, \] but \(\Z [i]\) is a Euclidean domain (Lemma 2.3), hence a PID (Theorem 2.6), hence a UFD (Theorem 2.10). Explain why this is not a contradiction.

Solution

It is not a contradiction because the factors in the two products are not irreducible! Moreover, when decomposed into irreducibles, they become the same, up to units. To show this, try to decompose \(1+3i\) into irreducibles: it has norm \(10\) so if it has a proper factorisation \(1+3i=xy\), then the proper factors must have norm \(2\) or \(5\) (and are thus irreducible, as their norms are prime).

The elements of norm \(2\) are \(\pm 1\pm i\).

The elements of norm \(5\) are \(\pm 1\pm 2i\) and \(\pm 2\pm i\).

Dividing, \[ \frac {1+3i}{1+i}=\frac {(1+3i)(1-i)}{2}=2+i, \] so indeed \(1+3i=(1+i)(2+i)\) is the product of two irreducibles. Taking complex conjugates, \[ 1-3i=(1-i)(2-i). \] We thus have \[ (1+3i)(1-3i)=(1+i)(1-i)(2+i)(2-i), \] and the decomposition on the right-hand side is into irreducibles. On the other hand \(2=(1+i)(1-i)\) and \(5=(2+i)(2-i)\), so \[ 2\cdot 5=(1+i)(1-i)(2+i)(2-i) \] is the same factorisation. (Note also that \(1-i=-i(1+i)\), so \(2=-i(1+i)^{2}\) is, up to a unit, the square of an irreducible.)

9.

\(\dagger \) In this problem we prove the claim, made after Theorem 2.6, that \(\Z [\frac {1+\sqrt {-19}}{2}]\) is not a Euclidean domain.

(a)

Let \(R\) be a Euclidean domain that is not a field. Show that there is a non-zero non-unit \(u\in R\) with the following property: for every \(x\in R\) there is some \(z\in R^{\times }\cup \{0\}\) such that \(u\mid x-z\). (Hint: choose \(u\) to be “minimal” in some sense.)

(b)

Let \(\theta =\frac {1+\sqrt {-19}}{2}\), so that \(\theta ^{2}=\theta -5\), and let \(R=\Z [\theta ]=\{a+b\theta : a,b\in \Z \}\). Show that \(N(a+b\theta )=|a+b\theta |^{2}\) is given by \[ N(a+b\theta )=a^{2}+ab+5b^{2}, \] and deduce that the units of \(R\) are \(\pm 1\).

(c)

Use parts (a) and (b) to show that \(R\) is not a Euclidean domain.

10.

(Exercise 3.2) Show that the units of \(\Z [i]\) are \(\pm 1\) and \(\pm i\).

11.

\(\star \) Find all integers \(x,y\) with \(y\) odd such that \[ y^{2}+4=x^{3}. \] (\(\dagger \) Find the solutions with \(y\) even too.)

Solution

By Lemma 2.3 and Theorems 2.6 and 2.10, \(\Z [i]\) is a UFD, and by Problem 10 its units \(\pm 1\), \(\pm i\) are all cubes: \(\pm 1=(\pm 1)^{3}\) and \(\pm i=(\mp i)^{3}\). As in the proof of Theorem 2.12, if \(\alpha \bar {\alpha }\) is a cube in \(\Z \) and \(\alpha \) and \(\bar {\alpha }\) have no common irreducible factor, then \(\alpha \) is a unit times a cube, and hence a cube.

We have \((y+2i)(y-2i)=x^{3}\). If an irreducible \(\pi \) divides both factors, then it divides their difference \(4i=-i(1+i)^{4}\), so \(\pi \) is an associate of \(1+i\) (which is irreducible, as its norm \(2\) is prime). But then \(2=N(1+i)\) divides \(N(y+2i)=y^{2}+4\), which is odd.

Thus the factors are coprime and so \(y+2i=(a+bi)^{3}\) for some \(a,b\in \Z \), and comparing real and imaginary parts, \begin{align*} y&=a^{3}-3ab^{2}=a(a^{2}-3b^{2}),\\ 2&=3a^{2}b-b^{3}=b(3a^{2}-b^{2}). \end{align*}

So \(b\in \{\pm 1,\pm 2\}\), and \(3a^{2} - b^2 = 2/b\). The only cases leading to integer \(a\) are \(b=1\) or \(b=-2\), with \(a=\pm 1\). For \(b=1\) we get \(y=\mp 2\), which is not odd. For \(b=-2\) we get \(y=a(1-12)=\mp 11\), and then \(x^{3}=125\), so \(x=5\). So the solutions with \(y\) odd are \((x,y)=(5,\pm 11)\).

The solutions with \(y\) even. Write \(y=2z\). Then \(x\) is even, say \(x=2w\), and \(4z^{2}+4=8w^{3}\), that is, \(z^{2}+1=2w^{3}\). So \(z\) is odd, and then \(z^{2}+1\equiv 2\bmod 4\), so \(w\) is odd too. In \(\Z [i]\), \[ (z+i)(z-i)=2w^{3}=-i(1+i)^{2}w^{3}. \] This time the factors do have a common factor. As in the odd case, a common irreducible factor divides their difference \(2i=(1+i)^{2}\), so is an associate of \(1+i\). And \(1+i\) divides \(z+i=(z-1)+(1+i)\), as \(z-1\) is even, but \((1+i)^{2}=2i\) does not, as \(\frac {z+i}{2}\notin \Z [i]\).

So we run the argument of Theorem 2.12, keeping track of \(1+i\). Write \[ z+i=u(1+i)\prod _{j=1}^{r}\pi _{j}^{e_{j}} \] with \(u\) a unit, \(e_{j}\in \N \) and \(\pi _{j}\) irreducible, no two of them associates and none an associate of \(1+i\). Conjugating, \[ z-i=\bar {u}(1-i)\prod _{j=1}^{r}\bar {\pi }_{j}^{e_{j}}, \] and no \(\bar {\pi }_{k}\) is an associate of any \(\pi _{j}\), as otherwise it would be a common factor of \(z+i\) and \(z-i\) other than \(1+i\). Multiplying, and dividing by \(u\bar {u}(1+i)(1-i)=2\), \[ w^{3}=\prod _{j=1}^{r}\pi _{j}^{e_{j}}\bar {\pi }_{j}^{e_{j}}. \] All exponents in the factorisation of \(w^{3}\) are divisible by \(3\), so \(3\mid e_{j}\) for all \(j\). As \(u\) is a cube, \(z+i=(1+i)(a+bi)^{3}\) for some \(a,b\in \Z \).

Comparing imaginary parts in \(z+i=(1+i)(a+bi)^{3}\), \[ 1=(a^{3}-3ab^{2})+(3a^{2}b-b^{3})=(a-b)(a^{2}+4ab+b^{2}). \] Hence \(a-b=a^{2}+4ab+b^{2}=\pm 1\). If \(a=b+1\) then \(6b^{2}+6b+1=1\), so \(b=0\) or \(b=-1\); if \(a=b-1\) then \(6b^{2}-6b+1=-1\), which has no integer solutions. So \((a,b)=(1,0)\) or \((0,-1)\), giving \((a+bi)^{3}=1\) or \((a+bi)^{3}=i\). Then \(z+i=1+i\) or \(z+i=i-1\), so \(z=1\) or \(z=-1\). In either case \(w^{3}=\frac {z^{2}+1}{2}=1\), so \(w=1\), and \(x=2\), \(y=\pm 2\).

So the solutions with \(y\) even are \((x,y)=(2,\pm 2)\).

3 Sums of two squares

12.

(Wilson’s theorem) Let \(p\) be a prime. Show that \((p-1)!\equiv -1\bmod p\).

13.

\(\star \) Let \(\pi \in \Z [i]\) be irreducible. Show that \(\pi \) divides some prime \(p\in \Z \), and deduce that either \(\pi \in \{\pm p, \pm ip\}\) for some prime \(p\equiv 3\bmod 4\), or \(N(\pi )=p\) for some prime \(p\) with \(p=2\) or \(p \equiv 1 \bmod 4\).

Solution

As \(\Z [i]\) is a principal ideal domain, \(\pi \) is prime. Factorising the integer \(N(\pi )=\pi \bar {\pi }>1\) into primes of \(\Z \), \(\pi \) divides one of these factors. Thus there is a prime \(p \in \N \) with \(\pi \mid p\).

Then \(N(\pi )\mid N(p)=p^{2}\), and \(N(\pi )\neq 1\) as \(\pi \) is not a unit, so \(N(\pi )=p\) or \(N(\pi )=p^{2}\).

If \(N(\pi ) = p\) then \(p\) is a sum of two squares and so \(p = 2\) or \(p \equiv 1 \bmod 4\).

If \(N(\pi )=p^{2}\), then \(p/\pi \in \Z [i]\) has norm \(1\), so is a unit, and so \(p/\pi \) is one of \(\pm 1\) and \(\pm i\) by Exercise 3.2. Hence \(\pi =\pm p\) or \(\pm ip\). In particular \(p\) is irreducible in \(\Z [i]\), so by Proposition 3.3 it is not a sum of two squares, and so \(p\equiv 3\bmod 4\) by Theorem 3.5.

14.

\(\star \) Write \(9797 = 97 \times 101\) as a sum of two squares in two different ways.

15.

You are given that the number \(p=281\) is prime, and \(53^{2}\equiv -1\bmod p\).

(a)

Use the Euclidean algorithm in \(\Z [i]\) to find a greatest common divisor \(\pi \) of \(281\) and \(53+i\). That is, divide with remainder until you reach zero; the last nonzero remainder is a greatest common divisor.

(b)

Compute \(N(\pi )\), and hence write \(281\) as a sum of two squares.

16.

(Exercise 3.9.) Let \(n\in \N \) and suppose that \[ n=\prod _{i=1}^{r}p_{i} \] where \(p_{1},\ldots ,p_{r}\) are distinct primes that are \(\equiv 1\bmod 4\), and \(r \ge 1\). Show that the number of pairs \(x, y \in \N \) such that \(x^{2}+y^{2}=n\) is \(2^{r}\).

4 Finite field extensions

17.

Let \(\sqrt [6]{2}\) denote the positive real sixth root of \(2\).

(a)

Show that \([\Q (\sqrt [6]{2}):\Q ]=6\).

(b)

Show that \(x^{3}-\sqrt {2}\) is irreducible over \(\Q (\sqrt {2})\).

18.

Let \(\alpha \in \C \) be algebraic over \(\Q \) and assume that its minimal polynomial over \(\Q \) has odd degree. Show that \(\Q (\alpha )=\Q (\alpha ^{2})\).

19.

\(\star \) Let \(L=\Q (\sqrt {2},i)\).

(a)

Show that \([L:\Q ]=4\).

(b)

Find \(\theta \in L\) such that \(L=\Q (\theta )\).

20.

Let \(L/F\) be a field extension, let \(\alpha \in L\) be algebraic over \(F\) with minimal polynomial \(p_{\alpha }(x)\), and let \(f(x)\in F[x]\) with \(f(\alpha )\neq 0\).

(a)

Show that there are \(a(x),b(x)\in F[x]\) with \[a(x)f(x)+b(x)p_{\alpha }(x)=1,\] and deduce that \[f(\alpha )^{-1}=a(\alpha ).\] Explain how to find \(a(x)\) using the Euclidean algorithm in \(F[x]\). This gives another proof that \(F[\alpha ]=F(\alpha )\); compare Lemma 4.11.

(b)

Let \(\alpha =\sqrt [3]{2} \in \R \). Write \(\frac {1}{1+\alpha ^{2}}\) in the form \(c_{0}+c_{1}\alpha +c_{2}\alpha ^{2}\) with \(c_{0},c_{1},c_{2}\in \Q \).

21.

\(\star \) Let \(K=\Q (\alpha )\) be a field of degree \(d\) over \(\Q \), where \(\alpha \in \C \). Let \(a,b\in \Q \) with \(b\neq 0\). Show that \[ N_{K/\Q }(a+b\alpha )=(-b)^{d}p_{\alpha }(-a/b). \]

22.

\(\star \) Let \(\theta \in \C \) with \(\theta ^{3}=7\), and set \(K=\Q (\theta )\). Calculate \(\Tr _{K/\Q }(a+b\theta +c\theta ^{2})\) and \(N_{K/\Q }(a+b\theta +c\theta ^{2})\), where \(a,b,c\in \Q \).

23.

Let \(f(x)=x^{3}-2x-2\), let \(\theta \in \C \) be a root of \(f(x)\), and find the minimal polynomial of \(1+\theta +\theta ^{2}\) over \(\Q \).

24.

\(\star \) Let \(L=\Q (\sqrt {2},\sqrt {3})\) and \(K=\Q (\sqrt {3}) \subset L\).

(a)

Find the characteristic polynomial \(\chi _{\sqrt {2},L/\Q }(x)\).

(b)

Let \(\alpha =\frac {\sqrt {2}+\sqrt {6}}{2}\). Compute \(N_{L/K}(\alpha )\) and \(\Tr _{L/K}(\alpha )\).

(c)

Hence find \(N_{L/\Q }(\alpha )\) and \(\Tr _{L/\Q }(\alpha )\).

5 Number fields and algebraic integers

25.

\(\star \) (Examples and non-examples of algebraic integers).

(a)

Find a monic polynomial \(f(x)\in \Z [x]\) which has \(\sqrt {3}+i\) as a root. Conclude that \(\sqrt {3}+i\) is an algebraic integer.

(b)

Which of the following are algebraic integers? \[ \frac {4}{17},\qquad \sqrt {2}+\sqrt {7},\qquad e^{2\pi i/3},\qquad \frac {\sqrt [3]{3}}{2},\qquad \frac {7+\sqrt {5}}{2}. \]

26.

Let \(f(x)\in \Z [x]\) be a monic polynomial of degree at least \(1\), and let \(\alpha \in \bar {\Q }\). Show that \(f(\alpha )\in \bar {\Z }\) if and only if \(\alpha \in \bar {\Z }\).

27.

Let \(K\) be a number field and let \(I\) be a non-zero ideal of \(\cO _{K}\). Show that \(I\cap \Z \) is a non-zero ideal of \(\Z \).

28.

\(\star \) Let \(K=\Q (\theta )\), where \(\theta \in \C \) satisfies \(\theta ^{3}+\theta ^{2}-2\theta -4=0\), and let \(\alpha =\frac {\theta ^{2}+\theta }{2}\).

(a)

Show that \(\alpha \in \cO _{K}\). (Hint: find its characteristic polynomial.)

(b)

Find the minimal polynomial of \(\alpha \) over \(\Q \).

(c)

Show that \(\alpha \in \cO _{K}^{\times }\).

29.

\(\dagger \) Let \(K\) be a number field.

(a)

Let \(\alpha \in \bar {\Z }\). Show that \(p_{\alpha ,K}(x)\in \cO _{K}[x]\). (Hint: consider the roots of \(p_{\alpha ,K}(x)\).)

(b)

Let \(L/K\) be an extension of number fields and let \(\alpha \in \cO _{L}\). Show that \(\chi _{\alpha ,L/K}(x)\in \cO _{K}[x]\), and deduce that \(N_{L/K}(\alpha )\) and \(\Tr _{L/K}(\alpha )\) lie in \(\cO _{K}\).

30.

Let \(p\) be an odd prime, let \(\zeta \neq 1\) be a complex number with \(\zeta ^{p}=1\), and let \(R=\Z [\zeta ]\). Show that \[ \frac {1-\zeta ^{i}}{1-\zeta ^{j}}\in R^{\times } \] for all integers \(i\) and \(j\) not divisible by \(p\). (Hint: show that if \(i\equiv kj\bmod p\), then \(\frac {1-\zeta ^{i}}{1-\zeta ^{j}}=\frac {1-(\zeta ^{j})^{k}}{1-\zeta ^{j}}\), and that the latter lies in \(R\).)

31.

Let \(K=\Q (\sqrt [3]{2},\sqrt [3]{3})\) and \(\theta =\frac {1+\sqrt [3]{2}}{\sqrt [3]{3}}\). Show that \(\theta \in \cO _{K}^{\times }\).

32.

(Exercise 5.15) Let \(d,e\neq 1\) be squarefree integers with \(\Q (\sqrt {d})=\Q (\sqrt {e})\). Show that \(d=e\).

33.

\(\star \) Let \(K=\Q (\sqrt {-3})\).

(a)

Find \(\cO _{K}\) and \(\cO _{K}^{\times }\).

(b)

Show that \(\cO _{K}\) is a Euclidean domain.

(c)

Show that \(\Z [\sqrt {-3}]\) is not a UFD.