Exercise (7.4).13

Prove that there are infinitely many primes of the form $3m + 1$ without using Dirichlet’s Theorem. 

Hint: You may find the result of question 5 helpful.

For the purpose of contradiction we assume there are a finite number $k$ of primes $p_1, p_2, \ldots, p_k$ of the form $3m+1$, where $m$ is some positive integer. 

We construct a number $N$ as follows

$$ N = (p_1 \times p_2 \times \ldots p_k )^2 + 3 $$

This $N$ is of the form $3m+1$ for some integer $m$.

There are two cases for $N$, prime and composite. Let's consider each in turn. 

Case $N$ prime

If $N$ is prime, then it is larger than any of the $p_1, p_2, \ldots, p_k$ primes. 

We've established that $N$ is of the form $3m+1$. This contradicts the assumption that the only primes of the form $3m+1$ are $p_1, p_2, \ldots, p_k$.

Case $N$ composite

If $N$ is composite it has an odd prime factor $p$, and so

$$ (p_1 \times p_2 \times \ldots p_k)^2 \equiv -3 \pmod p $$

Exercise (7.4).5 tell us $(\frac{-3}{p})=1 \iff p \equiv 1 \pmod 6$. That is, $p=6k+1$ for some integer $k$. Rewriting as $p=3(2k)+1$ means $p$ is of the form $3m+1$.

This $p$ is not one of the $p_1, p_2, \ldots, p_k$ because none of these divide $N=(p_1 \times p_2 \times \ldots p_k)^2 + 3$. If one $p_i$ did divide $N$ then it would have to divide 3, a contradiction. 

This $p$ contradicts the assumption that the only primes of the form $3m+1$ are $p_1, p_2, \ldots, p_k$.

Both cases for $N$ contradict the assumption there are a finite number of primes of the form $3m+1$, and so there are infinitely many primes of this form.

Exercise (7.4).12

Prove that the odd prime divisors of the integer $n^2 + 1$ are of the form $4k + 1$.

If odd prime $p$ is a factor of $n^2+1$ then

$$ n^2 \equiv -1 \pmod p $$

From Proposition (7.11) extended by the result from Exercise (7.1).6 we know that $(\frac{-1}{p})=1 \iff p \equiv 1 \pmod 4$. That is, $p=4k+1$ for some integer $k$.

Exercise (7.4).11

Let $p= 13$ and $a = 16$. Show that

$$\sum_{k=1}^{(p-1)/2} \lfloor \frac{a \times k}{p} \rfloor = 23 $$

but $g= 2$ where $g$ is as defined in Gauss’s Lemma. Explain why Lemma (7.20) fails in this case.

The following table shows the calculations which confirm the sum is 23.

k	floor (16k/13)
1	1
2	2
3	3
4	4
5	6
6	7
	23

The Lemma is not applicable because it requires $a$ to be odd, but here $a=16$ is even.

Exercise (7.4).10

Prove Lemma (7.20).

Let's remind ourselves of Lemma (7.20).

Let $p$ be an odd prime and $a$ also be odd such that $p \not \mid a$. Let $g$ be the number of negative residues as defined in Gauss’s Lemma (7.14). We have

$$\sum_{k=1}^{(p-1)/2} \lfloor \frac{a \times k}{p} \rfloor  \equiv g \pmod 2 $$

We start with the division algorithm and write $ak$ as

$$ ak = p \times \lfloor \frac{ak}{p} \rfloor + r $$

where $r$ is the least positive residue of $ak$ modulo $p$.

Next we'll consider the set $R$ of values of $r$ for $1 \le k \le \frac{p-1}{2}$.

$$ R = \{s_1, s_2, \ldots,  r_h, \quad t_1, t_2, \ldots,  t_g\}$$

where the residues $1 \le s_i \le \frac{p-1}{2}$ and $\frac{p+1}{2} \le t_i \le (p-1)$. Here $g$, by definition, is the number of least positive residues larger than $\frac{p-1}{2}$, and $g+h=\frac{p-1}{2}$.

We'll show the residues are distinct, a fact we'll use later. Consider two residues $r_1, r_2 \in R$. 

$$ r_1 \equiv r_2 \pmod p \implies ak_1 \equiv ak_2 \pmod p \implies k_1\equiv k_2 \pmod p $$

Since $1 \le k_1,k_2 \le \frac{p-1}{2}$, this means $k_1=k_2$. That is, no two residues are congruent modulo $p$, and since the set $R$ is of least positive residues, they are all less than $p$, and so incongruence also means inequality.

