Chapter 10

There is an explanation for everything. It is a pity that many of those explanations make no sense.

- Craig Shaw Gardner

Problem 112 If a is a quadratic residue of an odd prime p, then p − a is a quadratic residue if p ≡ 1 (mod 4) and is a nonresidue if p ≡ 3 (mod 4).

Proof: We’ll show that (p − a)^{\frac{p−1}{2}} ≡ 1 (mod p) if p ≡ 1 (mod 4) and that (p − a)^{\frac{p−1}{2}} ≡ −1 (mod p) if p ≡ 3 (mod 4). Then we’ll invoke Euler’s Criterion (problem 110), and we’ll be done.

Consider (p − a)^{\frac{p−1}{2}} . Since

p − a ≡ −a(mod p),

we know that

(p − a)^{\frac{p−1}{2}} ≡ (−a)^{\frac{p−1}{2}} (mod p)
≡ (−1)^{\frac{p−1}{2}} (a)^{\frac{p−1}{2}} .

But a is a quadratic residue of p, so a^{\frac{p−1}{2}} ≡ 1 (mod p). Thus,

(p − a)^{\frac{p−1}{2}} ≡ (−1)^{\frac{p−1}{2}} (mod p).

If p ≡ 1 (mod 4) then p = 4k + 1, for some k. Then,

\frac{p−1}{2} = \frac{4k+1−1}{2}
= 2k,

so

(p − a)^{\frac{p−1}{2}} ≡ (−1)^{\frac{p−1}{2}} (mod p)

≡ (−1)^{\frac{p−1}{2}} = (−1)^{2k} = 1.

Thus, by Euler’s Criterion, p − a is a quadratic residue when p ≡ 1 (mod 4).

If p ≡ 3 (mod 4) then p = 4k + 3, for some k. Then,

\frac{p−1}{2} = \frac{4k+3−1}{2}
= 2k + 1,

so

(p − a)^{\frac{p−1}{2}} ≡ (−1)^{\frac{p−1}{2}} (mod p)
≡ (−1)^{\frac{p−1}{2}}
= (−1)^{2k+1}
= −1.

By Euler’s Criterion, p − a is a quadratic nonresidue when p ≡ 3 (mod 4).

Problem 113 If p = 2^{k} + 1 is prime, then every quadratic nonresidue of p is a primitive root of p.

Proof: We’ll prove this by contrapositive. That is, we’ll prove that if a is not a primitive root of p, then it’s a quadratic residue of p.

Let a be some number which is not a primitive root of p. Then there exists some number, m less than ϕ(p) such that a^{m} ≡ 1 (mod p). Recall that ϕ(p) = p − 1, so m < 2^{k}.

We also know (from problem 93) that m | ϕ(p), so m | 2^{k}. So m = 2^{n} for some n < k. Now, using a bit of algebra and the results of problem 46...

a^{2^{n}} ≡ 1 (mod p)
(a^{2^{n}})^{2^{(k−1)−n}} ≡ 1^{2^{(k−1)−n}}
a^{2^{k−1}} ≡ 1.

But

2^{k−1} = \frac{2^{k}}{2}

= \frac{p − 1}{2}.

Therefore,

a^{2^{k−1}} = a^{\frac{p−1}{2}} ≡ 1 (mod p).

So, by Euler’s Criterion, a is a quadratic residue of p.

Definition Let p be an odd prime and gcd(a, p) = 1. The Legendre Symbol , (a/p), is the function which returns 1 if a is a quadratic residue of p and returns -1 if a is a quadratic nonresidue of p.

Problem 114 Now that we have this handy new definition, let’s figure out what we can do with it... For the following problems p is an odd prime, and a and b are relatively prime to p.

Problem 114a: If a ≡ b (mod p), then (a/p) = (b/p).

Proof: We’ll tackle this with two cases:

