Number Theory

Remark 1.1   For an arithmetic progression, $a_0, a_1=a_0+d, a_2=a_0+2d,\cdots$ to have infinitely many primes, it is necessary that gcd$(d,a_0)=1$.

This is true because the gcd will divide all terms. The converse is also true:

Theorem 1.2   (Dirichlet) Whenever gcd$(d,a_0)=1$, the arithmetic progression, $a_0, a_1=a_0+d, a_2=a_0+2d,\cdots$ will have infinitely many primes.

This remarkable theorem is proved using complex analysis. We shall give elementary proofs of special cases. The case $d=1$ is simply the infinitude of primes.

Theorem 1.3   (Euclid) There are infinitely many primes.

Proof. For a contradiction, assume there are finitely many, $p_1,\dots, p_n$. Construct $N=\Pi_{i=1}^np_i$. Then for any $i$, $p_i$ does not divide $N+1$, so $N+1$ is not divisible by any prime. This is a contradiction, since all numbers $\ge 2$ are divisible by some prime. (This can be easily proved by induction.) $\qedsymbol$

Definition 1.4   We say that two numbers, $a$, and $b$ are congruent mod m, or $a\equiv b \mod m$ if $m\mid b-a$.

Lemma 1.5   If $n\equiv-1\mod 4$, then it must have a prime divisor $\equiv-1\mod 4$.

Proof. $n$ is an odd number. Thus it is the product of odd primes. If all of these primes are $\equiv 1\mod 4$, then their product is also $\equiv 1\mod 4$, which is a contradiction. $\qedsymbol$

Theorem 1.6   There are infinitely many primes $\equiv-1\mod 4$.

Proof. Assume that there are finitely many, $p_1,\cdots p_n$. Construct $N=\Pi_{i=1}^np_i$. Then by the Lemma, $4N-1$ must have a prime divisor congruent to $-1\mod 4$. However, this is a contradiction, since no $p_i$ divides it (why?). $\qedsymbol$

The infinitude of primes $\equiv 1\mod 4$ is not so straightforward. We need the following

Lemma 1.7   If $p$ is an odd prime, and $p\mid a^2+1$, then $p\equiv 1 \mod 4$.

Theorem 1.8   There are infinitely many primes congruent to $1\mod 4$.

Proof. Assume that there are finitely many, $p_1,\cdots p_n$. Construct $N=\Pi_{i=1}^np_i$. Then, by the Lemma, all (odd) prime divisors of $4N^2+1$ must be congruent to $1\mod 4$. This is a contradiction, since this number is not divisible by any of the $p_i$. (Why did we multiply by 4?) $\qedsymbol$

We need to prove the Lemma. This, in turn, requires Fermat's Little Theorem, which we now state.