We now construct another set $S$ from $R$ by replacing those elements $t_i$ with $p-t_i$. Note that since  $\frac{p+1}{2} \le t_i \le (p-1)$, this means  $1 \le p - t_i \le \frac{p-1}{2}$.

$$ S = \{s_1, s_2, \ldots,  r_h, \quad p-t_1, p-t_2, \ldots,  p-t_g\}$$

We'll show that $S=\{1,2,3, \ldots, \frac{p-1}{2}\}$. To do this we first note that there are $\frac{p-1}{2}$ elements of $S$ all less than or equal to $\frac{p-1}{2}$. We also need to show no two elements are the same. We know all the $s_i$ are distinct, and all the $t_i$ are distinct. Let's consider whether $s_i$ and $p-t_i$ are distinct. 

$$ s_i \equiv p-t_i \pmod p \implies s_i + t_i \equiv 0 \pmod p \implies a (k_1 + k_2) \equiv 0 \pmod p \implies k_1 +k_2 \equiv 0 \pmod p $$

This is a contradiction since $2 \le k_1+k_2 \le p-1$, and so no two elements of $S$ are congruent.

Since $S$ has $\frac{p-1}{2}$ incongruent elements, all of value less than or equal to $\frac{p-1}{2}$, then it must be that 

$$ S = \{1, 2, 3, \ldots , \frac{p-1}{2} \}$$

Let's consider the sum of the elements of $S$,

$$ \sum_{k=1}^{(p-1)/2}k  = \sum_{i=1}^{h} s_i + \sum_{i=1}^{g} p-t_i \tag{i}$$

Let's also consider the sum of $ak$ over $1 \le k \le \frac{p-1}{2}$, 

$$  \sum_{k=1}^{(p-1)/2} ak = \sum_{k=1}^{(p-1)/2}p \lfloor \frac{ak}{p} \rfloor +\sum_{i=1}^{h} s_i + \sum_{i=1}^{g} t_i   \tag{ii} $$

Subtracting (ii)  from (i), 

$$  (a-1)\sum_{k=1}^{(p-1)/2} k = p \sum_{k=1}^{(p-1)/2} \lfloor \frac{ak}{p} \rfloor -pg + 2\sum_{i=1}^{g} t_i   $$

Taking modulo 2 means removing terms that are even, noting that $(a-1)$ is even,

$$  pg \equiv p \sum_{k=1}^{(p-1)/2} \lfloor \frac{ak}{p} \rfloor  $$

Dividing by $p$ is permissible since $p \not \mid 2$

$$  \sum_{k=1}^{(p-1)/2} \lfloor \frac{ak}{p} \rfloor \equiv g  \pmod 2 $$

This is the desired result.

Note: this solution was helped by Esenstein's Lemma (proofwiki).

Exercise (7.4).9

Prove Corollary (7.17).

We remind ourselves of  Prove Corollary (7.17). 

Let p and q be distinct odd primes, then

$$ (\frac{p}{q}) = \begin{cases} (\frac{q}{p}) & \text{ if } p \equiv 1 \pmod 4 \text{ or } q \equiv 1 \pmod {4}  \\ -(\frac{q}{p}) & \text{ if } p \equiv q \equiv 3 \pmod {4}  \end{cases} $$

We use the result we proved in Exercise (7.4).3. If $p$ and $q$ are distinct odd primes then

$$ (\frac{p}{q}) \times (\frac{q}{p}) = \begin{cases} 1 & \text{ if } p \equiv 1 \pmod {4} \text{ or } q \equiv 1 \pmod {4}  \\ -1 & \text{ if } p \equiv q \equiv 3 \pmod {4}  \end{cases}$$

Let's consider each of the two cases in turn.

If $p \equiv 1 \pmod 4$ or $q \equiv 1 \pmod 4$ then

$$ (\frac{p}{q}) \times (\frac{q}{p}) = 1$$

This is only possible if $ (\frac{p}{q})$ and $(\frac{q}{p})$ are both 1 or both -1, that is  $(\frac{p}{q}) = (\frac{q}{p})$. The corollary holds for this case.

If $p \equiv q \equiv 3 \pmod 4$ then

$$ (\frac{p}{q}) \times (\frac{q}{p}) = -1$$

This is only possible $ (\frac{p}{q}) = 1$ and $(\frac{q}{p})=-1$,  or $ (\frac{p}{q}) = -1$ and $(\frac{q}{p})=1$. That is  $(\frac{p}{q}) = -(\frac{q}{p})$. The corollary holds for this case.

We have shown Corollary (7.17) holds for all possible cases of $p$ and $q$.

Exercise (7.4).8

Determine