Case 1: Suppose (a/p) = 1. Then a is a quadratic residue of p, so, by Euler’s Criterion, a^{\frac{p−1}{2}} ≡ 1 (mod p). But a ≡ b (mod p), so a^{\frac{p−1}{2}} ≡ b^{\frac{p−1}{2}} (mod p). Thus, b^{\frac{p−1}{2}} ≡ 1 (mod p) and by Euler’s Criterion, b is quadratic residue of p. So (b/p) = 1 = (a/p).

Case 2: Suppose (a/p) = −1. Then a is a quadratic nonresidue of p, so, by Euler’s Criterion, a^{\frac{p−1}{2}} ≡ −1 (mod p). But a ≡ b (mod p), so a^{\frac{p−1}{2}} ≡ b^{\frac{p−1}{2}} . Thus, b^{\frac{p−1}{2}} ≡ −1 (mod p) and by Euler’s Criterion, b is quadratic nonresidue of p. So (b/p) = −1 = (a/p).

But (a/p) = ±1, so (a/p) = (b/p).

Problem 114b: (ab/p) = (a/p)(b/p).

Proof: This time, we’ll need three cases:

Case 1: Suppose a and b are both quadratic residues. Then,

a^{\frac{p−1}{2}} ≡ 1 ≡ b^{\frac{p−1}{2}} (mod p)

and

(a/p) = 1 = (b/p).

Now, since both a^{\frac{p−1}{2}} and b^{\frac{p−1}{2}} are equivalent to 1 (mod p),

(ab)^{\frac{p−1}{2}} = a^{\frac{p−1}{2}} b^{\frac{p−1}{2}} ≡ 1 (mod p),

so ab is a quadratic residue of p (by Euler’s Criterion) and

(ab/p) = 1 = (a/p)(b/p).

Case 2: Suppose a and b are both quadratic nonresidues. Then (similarly to Case 1),

a^{\frac{p−1}{2}} ≡ −1 ≡ b^{\frac{p−1}{2}} (mod p)

and

(a/p) = −1 = (b/p).

Now, since both a^{\frac{p−1}{2}} and b^{\frac{p−1}{2}} are equivalent to -1 (mod p),

(ab)^{\frac{p−1}{2}} = a^{\frac{p−1}{2}} b^{\frac{p−1}{2}} ≡ 1 (mod p),

so ab is a quadratic residue of p (by Euler’s Criterion) and

(ab/p) = 1 = (−1)^{2} = (a/p)(b/p).

Case 3: Finally, suppose exactly one of a or b is a quadratic residue. Without loss of generality, let a be the quadratic nonresidue. You know the drill...

a^{\frac{p−1}{2}} ≡ −1 (mod p)
b^{\frac{p−1}{2}} ≡ 1 (mod p)

and

(a/p) = −1,
(b/p) = 1.

Thus,

(ab)^{\frac{p−1}{2}} = a^{\frac{p−1}{2}} b^{\frac{p−1}{2}} ≡ (−1) · 1 = −1 (mod p),

so ab is a quadratic nonresidue of p (by Euler’s Criterion) and

(ab/p) = −1 = (−1) · 1 = (a/p)(b/p).

Having exhausted all the possibilities, we can now conclusively say that (ab/p) = (a/p)(b/p).

Problem 114c: (ab^{2}/p) = (a/p).

Proof: By 114b, we know

(ab^{2}/p) = (a/p)(b^{2}/p)
= (a/p)(b/p)(b/p).

But (b/p) = ±1, so (b/p)^{2} = 1. Thus,

(ab^{2}/p) = (a/p).

Problem 114d (part 1): (1/p) = 1.

Proof: 1^{\frac{p−1}{2}} = 1, so 1^{\frac{p−1}{2}} ≡ 1 (mod p). Therefore, by Euler’s Criterion, 1 is a quadratic residue of p, so (1/p) = 1.

Problem 114d (part 2): (−1/p) = (−1)^{\frac{p−1}{2}} .