Theorem 1.9 (Fermat's Little Theorem)   If $p$ is a prime, then $p{\,\mid\,}a^p-a$.

• Equivalently: If $p$ is a prime then $a^{p}\equiv a\mod p$.
• Equivalently: If $p$ is a prime and $p\,\nmid\,a$, then $p{\,\mid\,}a^{p-1}-1$.
• Equivalently: If $p$ is a prime and $p\,\nmid\,a$, then $a^{p-1}\equiv 1\mod p$.

Exercise 1.10   Show that each of the last three statements is equivalent to the first.

Proof. We may, (by adding a multiple of $p$ to $a$) assume that $a$ is positive. Now consider all strings of length $p$ of numbers between $1$ and $a$. For example, if $p=7$, $a=4$, we could have $(1,4,4,3,4,1,1)$. There are $a^p$ such strings. Call two strings equivalent if ``they make the same necklace,'' i.e., they differ by cyclic rotation. That is, the above string is equivalent to $(4,4,3,4,1,1,1)$, $(4,3,4,1,1,1,4)$, $(3,4,1,1,1,4,4)$, etc. Now in most cases, there will be exactly $p$ equivalent strings. The exceptions are the strings $(x,x,x,x,\cdots,x)$, which will have only one string (themselves) in their equivalence class. Therefore the number of equivalence classes (``necklaces'') is $(a^p-a)/p+a$, so $(a^p-a)/p$ must be an integer. $\qedsymbol$

Definition 1.11   $a$ is a quadratic residue modulo the prime $p$ if $a\not\equiv 0 \mod p$ and there exists an $x$ such that $x^2\equiv a\mod p$.

Proof of Lemma 1.7. The condition is that $a^2\equiv-1\mod p$; and by Fermat's Little Theorem we have $a^{p-1}\equiv 1\mod p$. Since $p$ is odd, $1\equiv a^{p-1}\equiv (a^2)^{(p-1)/2}\equiv(-1)^{(p-1)/2}$. Now since $p$ is odd, $-1\not\equiv 1 \mod p$, so ${(p-1)/2}$ must be even, or $4{\,\mid\,}p-1$. $\Box$

Exercise 1.12   Prove: every prime greater than 3 is congruent to $\pm 1\mod 6$.

Exercise 1.13   There are infinitely many primes of the form $6k-1$. Hint. Follow the $4k-1$ case.

Exercise 1.14   There are infinitely many primes of the form $6k+1$.

This is harder; you need a new lemma:

Exercise 1.15   If $p$ is a prime and $p{\,\mid\,}a^2+a+1$, then $p=3$ or $p\equiv 1\mod 6$. Hint. Prove: $a^3\equiv 1\mod p.$

Definition 1.16   If $p\,\nmid\,a$, the order of $a\mod p$ is the smallest positive integer $k$, such that $a^k\equiv 1 \mod p$. We say $k=$ord$_p(a)$.

Exercise 1.17   Prove that the following statement is equivalent to Fermat's Little Theorem, 1.9.

• If $p$ is a prime and $p\,\nmid\,a$, then ord$_p(a)\mid p-1$.

Exercise 1.18   If $p$ is a prime number other than 2 or 5 then the decimal expansion of $1/p$ is periodic with period ord$_p(10)$.

Definition 1.19   We say that $a$ is a primitive root modulo $p$ if ord$_p(a)=p-1$.

Exercise 1.20   10 is a primitive root mod 7 if and only if 3 is a primitive root mod 7.

Exercise 1.21   Verify: $\{1,3,3^2,3^3,3^4,3^5,3^6\}\equiv\{1,3,2,6,4,5\} \pmod 7$, so that all numbers from 1 to 6 appear before repetition occurs in the sequence $3^k \mod 7$.

Exercise 1.22   Prove: $a$ is a primitive root mod $p$ if and only if the set $\{1,a,a^2,\cdots a^{p-2}\}$ represents all numbers numbers modulo $p$ that are not divisible by $p$.

Theorem 1.23   For every prime, $p$, there exists a primitive root mod $p$.

(We shall prove this important result later and will not use it in this set of exercises.)

Our next goal is to prove the following remarkable result:

Theorem 1.24 (Gauss)   A prime number $p$ can be written as a sum of two squares if and only if $p=2$ or $p\equiv 1 \mod 4$.

The ``only if'' part is straightforward:

Exercise 1.25   If $p\equiv -1 \mod 4$, then $p$ cannot be written as the sum of two squares. Hint. Observe that $(\forall x)(x^2\equiv 0$ or $1\mod 4)$.

To prove the converse, we need to learn about polynomials, quadratic residues, and lattices.

Theorem 1.26   Assume $F$ is a field. If $f(x)$ is a polynomial over $F$ then $x-a$ is a divisor of $f(x)-f(a)$.

Proof. Let $f(x)=\sum_{k=0}^n c_kx^k$. Since $x-a{\,\mid\,}x^k-a^k$, and $f(x)-f(a)=\sum c_k(x^k-a^k)$, we see that $(x-a){\,\mid\,}f(x)-f(a)$, $\qedsymbol$

Notation 1.27   $F[x]$ is the ring of all polynomials over $F$.

Corollary 1.28   If $f\in F[x]$, and $f(a)=0$, then $f(x)=(x-a)g(x)$ for some $g\in F[x]$.

Corollary 1.29   A nonzero polynomial of degree $n$ has at most $n$ roots.

Proof. By induction on $n$. $\qedsymbol$

Theorem 1.30   For an odd prime $p$, the following are equivalent:

1. [(a)] $p\equiv 1 \mod 4$.
2. [(b)] $-1$ is a quadratic residue mod$p$.

Proof. We already proved that (b) $\Rightarrow$ (a) (Lemma 1.7). For the other direction, assume now that $p\equiv 1 \mod 4$. Let $f(x)=x^p-x\in\mathbb{F}_p[x]$. By Fermat's Little Theorem, every element of $\mathbb{F}_p$ is a root of $f$. We factor $f$ as $x^p-x=x(x^{p-1}-1)=x(x^{(p-1)/2}-1)(x^{(p-1)/2}+1)$. Since none of the factors has more roots than its degree and the total number of roots is $p$, each factor must have exactly as many roots as its degree. In particular, there must exist a root $a$ of $(x^{(p-1)/2}+1)$. However, since $p\equiv 1 \mod 4$, $-1\equiv a^{(p-1)/2}\equiv( a^{(p-1)/4})^2 \mod p$. Therefore $-1$ is a square mod $p$. $\qedsymbol$

Definition 1.31   A lattice in $\mathbb{R}^n$ is a set $\mathbb{Z}{\mathbf{u}}_1+\dots+\mathbb{Z}{\mathbf{u}}_n=\{a_1{\mathbf{u_1}}+\dots+ a_n{\mathbf{u_n}}\,:\,a_1,\dots, a_n\in \mathbb{Z}\}$, where $\{{\mathbf{u_1}},\dots, {\mathbf{u_n}}\}$ is linearly independent over $\mathbb{R}$.

Definition 1.32   The set $\{\sum_{i=1}^n a_i{\mathbf{u}}_i\,:\, 0\le a_i\le 1\}$ is a fundamental parallelepiped of the lattice $L$.

Our main interest in this section will be the two-dimensional case, so instead of the $n$-dimensional parallelepipeds the reader may think of the familiar parallelograms in the plane.

Exercise 1.33   The translates of the fundamental parallelepiped by vectors in $L$ tile ${\mathbb{R}}^n$, i.e., they cover ${\mathbb{R}}^n$ without overlapping interiors.

Theorem 1.34   A fundamental parallelepiped is characterized by the fact that it is a parallelepiped which intersects the lattice in exactly its $2^n$ corners.

Recall that the area of a parallelogram spanned by ${\mathbf{u}}=\binom{u_1}{u_2}$ and ${\mathbf{v}}=\binom{v_1}{v_2}$ is
$Area=\vert u_1v_2-u_2v_1\vert=\vert\det\binom{u_1~v_1}{u_2~v_2}\vert$. (The analogous determinant expression works in $n$-dimensions.)

Exercise 1.35   All fundamental parallelepipeds have the same area.

Definition 1.36   A subset $S$ of a real vector space $V$, is called convex if for each $t\in \mathbb{R}$, $0<t<1$, and each ${\mathbf{u}}$, ${\mathbf{v}}$ in $V$, $(1-t){\mathbf{u}}+ t {\mathbf{v}}\in S$.

Theorem 1.37 (Minkowski)   Let $L$ be a lattice in $\mathbb{R}^n$, and the area of a findamental parallelogram be $A$. If $S$ is convex, centrally symmetric about the origin, and the area of $S$ is greater than $2^n A$, then $L\cap S\neq \{0\}$.

(The proof of this fundamental result in the ``Geometry of Numbers'' will be given later.) Next we use Minkowski's Theorem to prove Gauss' result, 1.24. The devilishly clever proof is due to Paul Turán.

Theorem 1.38   If $p\equiv 1 \mod 4$, then there are integers, $e$, and $f$, such that $p=e^2+f^2$.

Proof. By Theorem 1.30, there exists a $c$ such that $p{\,\mid\,}c^2+1$. Let ${\mathbf{u}}=\binom{c}{1}$ and ${\mathbf{v}}=\binom{p}{0}$ be vectors in $\mathbb{R}^2$. A general point in the lattice, $L$ spanned by these is $x{\mathbf{u}}+y{\mathbf{v}}=\binom{xc+yp}{x}$. Note that $(xc+yp)^2+x^2\equiv x^2(c^2+1)\equiv 0\mod p$, so if $\binom{e}{f}$ is in $L$, then $p{\,\mid\,}e^2+f^2$. Look at the open disk: $S=\{\binom{e}{f}: e^2+f^2<\sqrt{2p}\}$. The area of $S$ is $2\pi p>4p$, and the area of the fundamental parallelogram is $\vert c0-1p\vert=p$, so by Minkowski's Theorem, 1.37, there is some nonzero point in the lattice and in the disk. Therefore, there exist $e$ and $f$ such that $0<e^2+f^2<2p$, and $p{\,\mid\,}e^2+f^2$, so $e^2+f^2 =p$. $\qedsymbol$

Divisor game. Consider the following game, played by two people: Choose a number $n$. Players take turns naming a factor of $n$. Once a factor is named, it and none of its factors may be named again. The loser is the first player to say $n$.

Exercise 1.39   Find the winning strategies for the first player when $n=p^k$, $n=p^k q$, $n=p^kq^k$, $n=pqrs$.

Exercise 1.40   Show that the first player always has a winning strategy.
Hint. Do not try to find the winning strategy for all $n$.

Coin placing game. Given a rectangular table and an unlimited supply of quarters, each player takes turns placing quarters on the table (this is a ``continuous'' game). The quarters, once placed, may not be moved; they may not overlap, and may not hang over the edge.

Exercise 1.41   Find a winning strategy for the first player.