$$ \sum_{k=1}^{(q-1)/2} \lfloor \frac{k \times p}{q} \rfloor + \sum_{k=1}^{(p-1)/2} \lfloor \frac{k \times q}{p} \rfloor $$

for the primes $p= 17$ and $q= 13$. Also interpret your answer geometrically by counting the lattice points above and below the line $y=\frac{q}{p}x$.

For $p= 17$ and $q= 13$, we have

$$ \begin{align} \sum_{k=1}^{6} \lfloor \frac{k \times 17}{13} \rfloor + \sum_{k=1}^{8} \lfloor \frac{k \times 13}{17}  \rfloor & = \lfloor \frac{17}{13} \rfloor + \lfloor \frac{34}{13} \rfloor  +  \lfloor \frac{51}{13} \rfloor +  \lfloor \frac{68}{13} \rfloor  +  \lfloor \frac{85}{13} \rfloor  +  \lfloor \frac{102}{13} \rfloor \\ \\ & +  \lfloor \frac{13}{17} \rfloor +  \lfloor \frac{26}{17} \rfloor +  \lfloor \frac{39}{17} \rfloor +  \lfloor \frac{52}{17} +  \lfloor \frac{65}{17} \rfloor +  \lfloor \frac{78}{17} \rfloor +  \lfloor \frac{91}{17} \rfloor +  \lfloor \frac{104}{17} \rfloor \\ \\ & = (1 + 2 + 3 + 5 + 6 + 7) + (0 + 1+2+3+3+4+5+6) \\ \\ & = 24 + 24 = 48  \end{align}$$

Alternatively we can use Eisenstein's Lemma (7.19)

$$ \sum_{k=1}^{6} \lfloor \frac{k \times 17}{13} \rfloor + \sum_{k=1}^{8} \lfloor \frac{k \times 13}{17}  \rfloor = (\frac{13-1}{2}) \times (\frac{17-1}{2}) = 6 \times 8 = 48 $$

The following graph (link) illustrates the lattice points above and below the line $y=\frac{13}{17}x$. 

We can see that below the line there are columns of lattice points of heights 1, 2, 3, 3, 4, 5, 6, corresponding to the calculation above.

Similarly, above the line there are rows of lattice points of length 1, 2, 3, 5, 6, 7, also corresponding to the calculation above.

However we count the lattice points, the total is $8 \times 6 = 48$.

Exercise (7.4).7

Prove that there are infinitely many primes of the form $8k- 1$ without using Dirichlet’s Theorem.

Hint: Suppose there are a finite number of primes $p_1, p_2, \ldots , p_k$ of this form and consider the integer $(4p_1p_2\ldots p_k)^2− 2$ and then use Proposition (7.15).

We assume, for the purpose of contradiction, there are finite primes $p_1, p_2, \ldots, p_k$ of the form $8k-1$, where $k$ is a positive integer. 

Let's consider a constructed number $N=(p_1p_2 \ldots p_k)^2-2$, noting that $p_i \equiv -1 \pmod 8$,

$$ N \equiv (p_1p_2 \ldots p_k)^2 -2 \equiv (-1 \times -1 \ldots -1)^2 -2 \equiv 1-2 \equiv -1 \pmod 8  $$

This means $N$ is of the form $8k-1$. 

We have two cases for $N$, prime or composite.

Case $N$ prime

If $N$ is prime, then we have found another prime of the form $8k-1$ that is larger than any of the $p_1, p_2, \ldots, p_k$ of the form $8k-1$. This contradicts the assumption there are only $k$ primes of form $8k-1$.

Case $N$ composite

If $N$ is composite, then it has a prime factor, which we can call $q$. This means

$$ (p_1p_2 \ldots p_k)^2 \equiv 2 \pmod q $$

By Proposition (7.15) this means $q \equiv \pm 1 \pmod 8$.

Let's consider each of these two options.

• If $q \equiv -1 \pmod 8$, that is $q=8t-1$ for some integer $t$, then $q$ must be one of the known $p_1, p_2, \ldots, p_k$. This gives us $q \mid (p_1p_2 \ldots p_k)^2-2 \implies q \mid 2$. This is a contradiction, and invalidates the assumption there are only $k$ primes of form $8k-1$.

• If all the odd prime factors of $N$ are congruent to $1 \pmod 8$ that would mean $N \equiv 1 \pmod 8$. But we have seen above that $N \equiv -1 \pmod 8$. This means some (an odd number) of the prime factors must be congruent to $-1 \pmod 8$, and we have just shown how this invalidates the assumption there are only $k$ primes of the form $8k-1$.

For all the possible cases, we have shown the assumption of a finite number of primes of the form $8k-1$ leads to a contradiction. And so there are an infinite number of primes of the form $8k-1$.