Proof: This also follows directly from Euler’s Criterion and the definition of the Legendre symbol. (−1/p) = 1 exactly when -1 is a quadratic residue of p–when (−1)^{\frac{p−1}{2}} = 1, and (−1/p) = −1 exactly when -1 is a quadratic nonresidue of p–when (−1)^{\frac{p−1}{2}} = −1. So (−1/p) = (−1)^{\frac{p−1}{2}} . Note: Looking at the exponent, we can see that −1 is a quadratic residue of p if p is of the form 4k + 1 and is a nonresidue if p is a 4k + 3 prime.

What have we learned from all this? Part (a.) lets us put everything in the mod p universe–we can easily reduce any numbers larger than the modulo with which we’re working. Problem 144b. gives us a strong multiplicativity for the Legendre symbol. (It’s strong because a and b don’t have to be relatively prime.) Part (c.) lets us disregard squares (thus any even powers) when calculating the Legendre symbol.

Problems 115 and 116 If p is an odd prime, then

∑_{a=1}^{p−1}(a/p) = 0.

That is, there are the same number of quadratic residues and nonquadratic residues of p. Moreover, the quadratic residues are congruent modulo p to the even powers of a primitive root r of p. The quadratic nonresidues are congruent modulo p to the odd powers of r.

Proof: Since p is prime, it has a primitive root r (by problem 98). Thus, r^{ϕ(p)} = r^{p−1} ≡ 1 (mod p). Now, all powers of r (less than p) are distinct (see problem 99) and all even powers of r are quadratic residues of p, since r^{2k} = (r^{k})^{2}. So we have at least \frac{p−1}{2} quadratic residues of p. Now we must show that there are no more.

Suppose (in order to get a contradiction) that some odd power of r is also a quadratic residue of p. Then,

r^{2k+1} ≡ x^{2} (mod p)

for some x. We know (from problem 93) that x^{p−1} ≡ 1 (mod p). Now, a bit of algebra:

1 ≡ x^{p−1} (mod p)
≡ (x^{2})^{\frac{p−1}{2}}
≡ (r^{2k+1})^{\frac{p−1}{2}} = r^{(p−1)k}r^{\frac{p−1}{2}} .

But r^{p−1} ≡ 1 (mod p). So,

r^{(p−1)k}r^{\frac{p−1}{2}} ≡ 1^{k}r^{\frac{p−1}{2}} (mod p).

Therefore,

r^{\frac{p−1}{2}} ≡ 1 (mod p).

But then r can’t be a primitive root (since \frac{p−1}{2} is smaller than p−1). Contradiction! So we can conclude that no odd powers of r are quadratic residues and that there are the same number of quadratic residues as nonresidues.

Gauss’s Lemma (Problem 117) Let p be an odd prime and gcd(a, p) = 1. If n denotes the number of integers in the set

S = \{a, 2a, 3a, ..., \frac{p − 1}{2} · a\}

whose remainders upon division by p exceed \frac{p}{2}, then (a/p) = (−1)^{n}.

Proof: Hold on. First we’re going to have to create a few sets.

S′ = {s (mod p)| s ∈ S}
S′′ = \{s′′ | s′′ = s′ if s′ ≤ \frac{p}{2} and s′′ = −(p − s′) if s′ > \frac{p}{2}\}

So S′ is just S, evaluated modulo p. S′′ is created by taking each element in S′ which is larger than \frac{p}{2} and rewriting it so that its absolute value is less than \frac{p}{2}.

Now we’ll show that everything in S′ is distinct. Assume not: there exist two distinct elements in S which are equivalent modulo p.

k_{1}a ≡ k_{2}a (mod p)

Since gcd(a, p) = 1, by the cancellation law (problem 50), we know

k_{1} ≡ k_{2} (mod p).

But all the k_{q}’s are less than \frac{p−1}{2} (by the construction of S), so that means

k_{1} = k_{2}.

Thus, the elements in S are not distinct, and we have a contradiction. So everything in S′ is distinct.

Next, let’s show that the absolute value of everything in S′′ is distinct. Suppose not:

| − (p − k_{1}a)| ≡ k_{2}a (mod p).

Then,

p − k_{1}a ≡ k_{2}a
−k_{1}a ≡ k_{2}a,

and

p | −k_{1}a − k_{2}a.

But gcd(p, a) = 1, so

p | −k_{1} − k_{2},

which means

−k_{1} ≡ k_{2} (mod p).

For that to be true, though, either k_{1} or k_{2} would have to be greater than \frac{p}{2}. (Recall that \frac{p}{2} isn’t an integer.) But all the k_{q}’s are less than \frac{p−1}{2} (by the construction of S). So the absolute values of the elements of S′′ are distinct.

There are clearly \frac{p−1}{2} elements in S, so there are also that many elements in S′ and S′′ (since everything in those sets is distinct.) By its construction, all the elements of S′′ have absolute values less than \frac{p}{2}. But it has \frac{p−1}{2} elements, so

∏_{s′′∈S′′} s′′ = ±\frac{p − 1}{2}!.

That is, all the integers from 1 to \frac{p−1}{2} appear exactly once in S′′, though each might be positive or negative (think Pigeonhole Principle and see the example below).

Now, an element in S′′ will be negative if and only if its source element (in S) was larger than \frac{p}{2} (mod p). So there are n negative elements in S′′. (Remember the definition of n, above.) So,

∏_{s′′∈S′′} s′′ = (−1)^{n} \frac{p − 1}{2}!.

When changing elements from S to S′ to S′′ we haven’t changed the value of any element, modulo p. So the product of the elements in S must be equal (mod p) to the product of the elements in S′′:

∏_{s′′∈S′′} s′′ ≡ ∏_{s∈S} s (mod p).

Thus (subsituting from above, and writing out ∏_{s∈S} s),

(−1)^{n} \frac{p − 1}{2}! ≡ \frac{p − 1}{2}!a^{\frac{p−1}{2}} (mod p)

(−1)^{n} ≡ a^{\frac{p−1}{2}} .

But (a/p) is given by evaluating a^{\frac{p−1}{2}} (mod p) (Euler’s Criterion), so

(a/p) = (−1)^{n}.

Phew. We’re done. Would you like to see an example?

Example 10.1 We’ll use Gauss’s Lemma to evaluate (3/11). We know 5^{2} ≡ 3 (mod 11), so we know the answer should be 1...

S = {1 · 3, 2 · 3, 3 · 3, 4 · 3, 5 · 3}
= {3, 6, 9, 12, 15}

S′ = {3, 6, 9, 1, 4}
S′′ = {3, −5, −2, 1, 4}

There are two negative elements in S′′–i.e., there are two elements of S whose remainders upon division by p exceed \frac{p}{2}. So n = 2 and (−1)^{n} = 1 = (a/p). Gauss’s Lemma worked! (Note that the elements of S′′ are, disregarding the negative signs, the integers from 1 to \frac{p−1}{2}.)

Problem 118 If p is an odd prime, then (2/p) = 1 if and only if p ≡ ±1 (mod 8).

Proof: We’ll prove this by cases, relying on Gauss’s Lemma. Here, a = 2, so

S = \{2, 4, 6, ..., \frac{p − 1}{2} · 2\}

Case 1: Suppose p ≡ −1 (mod 8), that is, p = 8k − 1. Then \frac{p}{2} = 4k − \frac{1}{2}. Which elements of S will exceed 4k − \frac{1}{2} (mod p) ? 4k, 4k + 2, ..., 8k − 2. How many are there? The number of even numbers between 8k − 2 and 4k, inclusive, is \frac{(8k−2)−4k}{2} + 1 = 2k. So n is even, and, by Gauss’s Lemma, (2/p) = 1.

Case 2: Suppose p ≡ 1 (mod 8), that is, p = 8k + 1. Then \frac{p}{2} = 4k + \frac{1}{2}. Which elements of S will exceed this (mod p)? 4k + 2, 4k + 4, ..., 8k. That makes a total of \frac{8k−(4k+2)}{2} + 1 = 2k elements. So n is even, and, by Gauss’s Lemma, (2/p) = 1.

Case 3: Suppose p ≡ 3 (mod 8), that is, p = 8k + 3. Then \frac{p}{2} = 4k + \frac{3}{2}. Which elements of S will exceed this (mod p)? 4k+2, 4k+4, ..., 8k+2. That makes a total of \frac{(8k+2)−(4k+2)}{2} + 1 = 2k + 1. So n is odd, and, by Gauss’s Lemma, (2/p) = −1.

Case 4: Suppose p ≡ 5 (mod 8), that is, p = 8k + 5. Then \frac{p}{2} = 4k + \frac{5}{2}. Which elements of S will exceed this (mod p)? 4k+4, 4k+6, ..., 8k+4. That makes a total of \frac{(8k+4)−(4k+4)}{2} + 1 = 2k + 1. So n is odd, and, by Gauss’s Lemma, (2/p) = −1.

Problem 119 If p ≡ 7 (mod 8), then p | 2^{\frac{p−1}{2}} − 1.

Proof: Since p ≡ 7 (mod 8), by problem 118 we know that (2/p) = 1. By Euler’s Criterion, then,

2^{\frac{p−1}{2}} ≡ 1 (mod p)

So

p | 2^{\frac{p−1}{2}} − 1.

Example 10.2 So how can you use problem 119? Ever wonder if 2^{83} −1 is prime? Calculator can’t handle that many digits?

Proof that 167 | 2^{83} − 1: 167 = 20 · 8 + 7, so 167 ≡ 7 (mod 8). Therefore, by problem 119, 167 | 2^{\frac{167−1}{2}} − 1. Thus, 167 | 2^{83} − 1. So it’s not prime. Sorry.

The same trick works for 2^{p} − 1, when, for example, p = 11, 23, 131, 179, 181, 251.

Data for Problem 120 Here’s some data Beth collected on the relationship between (p/q) and (q/p):

Here are some (p, q) such that (p/q) = (q/p) = 1:

(5, 11), (5, 19), (17, 19), (3, 13)

And some (p, q) such that (p/q) = (q/p) = −1:

(3, 5), (5, 7), (7, 13), (11, 13), (7, 17), (5, 13), (5, 17), (5, 23), (11, 17)

Finally, here are some (p, q) such that (p/q) ≠ (q/p):

(3, 7), (7, 11), (3, 11), (7, 19), (11, 19), (3, 23)

Notice that everything in the third list is of the form 4k + 3. At least one of each pair in the first two sets is of the form 4k + 1...

Day 27, November 9, notes scribed by Drew Schroeder.

Preliminaries to the proof of the law of quadratic reciprocity.

Remember that last time we observed a strange relationship between the existence of solutions to the pair of quadratic congruences x^{2} ≡ p (mod q) and x^{2} ≡ q (mod p) and the form of the primes p and q. It appeared from the data we had that whenever either p or q was of the form 4k + 1 then the two congruences either both had a solution or both did not, it was only when both p and q were of the form 4k + 3 that we ever observed one congruence having a solution and the other not. Turns out that Gauss (and Euler and Legendre) noticed the same thing. Gauss produced the first proof in his Disquistiones Arithmeticae of 1801, the publication of this book is considered by many to be the beginning of modern number theory. During his lifetime Gauss returned again and again to the law of quadratic reciprocity, he called it “The Gem of Arithmetic” and he produced 7 different proofs. The first one cost him a year of effort.

To begin our proof, recall Gauss’s Lemma and the beginning of its proof. Gauss’s Lemma Let p be an odd prime and gcd(a, p) = 1. If n denotes the number of integers in the set

S = \{a, 2a, 3a, ..., \frac{p − 1}{2} · a\}

whose remainders upon division by p exceed \frac{p}{2}, then (a/p) = (−1)^{n}.

In the course of proving this Beth constructed the set S′ by reducing each of the ka modulo p. Let’s denote those elements of S′ which are less than p/2 by r_{i} (note there are n such) and those greater by s_{j}, say j = 1 … m. Beth also observed that the set S” whose elements are the r_{i} and p − s_{j} are exactly the numbers 1 through p − 1/2. An example might help, suppose a = 5 and p = 13.

S = {5, 10, 15, 20, 25, 30}
S′ = {5, 10, 2, 7, 12, 4}
S” = {5, 3, 2, 6, 1, 4}

We are guaranteed that S” was going to contain 1 through 6, as Beth showed on Monday. Notice that n = 3 (look at S′) so (a|p) = −1, and 5 is not a quadratic residue of 13.

We need one more lemma before attacking the proof of quadratic recipocity.

Lemma 10.1 If p is an odd prime and a an odd integer with gcd(a, p) = 1 and

b = ∑_{k=1}^{p−1/2}⌊\frac{ka}{p}⌋, then (a|p) = (−1)^{b}.

This looks a lot like Gauss’s Lemma, what it says is that the n from Gauss and this bizarre looking quantity b have the same parity, thus one could use either to compute (a|p). In the above example, a = 5, p = 13, notice that

b = ⌊5/13⌋ + ⌊10/13⌋ + ⌊15/13⌋ + ⌊20/13⌋ + ⌊25/13⌋ + ⌊30/13⌋

= 0 + 0 + 1 + 1 + 1 + 2 = 5

So, 5 is not a quadratic residue of 13.

Proof: Consider the set S from our proof of Gauss’s Lemma, for each ka in S use the division algorithm to write

ka = q_{k}p + t_{k} 1 ≤ t_{k} ≤ p − 1

The t_{k} are precisely the r_{i} and s_{j} of our Gauss’s Lemma proof. Observe that if you divide both sides of this equation by p you get that ka is q_{k} plus something smaller than 1. That is, ⌊ka/p⌋ = q_{k}. So, we can write

∑_{k=1}^{p−1/2} ka = ∑_{k=1}^{p−1/2}⌊ka/p⌋p + ∑_{i=1}^{l} r_{i} + ∑_{j=1}^{n} s_{j}

As noted above and in the proof of Gauss’s Lemma,

∑_{k=1}^{p−1/2} k = ∑_{i=1}^{l} r_{i} + ∑_{j=1}^{n}(p − s_{j}) = pn + ∑_{i=1}^{l} r_{i} − ∑_{j=1}^{n} s_{j}

Subtracting the last two equalities from one another gives,

(a − 1) ∑_{k=1}^{p−1/2} k = p ( ∑_{k=1}^{p−1/2}⌊ka/p⌋ − n) + 2 ∑_{j=1}^{n} s_{j}

Noting that a and p are odd and reducing the above equality into a congruence modulo 2 gives,

0 ≡ ∑_{k=1}^{p−1/2}⌊ka/p⌋ − n (mod 2)

That is, n and b have the same parity. Ta Da!

bf Problem 120 (The Law of Quadratic Reciprocity) If p and q are distinct odd primes, then the quadratic congruences x^{2} ≡ p (mod q), x^{2} ≡ q (mod p) are both solvable or both unsolvable if either of p or q is of the form 4k + 1. If both p and q are of the form 4k + 3, then exactly one of the congruences is solvable.

Note that one could write this quite compactly,

(p|q)(q|p) = (−1)^{\frac{p−1}{2} \frac{q−1}{2}}

This is what we will prove, the argument is a variation of one of Gauss’s proofs, due in this form to his student Eisenstein.

Proof: Consider the rectangle, R, in the plane with vertices at (0, 0), (p/2, 0), (0, q/2), (p/2, q/2). There are exactly (p − 1)/2 · (q − 1)/2 points in the interior of this rectangle with both coordinates integers (these are called lattice points). Also, consider the line joining (0, 0) to (p/2, q/2), this line is y = q/px. It is easy to this line contains no lattice points. If it did contain a point, say (a, b), then its slope would be b/a, but its slope is q/p which is already in lowest terms since q and p are prime. So, that can’t happen.

For each integer k < p − 1/2 count the number of lattice points with x-coordinate k below the line. Since the point (k, kq/p) is on the line, there are ⌊kq/p⌋ such points for each k. Therefore the total number of points below the line is,

∑_{k=1}^{p−1/2}⌊kq/p⌋

Call this quantity c. Similarly, looking at the picture sidewise, we get that the number of points above the line, call it d, is,

∑_{k=1}^{q−1/2}⌊kp/q⌋

Note that there are, therefore, c + d lattice points in R, but of course we already know that there are (p − 1)/2 · (q − 1)/2 lattice points in R. The previous lemma says that (q|p) = (−1)^{c} and (p|q) = (−1)^{d}, so

(q|p)(p|q) = (−1)^{c+d} = (−1)^{\frac{p−1}{2} \frac{q−1}{2}}

And, we’re done.

That was brilliant. What good is it? You can use it compute Legendre symbols, if you also remember that these symbols are multiplicative.

(104|179) = (8|179)(13|179) = (2|179)(4|179)(13|179)

Recall that (2|p) = 1 iff p = 8k ± 1, 179 ≡ 3 (mod 8), so

(104|179) = −(13|179)

But, 13 is a 4k + 1 so we use quadratic reciprocity to flip the latter symbol over and then reduce modulo 13,

(104|179) = −(179|13) = −(10|13) = −(2|13)(5|13)

OK, 13 ≡ 5 (mod 8), so (2|13) = −1, also 5 is a 4k + 1 guy,

(104|179) = (5|13) = (13|3) = (3|5) = (5|3) = (2|3) = −1

How long do you think it would have taken to verify that no number when squared and divided by 179 leaves a remainder of 104? (Hint, I think a looong time.)

We interrupt our progress to back up and finally settle the Hill-Schroeder conjecture for Mersenne primes. Theorem 10.1 Suppose p = 2m + 1 is an odd prime and q = 2p + 1 is also prime, if p|2^{m} − 1, then q|2^{p} − 1 if m is odd, and q|2^{p} + 1 if m is even.

Proof: So we have p = 2m + 1 is prime and 2^{m} ≡ 1 (mod p). Thus ϕ(p) = 2m, and therefore 2 must be a quadratic residue of p. That is, (2|p) = 1. Notice that,

(2|p)(q|p) = (2|p)(4m + 3|p) = (8m + 6|2m + 1) = (2|p) = 1

This implies that (q|p) = 1.

Note also that

(2|q)(p|q) = (2|4m + 3)(2m + 1|4m + 3) = (−1|4m + 3) = −1

Since m is odd both p and q are of the form 4k + 3 and then, by quadratic reciprocity, (p|q) = −(q|p) = −1. This, taken together with the last equality gives (2|q) = 1 and threfore, by Euler’s Criterion,

2^{p} ≡ 1 (mod q)

An exactly analogous argument works, mutatis mutandis, for the case m is even.

Problem 121 If each of m and n are the sum of two squares, then so also is mn.

Proof:

m = a^{2} + b^{2} n = c^{2} + d^{2}

mn = (a^{2} + b^{2})(c^{2} + d^{2}) = (ac)^{2} + (ad)^{2} + (bc)^{2} + (bd)^{2} = (ad − bc)^{2} + (ac + bd)^{2}

Problem 122 No prime of the form 4k + 3 is the sum of two squares.

Proof: We’ve seen this before, an even number squared is of the form 4k, an odd number squared gives you a 4k + 1. Adding two things of these forms can only give you remainders 0, 1, or 2 modulo 4.

Problem 123 Let p be a prime and gcd(a, p)=1. Then the congruence ax ≡ y (mod p) admits a solution x_{0}, y_{0} satisfying, 0 < |x_{0}| < \sqrt{p} and 0 < |y_{0}| < \sqrt{p}.

This will be useful in the proof of 124.

Proof: Let r = ⌊\sqrt{p}⌋ and consider the set T = \{ac − d | 0 ≤ c, d ≤ r\}. Since there are r + 1 choices for each of c and d, there are (r + 1)^{2} elements of T. Since (r + 1)^{2} > p it must be true that there exist a pair of things in T which are congruent modulo p, by the pigeonhole principle. That is, there exist distinct pairs (c_{0}, d_{0}) and (c_{1}, d_{1}) such that,

ac_{0} − d_{0} ≡ ac_{1} − d_{1} (mod p)

Or, rearranging,

a(c_{0} − c_{1}) ≡ (d_{0} − d_{1}) (mod p)

Notice that neither | c_{0} − c_{1} | nor | d_{0} − d_{1} | can exceed \sqrt{p}. Moreover, neither of these differences can be zero. Suppose that d_{0} − d_{1} = 0, since a and p are relatively prime that forces c_{0} − c_{1} = 0. The other possibility is even easier. Thus, let x_{0} = c_{0} − c_{1} and y_{0} = d_{0} − d_{1}.

Problem 124 An odd prime is expressible as a sum of two squares if and only if it is of the form 4k + 1. Moreover, any such representation is unique.

Proof: Suppose p is a prime of the form 4k + 1, then there exists a such that a^{2} ≡ −1 (mod p), by Euler’s Criterion. Now use the above lemma to find x and y both between 0 and \sqrt{p} such that ax ≡ y (mod p). Squaring both sides and rearranging gives x^{2} + y^{2} ≡ 0 (mod p). So, x^{2} + y^{2} = kp, where k > 0. But, we know that x and y are each less than \sqrt{p}, so their squares are each less than p. So, the sum of their squares is less than 2p, that is k = 1! The other direction is already done, see problem 122.

Problem 125 A number n is representable as the sum of two squares if and only if each of its prime factors of the form 4k + 3 occurs to an even power.

Proof: If each prime factor of n of the form 4k + 3 occurs to an even power, then n = k^{2}m where m has only prime factors of the form 4k + 1. So, by the above we can write m = a^{2} + b^{2}, and therefore, n = k^{2}m = (ka)^{2} + (kb)^{2}.

The other direction is harder, we begin by proving a lemma.

Lemma 10.2 If p is a prime of the form 4k + 3 and p|a^{2} + b^{2}, then p|a and p|b.

Proof: Suppose a ≢ 0 (mod p), then there exists x such that ax ≡ 1 (mod p), from our theory of linear congruences. Since p divides a^{2} + b^{2} we can write

(ax)^{2} + (bx)^{2} ≡ 0 (mod p)
⟶ p|(bx)^{2} + 1

But this very bad! It says that -1 is a quadratic residue mudulo this 4k + 3 prime, that never happens. So, p must divide a and therefore, it must divide b. Ta Da!

Of course this immediately implies if p|a^{2} + b^{2}, then p^{2}|a^{2} + b^{2}.

Now to finish the proof of problem 125 we need to show that if a p = 4k + 3 a prime divides n and n = a^{2} + b^{2}, then that prime factor occurs an even number of times. Suppose that p^{2k+1}|a^{2} + b^{2} for k > 0, we’ll show that, in fact, p^{2k+2}|a^{2} + b^{2}. Since p|a^{2} + b^{2}, by the lemma p|a and p|b. Therefore we can factor a p^{2} out of both sides of p^{2k+1}|a^{2} + b^{2}, i.e., p^{2k−1}|(a/p)^{2} + (b/p)^{2}. As long as 2k − 1 > 1 you can repeat and get p^{2k−3}|(a/p^{2})^{2} + (b/p^{2})^{2}. Do this k times and you get down to p|(a/p^{k})^{2} + (b/p^{k})^{2}. But by the lemma this implies that p^{2}|(a/p^{k})^{2} + (b/p^{k})^{2}, clearing fractions gives p^{2k+2}|a^{2} + b^{2}.