Exercise (7.3).14

Prove Proposition (4.24) of Chapter 4.

We remind ourselves of Prove Proposition (4.24).

Let $q$ be an odd prime. Any prime factor $p$ of $M_q = 2^q− 1$ is of the form $p \equiv \pm 1 \pmod 8$.

We start with prime $p$ being a factor of $2^q-1$. This means

$$ 2^q \equiv 1 \pmod p $$

Since $q$ is an odd prime, we can write it as $p=2n+1$, for some positive integer $n$.

$$ 2^{2n+1}  \equiv 1 \pmod p $$

Multiplying through by 2 is valid since $p \not \mid 2$, 

$$ 2^{2n+1}\times 2 \equiv 2^{2n+2} \equiv (2^{n+1})^2 \equiv 2 \pmod p $$

This means 2 must be a quadratic residue of $p$. By the result we proved in Exercise (7.3).3(i) we conclude that $p \equiv \pm1 \pmod 8$.

And so if prime $p$ is a factor of $M_q=2^q-1$ then $p \equiv \pm1 \pmod 8$.

Exercise (7.3).13

Prove Proposition (4.19) of Chapter 4.

We remind ourselves of Proposition (4.19).

Let $p= 2n + 1$ be prime. Then we have the following:

(a) If $p \equiv \pm 1 \pmod 8$ then $p \mid  (2^n-1)$.

(b) If $p \equiv \pm 3 \pmod 8$ then $p \mid  (2^n+1)$.

(a) By Proposition (7.15) we have that if $p \equiv \pm 1 \pmod 8$ where $p$ is an odd prime, then $(\frac{2}{p}) = 1$.

By Euler's Criterion we have $2^{\frac{p-1}{2}} \equiv 1 \pmod p$. Substituing $p=2n+1$ gives us the desired result

$$ p \mid 2^n - 1 $$

(b) By Proposition (7.15) we have that if $p \equiv \pm 3 \pmod 8$ where $p$ is an odd prime, then $(\frac{2}{p}) = -1$.

By Euler's Criterion we have $2^{\frac{p-1}{2}} \equiv -1 \pmod p$. Substituing $p=2n+1$ gives us the desired result

$$ p \mid 2^n + 1 $$

Exercise (7.3).12

(a) Show that $x^2 \equiv 3 \pmod {F_n}$ where the Fermat prime $F_n = 2^{2^n} + 1$ has no solutions for $n = 1, 2, 3$ and $4$.

(b) Prove that for any positive integer $n$

$$ F_n = 2^{2^n} + 1 \equiv 5 \pmod {12}$$

(a) The following table calculates $F_n \pmod {12}$ for $n=1,2,3,4$.

n	F_n	F_n mod 12
1	5	5
2	17	5
3	257	5
4	65537	5

We proved the following result in the previous exercise. For odd prime $p$, we have

$$ (\frac{3}{p}) = \begin{cases} 1 & \text{ if } p \equiv 1 \text{ or } 11 \pmod {12}  \\ -1 & \text{ if } p \equiv 5 \text{ or } 7 \pmod {12}  \end{cases} $$

Since $F_n \pmod{12}=5$ in all cases, this result tells us $(\frac{3}{F_n})=-1$, and so by Euler's Criterion 3 is not a quadratic residue of $F_n$. That is,  $x^2 \equiv 3 \pmod {F_n}$ has no solutions.

(b) We prove the result by induction.

Let $S(n)$ be the statement

$$ S(n) \quad := \quad F_n = 2^{2^n} + 1 \equiv 5 \pmod {12} $$

We need to prove a base case $S(1)$, and the inductive step $S(n) \implies S(n+1)$.

Base Case $S(1)$

We need to show that $F_1 \equiv 5 \pmod {12}$

$$ F_1 = 2^{2^1} + 1 = 4+1 = 5 \equiv 5 \pmod {12} $$

The base case is proven.

Inductive Step $S(n) \implies S(n+1)$

We assume $S(n)$ as the induction hypothesis. We aim to show $S(n+1)$.

$$ F(n+1) = 2^{2^{n+1}} +1 = 2^{2^n \times 2} + 1 =  2^{2^n +2^n} + 1 =(2^{2^n})\times (2^{2^n}) + 1 \equiv \underbrace{(4)\times(4)}_{S(n) \text{ applied twice}}+1 \equiv 17 \equiv 5 \pmod {12}   $$

And so we have shown $S(n) \implies S(n+1)$.

By showing the base case and the inductive step, by induction we have proven that for all natural numbers $n$

$$ F_n = 2^{2^n} + 1 \equiv 5 \pmod {12}$$

Exercise (7.3).11

(i) Prove that for prime $p > 3$ we have

$$ (\frac{3}{p}) = \begin{cases} 1 & \text{ if } p \equiv 1 \text{ or } 11 \pmod {12}  \\ -1 & \text{ if } p \equiv 5 \text{ or } 7 \pmod {12}  \end{cases} $$

(ii) Show that 3 is a quadratic residue of $p \iff p \equiv 1, 11 \pmod {12}$.

(iii) Factorise the following integers:

(a) $62^2 -3 = 3841$

(b) $104^2 -3 = 10813$

(c) $200^2 - 3 = 39997$

(d) $364^2 -3 = 132493$

(e) $568^2 -3 = 322621$

(i) We start with Gauss's Lemma that

$$ (\frac{3}{p}) = (-1)^g $$

where $g$ is the number of residues of $p$ greater than $\frac{p-1}{2}$ in the set $\{3\cdot 1, \;3\cdot 2, \;3 \cdot 3, \;\ldots , \; 3 \cdot \frac{p-1}{2}\}$.

The value of $g$ is the number of integers from the set $1,2, 3, \ldots, p-1$ which map to a value greater than $\frac{p-1}{2}$ up to and including $p-1$. This value of $g$ is

$$ g = \lfloor \frac{p-1}{3} \rfloor - \lfloor \frac{p-1}{2 \cdot 3} \rfloor $$

We write odd prime $p$ as $p=12k + t$ for some integer $k$ and where $t$ is only one of $1, 5, 7, 11$. Other values of $t$ contradict $p$ being prime. We consider each case for values of $t$. 

For $p=12k +1$ we have

$$ \begin{align} g & = \lfloor \frac{12k+1-1}{3} \rfloor - \lfloor \frac{12k+1-1}{2 \cdot 3} \rfloor \\ \\ & = \lfloor 4k \rfloor - \lfloor 2k \rfloor \\ \\ & = 2k  \end{align} $$

Because $g$ is even, we have

$$ (\frac{3}{p}) = (-1)^g = 1 $$

For $p=12k +5$ we have

$$ \begin{align} g & = \lfloor \frac{12k+5-1}{3} \rfloor - \lfloor \frac{12k+5-1}{2 \cdot 3} \rfloor \\ \\ & = \lfloor 4k + \frac{4}{3} \rfloor - \lfloor 2k + \frac{4}{6} \rfloor \\ \\ & = (4k+1) - (2k) \\ \\  &= 2k+1 \end{align} $$

Because $g$ is odd, we have

$$ (\frac{3}{p}) = (-1)^g = -1 $$

For $p=12k +7$ we have

$$ \begin{align} g & = \lfloor \frac{12k+7-1}{3} \rfloor - \lfloor \frac{12k+7-1}{2 \cdot 3} \rfloor \\ \\ & = \lfloor 4k + \frac{6}{3} \rfloor - \lfloor 2k + \frac{6}{6} \rfloor \\ \\ & = (4k+2) - (2k+1) \\ \\  &= 2k+1 \end{align} $$

Because $g$ is odd, we have

$$ (\frac{3}{p}) = (-1)^g = -1 $$

For $p=12k +11$ we have

$$ \begin{align} g & = \lfloor \frac{12k+11-1}{3} \rfloor - \lfloor \frac{12k+11-1}{2 \cdot 3} \rfloor \\ \\ & = \lfloor 4k + \frac{10}{3} \rfloor - \lfloor 2k + \frac{10}{6} \rfloor \\ \\ & = (4k+3) - (2k+1) \\ \\  &= 2k+2 = 2(k+1) \end{align} $$

Because $g$ is even, we have

$$ (\frac{3}{p}) = (-1)^g = 1 $$

We have consider all the cases for $p$ and they all support the desired conclusion that for odd prime $p$

$$ (\frac{3}{p}) = \begin{cases} 1 & \text{ if } p \equiv 1 \text{ or } 11 \pmod {12}  \\ -1 & \text{ if } p \equiv 5 \text{ or } 7 \pmod {12}  \end{cases} $$

(ii) To show that 3 is a quadratic residue of $p \iff p \equiv 1, 11 \pmod {12}$, we need to show both

• if $p \equiv 1,11 \pmod {12}$ then 3 is a quadratic residue of $p$
• if $3$ is a quadratic residue of $p$ then $p \equiv 1,11 \pmod {12}$

($\impliedby$)

The result we proved in part (i) immediately gives us that if $p \equiv 1,11 \pmod {12}$ then 3 is a quadratic residue of $p$, because by Euler's Criterion $(\frac{3}{p})=1$ means 3 is a quadratic residue of $p$.

($\implies$)

We will prove the logically equivalent contrapositive: if $p \not \equiv 1, 11 \pmod {12}$ then $3$ is not a quadratic residue of $p$. 

 If $p \not \equiv 1, 11 \pmod {12}$ then it must be the case that $p \not \equiv 5, 7 \pmod {12}$ because any other congruent values for $p$ would contradict $p$ being prime. The result from (i) tells us that $(\frac{3}{p})=-1$, and so by Euler's Criterion 3 is not a quadratic residue of $p$. 

We have proved the contrapositive, which is equivalent to $3$ is a quadratic residue of $p$ then $p \equiv 1,11 \pmod {12}$.

By proving both directions of the bi-conditional statement, we have proven the statement that 3 is a quadratic residue of $p \iff p \equiv 1, 11 \pmod {12}$.

(iii) The factorisation exercises require a list of the first odd primes which are congruent to 1 or 11 modulo 12. These are

$$ 11, 13, 23, 37, 47, 59, 61, 71, 73, 83, 97, 107, 109, 131, 157, 167, 179, 181, 191, 193, 227, 229, 239, 241 $$

(a) $62^2 \equiv 3 \pmod p$ means $p$ is congruent to 1 or 11 modulo 12 by the result proved above in part (i). Such a $p$ is a factor of $62^2-3$ because $62^2 -3 \equiv 0 \pmod p$.

Trying factor 23 gives

$ 3841 = 23 \times 167 $

(b) Trying factor 11 gives

$ 10813 = 11 \times 983 $

Trying factors up to $\lfloor \sqrt{983} \rfloor = 31$ shows 983 is prime.

(c) Trying factors 23, 37 and 47 gives

$39997 = 23 \times 37  \times 47$

(d) Trying factor 47 gives

$ 132493 = 47 \times 2819$

Trying factors up to $\lfloor \sqrt{2819} \rfloor = 53$ shows 2819 is prime.

(e) Trying factors 13, 23 and 83 gives.

$ 322621 = 13^2 \times 23 \times 83$

Exercise (7.3).10

Determine the following Legendre symbols by using Gauss’s Lemma:

(a) $(\frac{3}{13})$

(b) $(\frac{3}{17})$

(c) $(\frac{3}{19})$

(d) $(\frac{3}{23})$

(a) The following table shows the calculation of $3n \pmod {13}$ for $1 \le n \le \frac{13-1}{2}$, which values larger than $\frac{13-1}{2}$ shown as the smallest negative residues. 

n	3n mod 13	3n mod 13
1	3	3
2	6	6
3	9	-4
4	12	-1
5	2	2
6	5	5

There are 2 negative such residues. By Gauss' Lemma

$$ (\frac{3}{13}) = (-1)^2 = 1$$

And so by Euler's Criterion 3 is a quadratic residue of odd prime 13.

(b) The following table shows the calculation of $3n \pmod {13}$ for $1 \le n \le \frac{17-1}{2}$, which values larger than $\frac{17-1}{2}$ shown as the smallest negative residues. 

n	3n mod 17	3n mod 17
1	3	3
2	6	6
3	9	-8
4	12	-5
5	15	-2
6	1	1
7	4	4
8	7	7

There are 3 negative such residues. By Gauss' Lemma

$$ (\frac{3}{17}) = (-1)^3 = -1$$

And so by Euler's Criterion 3 is a quadratic non-residue of odd prime 17.

(c) The following table shows the calculation of $3n \pmod {19}$ for $1 \le n \le \frac{19-1}{2}$, which values larger than $\frac{19-1}{2}$ shown as the smallest negative residues. 

n	3n mod 19	3n mod 19
1	3	3
2	6	6
3	9	9
4	12	-7
5	15	-4
6	18	-1
7	2	2
8	5	5
9	8	8

There are 3 negative such residues. By Gauss' Lemma

$$ (\frac{3}{19}) = (-1)^3 = -1$$

And so by Euler's Criterion 3 is a quadratic non-residue of odd prime 19.

(d) The following table shows the calculation of $3n \pmod {23}$ for $1 \le n \le \frac{23-1}{2}$, which values larger than $\frac{23-1}{2}$ shown as the smallest negative residues. 

n	3n mod 23	3n mod 23
1	3	3
2	6	6
3	9	9
4	12	-11
5	15	-8
6	18	-5
7	21	-2
8	1	1
9	4	4
10	7	7
11	10	10

There are 4 negative such residues. By Gauss' Lemma

$$ (\frac{3}{23}) = (-1)^4 = 1$$

And so by Euler's Criterion 3 is a quadratic residue of odd prime 23.

Exercise (7.3).9

(i) Prove that for odd prime $p$ we have

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

(ii) Prove that if the odd prime $p$ satisfies

$$ p \mid  (x^2 + 2) $$

then $p ≡ 1, 3 \pmod 8$.

(iii) Factorise the following integers (−2 replaced by +2 of question 3):

(a) $18^2 + 2 = 326$

(b) $23^2 + 2 = 531$

(c) $51^2 + 2 = 2603$

(d) $27^2 + 2 = 727$

(e) $105^2 + 2 = 11027$

(f) $47^2 + 2 = 2211$

(g) $195^2 + 2 = 38027$

(i) We start with Proposition (7.15):

Let $p$ be an odd prime then

$$ (\frac{2}{p}) = \begin{cases} 1 & \text{ if } p \equiv \pm 1 \pmod 8  \\ -1 & \text{ if } p \equiv \pm 3 \pmod 8  \end{cases} $$

We note that

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

The following table summarises Propositions (7.11) and Propositions (7.15), with Proposition (7.11) recast to modulo 8.

p mod 8	(-1/p)	(2/p)	(-1/p)*(2/p)
1	1	1	1
3	-1	-1	1
-3	1	-1	-1
-1	-1	1	-1

Since every possible case for $p$ is considered, we can read off the final column as the desired conclusion, that for odd prime $p$

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

(ii) We start with $p \mid  (x^2 + 2)$ which is equivalent to

$$ x^2  \equiv -2 \pmod p $$

We have seen from part (i) that -2 is a quadratic residue of odd prime $p$ if $p \equiv 1 \pmod 8$ or $p\equiv 3 \pmod 8$. This is the desired conclusion.

(iii) The factorisation exercises require odd primes which are congruent to 1 or 3 modulo 8. The first of these are

$$ 3, 11, 17, 19, 41, 43, 59, 67, 73, 83, 89, 97, 107, 113, 131, 137, 139, 163, 179 $$

(a) We consider $18^2 \equiv -2 \pmod p$, where prime $p \equiv 1,3 \pmod 8$, Such a prime divides $18^2+2=326$. 

We immediately see 2 is a factor. Trying the above primes up to $\lfloor \sqrt{163}\rfloor=12$ tells us that 163 is prime, and so

$326 = 2 \times 163$

(b) Trying factor 59 gives us

$ 531 = 3^2 \times 59 $

(c) Trying factor 19 gives us

$ 2603 = 19 \times 137 $

Trying the above primes up to $\lfloor \sqrt{137}\rfloor=11$ tells us that 137 is prime.

(d) Trying factors 17 and 43 gives us

$ 731 = 17 \times 43 $ 

(e) Trying the above primes up to $\lfloor \sqrt{11027}\rfloor=105$ tells us that 11027 is prime.

(f) trying factors 11 and 67 gives us

$ 2211 = 3 \times 11 \times 67 $

(g) Trying factor 11 gives us

$ 38027 = 11 \times 3457$

Trying the above primes up to $\lfloor \sqrt{3457}\rfloor=58$ tells us that 3457 is prime.

Exercise (7.3).8

Determine the least positive residues $x$ in the following cases (1987 is a prime):

(a) $25^{995} \equiv x \pmod {1987}$

(b) $26^{995} \equiv x \pmod {1987}$

(a) Since $5^2=25$, then 25 is a quadratic residue of 1987. By Euler's Criterion this means

$$ 25^{\frac{1987-1}{2}} \equiv 25^{993} \equiv 1 \pmod {1987} $$

Multiplying through by $25^2=625$ gives

$$ 25^{995} \equiv 625 \pmod {1987} $$

And so the least positive residue $x$ in $25^{995} \equiv x \pmod {1987}$ is $x=625$.

(b) We test whether 26 is a quadratic residue of 1987.

$$ \begin{align} (\frac{26}{1987}) & = (\frac{2}{1987}) \times (\frac{13}{1987}) \\ \\ & = (-1) \times (\frac{13}{1987}) \\ \\ & =  (-1) \times (\frac{1987}{13})  \\ \\ & =  (-1) \times (\frac{11}{13})  \\ \\ & =  (-1) \times (\frac{13}{11}) \\ \\ & =  (-1) \times (\frac{2}{11}) \\ \\ & =  (-1) \times (-1)  = 1 \end{align} $$

This means 26 is a quadratic residue of 1987. And so by Euler's Criterion

$$ 26^{\frac{1987-1}{2}} \equiv 26^{993} \equiv 1 \pmod {1987} $$

Multiplying through by $26^2=676$ we have

$$ 26^{995} \equiv 676 \pmod {1987} $$

And so the least positive residue $x$ in $26^{995} \equiv x \pmod {1987}$ is $x=676$.

Exercise (7.3).7

Determine the least positive residue $x$ in $2^{271} \equiv x \pmod {541}$ where 541 is prime.

We use Proposition (7.15) and that prime $541 \equiv -3 \pmod 8$ to conclude that

$$ (\frac{2}{p}) = - 1 $$

By Euler's Criterion, this mean

$$ 2^{\frac{541-1}{2}} \equiv 2^{270} \equiv -1 \pmod {541} $$

Multiplying by 2 we have

$$ 2^{271} \equiv -2 \equiv x \pmod {541} $$

This gives us $x = 539$ as the least positive reside $x$ in $2^{271} \equiv x \pmod {541}$.

Exercise (7.3).6

Show that prime 1223 satisfies

$$1223 \mid (2^{611}− 1)$$

Hint: Use Euler’s Criterion.

We remind ourselves of Euler's Criterion (7.5).

Let $p$ be an odd prime such that $p \not \mid a$. Then $a$ is a quadratic residue of $p$ if and only if $a^{\frac{p-1}{2}} \equiv 1 \pmod p$.

We will use Proposition (7.15):

Let $p$ be an odd prime then

$$ (\frac{2}{p}) = \begin{cases} 1 & \text{ if } p \equiv \pm 1 \pmod 8  \\ -1 & \text{ if } p \equiv \pm 3 \pmod 8  \end{cases} $$

Since the prime $1223 \equiv -1 \pmod 8$, we have $(\frac{2}{p})=1$, by Proposition (7.15).

This means, by Euler's Criterion (7.5)

$$ 2^{\frac{1223-1}{2}} \equiv 2^{611} \equiv 1 \pmod {1223} $$

Re-arranging gives us the desired result

$$ 1223 \mid (2^{611}-1)  $$

Exercise (7.3).5

Prove Corollary (7.18).

Let's remind ourselves of Corollary (7.18).

Let $p$ be an odd prime then

$$ (\frac{2}{p}) = (-1)^{\frac{p^2-1}{8}} $$

We start with Proposition (7.15).

Let $p$ be an odd prime then

$$ (\frac{2}{p}) = \begin{cases} 1 & \text{ if } p \equiv \pm 1 \pmod 8  \\ -1 & \text{ if } p \equiv \pm 3 \pmod 8  \end{cases} $$

We consider both cases for $p$, that is, $p \equiv \pm 1 \pmod 8$ and $p \equiv \pm 3 \pmod 8$.

Case $p \equiv \pm 1 \pmod 8$

Here $p = 8k \pm 1$ for some integer $k$.  This means

$$ \frac{p^2 -1}{8} = \frac{8^2k^2 + 1 -1 \pm 16k}{8} = 8k^2 \pm 2k = 2(4k^2 \pm k) $$

In this case $\frac{p^2 -1}{8} = 2(4k^2 \pm k)$ is even, and so $(-1)^{\frac{p^2 -1}{8}} = 1$.  And so this case satisfies Corollary (7.18).

Case $p \equiv \pm 3 \pmod 8$

Here $p = 8k \pm 3$ for some integer $k$.  This means

$$ \frac{p^2 -1}{8} = \frac{8^2k^2 + 9 -1 \pm 48k}{8} = 8k^2 + 1 \pm 6k = 2(4k^2 \pm 3k) + 1$$

In this case $\frac{p^2 -1}{8} = 2(4k^2 \pm 3k) + 1$ is odd, and so $(-1)^{\frac{p^2 -1}{8}} = -1$.  And so this case satisfies Corollary (7.18).

For both possible cases of $p$ we have shown the Corollary holds, and so we have proven Corollary (7.18).

Exercise (7.3).4

Prove Lemma (7.13).

Let's remind ourselves of Lemma (7.13).

Let $p$ be an odd prime and $a$ be an integer such that $p \not \mid a$. Then

$$ a, 2a, 3a, ⋯ , (\frac{p-1}{2})a \not \equiv 0 \pmod p $$

Consider the number $ka$ where $k$ is an integer such that $1 \le k \le (\frac{p-1}{2})$.

Since $p$ does not divide $a$, then we consider whether $p$ divides $k$. We can see that $p$ does not divide $k$ because $k < p$.

And so $p$ does not divide $ka$. Equivalently, $ka \not \equiv 0 \pmod p$. 

That is,

$$ a, 2a, 3a, ⋯ , (\frac{p-1}{2})a \not \equiv 0 \pmod p $$

Exercise (7.3).3

(i) Prove that 2 is a quadratic residue of prime $p$ if and only if $p \equiv \pm 1 \pmod 8$.

(ii) Factorise the following integers:

(a) $18^2 -2 = 322$

(b) $23^2 -2 = 527$

(c) $51^2 -2 = 2599$

(d) $27^2 -2 = 727$

(e) $105^2 -2 = 11023$

(f) $47^2 -2 = 2207$

(g) $195^2 -2 = 38023$

(i) We need to prove to implications:

• 2 is a quadratic residue of $p$ $\impliedby$ $p \equiv \pm 1 \pmod 8$
• 2 is a quadratic residue of $p$ $\implies$ $p \equiv \pm 1 \pmod 8$

($\impliedby$)

We use Proposition (7.15). 

Let $p$ be an odd prime. Then

$$ (\frac{2}{p}) =  \begin{cases} 1 & \text{ if } p ≡ ±1 \pmod 8 \\ −1 & \text{ if } p ≡ ±3 \pmod 8 \end{cases}$$

This tells us that if $p \equiv \pm 1 \pmod 8$ then 2 is a quadratic residue of $p$.

($\implies$)

We contrapositive of the statement we want to prove is

$$p \not \equiv \pm 1 \pmod 8 \implies 2 \text{ is a not a quadratic residue of } p$$

Since $p$ is odd, and $p \not \equiv \pm 1 \pmod 8$, then the only remaining possibilities for $p$ are $p \equiv \pm 3 \pmod 8$. 

By Proposition (7.15) we conclude that 2 is not a quadratic residue of $p$.

By proving the contrapositive, we have proved the intended statement that 2 is a quadratic residue of $p$ $\implies$ $p \equiv \pm 1 \pmod 8$.

Proving both implications means have have proved the statement that

$$ 2 \text{ is a quadratic residue of prime } p \iff p \equiv \pm 1 \pmod 8 $$

(ii) In the following exercises we will use primes $p$ such that $p \equiv \pm 1 \pmod 8$. The first of these are

$$ 7, 17, 23, 31, 41, 47, 71, 73, 79, 89, 97 $$

(a) We consider $18^2 \equiv 2 \pmod p$, where prime $p \equiv \pm 1 \pmod 8$. Such a prime $p$ divides $18^2-2$.

Trying factor 7 gives us

$ 322 = 2 \times 7 \times 23 $

(b) Trying factor 17 gives us

$ 527 = 17 \times 31 $

(c) Trying factor 23 gives us

$ 2599 = 23 \times 113 $

(d) Trying factors up to $\lfloor \sqrt{727}\rfloor = 26$ tells us 727 is prime.

(e) Trying factor 73 gives us

$ 11023 = 73 \times 151 $

(f) Trying factors up to $\lfloor \sqrt{2207} \rfloor = 46$ tells us 2207 is prime.

(g) Trying factor 47 gives us 

$ 38023 = 47 \times 809 $

Trying factors up to $\lfloor \sqrt{809} \rfloor = 28$ tells us 809 is prime and so can't be decomposed further.

Exercise (7.3).2

Determine whether the following integers are quadratic residues of the prime 131:

(a) 14

(b) 12

(c) 15

(d) 65

(a) We want to calculate the Legendre symbol

$$ \begin{align} (\frac{14}{131}) & = (\frac{2}{131}) \times (\frac{7}{131}) \\ \\ & = (-1) \times (\frac{7}{131})  \tag{Proposition 7.15} \\ \\ & = -1 \times (\frac{131}{7}) = -1 \times -(\frac{5}{7}) \tag{Corollary 7.17} \\ \\& = (\frac{7}{5}) = (\frac{2}{5}) \tag{Corollary 7.17} \\ \\ & = -1 \tag{Proposition 7.15} \end{align}$$

And so 14 is not a quadratic residue of prime 131.

(b) We want to calculate the Legendre symbol

$$ \begin{align} (\frac{12}{131}) & =  (\frac{2^2}{131}) \times (\frac{3}{131}) = 1 \times (\frac{3}{131}) \tag{$2^2$ is a quadratic residue} \\ \\ & = - (\frac{131}{3}) = -(\frac{2}{3}) \tag{Corollary 7.17} \\ \\ & = -(-1) = 1 \tag{Proposition 7.15}\end{align}$$

And so 12 is a quadratic residue of prime 131.

(c) We want to calculate the Legendre symbol

$$ \begin{align} (\frac{15}{131}) & = (\frac{3}{131}) \times (\frac{5}{131}) = (1) \times  (\frac{5}{131}) \tag{result from (b)} \\ \\ & = (\frac{131}{5}) = (\frac{1}{5}) = 1 \tag{Corollary 7.17} \end{align}$$

And so 15 is a quadratic residue of prime 131.

(d) We want to calculate the Legendre symbol

$$ \begin{align} (\frac{65}{131}) & = (\frac{5}{131}) \times (\frac{13}{131}) = (1) \times  (\frac{13}{131}) \tag{result from (c)} \\ \\ & = (\frac{131}{13}) = (\frac{1}{13}) = 1 \tag{Corollary 7.17} \end{align}$$

And so 65 is a quadratic residue prime 131.

Exercise (7.3).1

Evaluate the following Legendre symbols $(\frac{a}{p})$ where $p$ is prime in each case:

(a) $(\frac{12}{ 71} )$

(b) $(\frac{15}{ 101} )$

(c) $(\frac{28 }{163} )$

(d) $(\frac{75 }{ 541} )$

(e) $(\frac{360 }{1223} )$

(f) $(\frac{115 }{1987} )$

(g) $(\frac{700 }{3571} )$

(h) $(\frac{703}{ 4409} )$

[Hint: 703= 19 × 37.]

These exercises are practice in using the new proposition and lemmas introduced in section 7.3.

(a) We proceed as follows

$$ \begin{align} (\frac{12}{71}) & = (\frac{2^2 \times 3}{71}) \\ \\ & = (\frac{3}{71}) \tag{$2^2$ is a quadratic residue} \\ \\ & = -(\frac{71}{3}) \tag{Corollary 7.17}\\ \\ & = -(\frac{2}{3}) \tag{$71\equiv 2 \pmod 3$} \\ \\ & = -(-1) = 1 \tag{Proposition 7.15} \end{align} $$

(b) We proceed as follows

$$ \begin{align} (\frac{15}{101}) & = (\frac{3 \times 5}{101}) \\ \\ & =  (\frac{3}{101}) \times  (\frac{5}{101}) \\ \\ & =  (\frac{101}{3}) \times  (\frac{101}{5}) \tag{Corollary 7.17} \\ \\  & =  (\frac{2}{3}) \times  (\frac{1}{5}) \\ \\ & = -1 \times 1 = -1 \tag{Proposition 7.15 and 7.11} \end{align} $$

(c) We proceed as follows

$$ \begin{align} (\frac{28}{163}) & = (\frac{2^2 \times 7}{163}) \\ \\ &=  (\frac{7}{163}) \tag{$2^2$ is a quadratic residue} \\ \\ & = - (\frac{163}{7}) \tag{Corollary 7.17} \\ \\ & = -(\frac{2}{7}) \\ \\ & =  -1 \tag{Corollary 7.15} \end{align} $$

(d) We proceed as follows

$$ \begin{align} (\frac{75}{541}) & = (\frac{5^2 \times 3}{541}) \\ \\ & = (\frac{3}{541}) \tag{$5^2$ is a quadratic residue} \\ \\ & = (\frac{541}{3}) \tag{Corollary 7.17} \\ \\ & =  (\frac{1}{3}) = 1   \end{align} $$

(e) We proceed as follows

$$ \begin{align} (\frac{360}{1223}) & = (\frac{2^2 \times 2 \times 3^2 \times 5}{1223}) \\ \\  & = (\frac{2}{1223}) \times (\frac{5}{1223})  \tag{$2^2$ and $3^2$ are quadratic residues} \\ \\ & =  (1) \times (\frac{5}{1223}) \tag{Corollary 7.15} \\ \\ & = (\frac{1223}{5})  \tag{Corollary 7.17} \\ \\ & =   (\frac{3}{5}) = (\frac{5}{3}) \tag{Corollary 7.17} \\ \\ & = (\frac{2}{3}) = -1 \tag{Proposition 7.15} \end{align} $$

(f) We proceed as follows

$$ \begin{align} (\frac{115}{1987}) & =  (\frac{5}{1987}) \times (\frac{23}{1987}) \\ \\  & =  (\frac{1987}{5}) \times -(\frac{1987}{23}) \tag{Corollary 7.17} \\ \\ & =  (\frac{2}{5}) \times -(\frac{3^2}{23}) \\ \\ & = (-1) \times -(1) =  1 \tag{Proposition 7.15 and $3^2$ is QR} \end{align} $$

(g) We proceed as follows

$$ \begin{align} (\frac{700}{3571}) & = (\frac{2^2 \times 5^2 \times 7}{3571}) = (\frac{7}{3571}) \tag{$2^2$ and $5^2$ are QR} \\ \\ & = - (\frac{3571}{7}) = -(\frac{1}{7}) = -1  \tag{Corollary 7.17} \end{align} $$

(h) We proceed as follows

$$ \begin{align} (\frac{703}{4409}) & =  (\frac{19}{4409}) \times  (\frac{37}{4409}) \\ \\ &= (\frac{4409}{19}) \times  (\frac{4409}{37}) = (\frac{1}{19}) \times  (\frac{6}{37}) = (1) \times  (\frac{6}{37}) \tag{Corollary 7.17} \\ \\ & = (\frac{2}{37}) \times (\frac{3}{37}) =  (-1) \times (\frac{3}{37}) \tag{Proposition 7.15} \\ \\ & = -(\frac{37}{3}) = -(\frac{1}{3}) = -1 \tag{Corollary 7.17} \end{align} $$

Exercise (7.2).14

Assuming 2 is a primitive root of the prime 101, find the square roots of $14 \pmod {101}$.

As per the previous exercise, even powers of the primitive root 2 are congruent to quadratic residues modulo 101.

The following table shows the first even powers of 2.

n	2^n mod 101
2	4
4	16
6	64
8	54
10	14

We can read off that

$$ 2^{10} \equiv (2^5)^2 \equiv (\pm 32)^2 \equiv 14 \pmod {101} $$

And so the square roots of 14 modulo 101 are $32 \pmod {101}$ and $69 \pmod {101}$.

Exercise (7.2).13

Determine the quadratic residues of the prime $p = 17$ by using the primitive root 3 modulo 17. Hence, or

otherwise, find the square roots of 13 (mod 17).

Since 3 is a primitive root of 17, then even powers of 3 are congruent to quadratic resides of 17. The following table of calculations shows $3^n \pmod {17}$ where $n$ is even.

n	3^n mod 17
2	9
4	13
6	15
8	16
10	8
12	4
14	2
16	1

We can read off that

$$ 3^4 \equiv 9^2 \equiv (\pm 9)^2\equiv 13 \pmod {17} $$

And so the square roots of 13 modulo 17 are $8 \pmod {17}$ and $9 \pmod {17}$.

Exercise (7.2).12

Let $r$ be a primitive root of an odd prime $p$.

(a) Prove that $r^{2n}$ is a quadratic residue of $p$.

(b) Prove that $r^{2n+1}$ is a quadratic non-residue of $p$.

(c) By using the primitive root $r$ show that there are $\frac{p− 1}{2}$ quadratic residues and $\frac{p− 1}{2}$ quadratic non-residues of $p$.

(a) We can see immediately that $r^n$ is a solution to $x \equiv r^{2n} \pmod p$, and so $r^{2n}$ is a quadratic residue of $p$.

(b) By the multiplicative property of the Legendre symbol, we need to show that $r$ is a quadratic non-residue, since $r^{2n}$ is a quadratic residue.

For the purpose of contradiction, we'll assume $r$ is a quadratic residue, and so by Euler's Criterion

$$ r^{\frac{p-1}{2}} \equiv 1 \pmod p $$

This is a contradiction because $r$ is a primitive root, and the smallest index $j$ such that $r^j \equiv 1 \pmod p$ must be $r=p-1$.

And so any primitive root is not a quadratic residue.

(c) We know from a previous exercise that the set

$$ S = \{ r^0, r^1, r^3, \ldots, r^{p-1} \} $$

is congruent to the set

$$ T = \{ 1, 2, 3, \ldots, (p-1) \} $$

We also know that even powers of the primitive root $r$ are quadratic residues, and that odd powers are quadratic non-residues.

There are $\frac{p-1}{2}$ elements of the set $S$ which have even powers. This means there are $\frac{p-1}{2}$ elements of the set $T$ which are quadratic residues.

By a symmetric argument there are $\frac{p-1}{2}$ elements of the set $T$ are quadratic non-residues.

And so we have shown there are $\frac{p− 1}{2}$ quadratic residues and $\frac{p− 1}{2}$ quadratic non-residues of $p$.

Exercise (7.2).11

Let $p$ be an odd prime. Prove that

$$ \sum_{a=1}^{p-1} (\frac{a}{p}) = 0 $$

where $(\frac{a}{p})$ is the Legendre symbol.

We use Proposition (7.4). 

Let $p$ be an odd prime. Then there are exactly $\frac{p- 1}{2}$ quadratic residues and $\frac{p- 1}{2}$ quadratic non-residues of $p$.

This means that of the $p-1$ residues of $p$, there are $\frac{p- 1}{2}$ quadratic residues and $\frac{p- 1}{2}$ quadratic non-residues. The Legendre symbol of the quadratic residues has value 1, and has value -1 for the non-residues.

And so

$$ \sum_{a=1}^{p-1} (\frac{a}{p}) = (\frac{p-1}{2} \times 1) + (\frac{p-1}{2} \times -1) = 0$$

Exeercise (7.2).10

Prove that the Legendre symbol

$$ (\frac{ab^2}{p}) = (\frac{a}{p}) $$

given that $\gcd (a, p) = \gcd (b, p) = 1$.

We use Proposition (7.9), noting that $p \not \mid a$, and $p \not \mid b$.

$$ \begin{align} (\frac{ab^2}{p}) & = (\frac{a}{p}) \times (\frac{b^2}{p}) \\ \\ & = (\frac{a}{p}) \times 1 \\ \\ & = (\frac{a}{p}) \end{align}$$

Exercise (7.2).9

(i) Show that if $p \mid (x^2 + 1)$ then

$$ p \equiv 1 \pmod 4 $$

(ii) Prove that there are infinitely many primes of the form $4n + 1$ without using Dirichlet’s Theorem.

(We have already proven this using Dirichlet’s Theorem—see Exercises 2.3, question 1 (a).)

We assume $p$ is an odd prime.

(i) $p \mid (x^2 +1)$ means

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

Euler's Criterion tell us that for this congruence to have solutions

$$ (-1)^{\frac{p-1}{2}} \equiv 1 \pmod p $$

There are two cases for $p$, which are $p=4k+1$ and $p=4k+3$, for some integer $k$. 

If $p=4k+1$, we have

$$ (-1)^{2k} \equiv 1 \pmod p $$

If $p=4k+3$, we have

$$ (-1)^{2k+1} \equiv 1 \pmod p $$

This is a contradiction, and so $p=3 \pmod 4$ is not possible, leaving only $p \equiv 1 \pmod 4$.

(ii) We take inspiration from Euclid's proof of infinite primes from around 300BC!

For the purpose of contradiction, we assume there are a finite number $n$ of primes of the form $4k+1$ where $k$ in a natural number, $p_1, p_2, \ldots, p_n$. 

We next consider the following constructed number

$$ N = (2 \times p_1 \times p_2 \times \ldots \times p_n)^2 + 1 = 4(p_1 \times p_2 \times \ldots \times p_n)^2 + 1 $$

We have two cases for $N$, it is either prime or it is not.

If $N$ is prime, then we have constructed a prime of the form $4k+1$, that is larger than any of the $p_1, p_2, \ldots, p_n$ primes. This is a contradiction of the assumption there are only $n$ primes of the form $4k+1$.

If $N$ is composite, then it has a prime factor, which can denote $p$. That is, $p \mid N$. Since $N$ is of the form $x^2+1$, the result from (i) tells is $p$ is of the form $4k+1$. But this $p$ is not any of the $p_1, p_2, \ldots, p_n$, and so we've found a another prime of the form $4k+1$. This contradicts the assumption there are only $n$ primes of the form $4k+1$.

Both cases contradict the assumption there are a finite number of primes of the form $4k+1$. And so there are an infinite number of primes of the form $4k+1$.

Exercise (7.2).8

Prove that the Legendre symbol

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

where $p$ is an odd prime.

We will use Proposition (7.8). 

Let $p$ be an odd prime and $a$ be an integer such that $p \not \mid a$. Then

$$(\frac{a}{p} ) \equiv a^{\frac{p−1}{2}} \pmod p$$

Setting $a=-1$ gives us the desired result.

$$(\frac{-1}{p} ) \equiv (-1)^{\frac{p−1}{2}} \pmod p$$

Exercise (7.2).7

Show that if $p \equiv 1 \pmod 4$ then $a^{\frac{p-1}{2}}$ where $\gcd(a, p) = 1$ is a quadratic residue of $p$.

We first note that $\gcd(a,p)=1$ means that $p \not \mid a$.

We need to show there exists an $x$ such that $x^2 \equiv a^{\frac{p-1}{2}} \pmod p$, where $p=4k + 1$ for some integer $k$.

Consider $x \equiv a^{\frac{p-1}{4}}$,

$$ x^2 \equiv a^{\frac{p-1}{2}}$$

We need to confirm that $a^{\frac{p-1}{4}}$ is an integer before we conclude it is a square root of $a^{\frac{p-1}{2}}$.

$$ a^{\frac{p-1}{4}}= a^{\frac{4k+1 -1}{4}} = a^{k} $$

Since both $a$ and $k$ are integers, so is $a^k=a^{\frac{p-1}{4}}$.

And so  $a^{\frac{p-1}{2}}$ is a quadratic residue of $p$ where $p \equiv 1 \pmod 4$.

Exercise (7.2).6

Let $a = p_1^{k_1} \times p_2^{k_2} \times \ldots \times p_n^{k_n}$ be the prime decomposition of $a$. Let $p$ be prime such that $p \not \mid a$. Prove that

$$ (\frac{a}{p}) = (\frac{p_1}{p})^{k_1} \times (\frac{p_2}{p})^{k_2} \times \ldots \times (\frac{p_n}{p})^{k_n} $$

where $(\frac{m}{p})$ is the Legendre symbol.

We proceed as follows

$$ \begin{align} (\frac{a}{p}) & = (\frac{p_1^{k_1} \times p_2^{k_2} \times \ldots \times p_n^{k_n}}{p}) \\ \\  &= (\frac{p_1^{k_1}}{p}) \times (\frac{p_2^{k_2}}{p}) \times \ldots \times (\frac{p_n^{k_n}}{p}) \\ \\ &= \biggl (\underbrace{(\frac{p_1}{p}) \times (\frac{p_1}{p}) \ldots (\frac{p_1}{p})}_{k_1} \biggr ) \times \biggl ( \underbrace{(\frac{p_2}{p}) \times (\frac{p_2}{p}) \ldots (\frac{p_2}{p})}_{k_2} \biggr )  \times \ldots \times \biggl (\underbrace{(\frac{p_1}{p}) \times (\frac{p_n}{p}) \ldots (\frac{p_n}{p})}_{k_n} \biggr ) \\ \\ &= (\frac{p_1}{p})^{k_1} \times (\frac{p_2}{p})^{k_2} \times \ldots \times (\frac{p_n}{p})^{k_n}   \end{align} $$

The second and third steps use the result from the previous exercise.

Exercise (7.2).5

Let $p$ be an odd prime and $a_1, a_2, a_3, \ldots , a_n$ be integers such that $p$ does not divide any of these integers. Prove that

$$ (\frac{a_1}{p}) \times (\frac{a_2}{p}) \times \ldots \times (\frac{a_n}{p}) = (\frac{a_1 \times a_2 \times \ldots \times a_n}{p}) $$

where $(\frac{a}{p})$ is the Legendre symbol.

We will do this by indiction. The statement $P(n)$ is

$$ (\frac{a_1}{p}) \times (\frac{a_2}{p}) \times \ldots \times (\frac{a_n}{p}) = (\frac{a_1 \times a_2 \times \ldots \times a_n}{p}) $$

We need to show the base case is true $P(1)$, and the inductive step $P(n) \implies P(n+1)$.

Base Case $P(1)$

The base case $P(1)$ is trivially true

$$ (\frac{a_1}{p}) = (\frac{a_1}{p}) $$

Inductive Step $P(n) \implies P(n+1)$

We assume the induction hypothesis $P(n)$ is true.

We proceed as follows

$$ \begin{align} (\frac{a_1}{p}) \times (\frac{a_2}{p}) \times \ldots \times (\frac{a_n}{p}) \times (\frac{a_{n+1}}{p}) & = \overbrace{\ (\frac{a_1 \times a_2 \times \ldots \times a_n}{p})}^{\text{induction hypothesis}} \times (\frac{a_{n+1}}{p}) \\ \\ & =  (\frac{a_1 \times a_2 \times \ldots \times a_n \times a_{n+1}}{p}) \end{align}$$

The last step uses Proposition (7.9)(c), and uses the fact that $p \not \mid (a_1 \times a_2 \times \ldots \times a_n)$ and $p \not \mid a_{n+1}$. 

And so $P(n) \implies P(n+1)$.

We have shown by induction that 

$$ (\frac{a_1}{p}) \times (\frac{a_2}{p}) \times \ldots \times (\frac{a_n}{p}) = (\frac{a_1 \times a_2 \times \ldots \times a_n}{p}) $$

for natural number $n$, odd prime $p$ which does not divide any of the $a_i$.

Exercise (7.2).4

Show that $a^{2n}$ ($n$ is a natural number) is a quadratic residue of a prime $p$, provided $p \not \mid a$.

We consider

$$ x^2 \equiv a^{2n} \pmod p $$

By proposition (3.14b) we have

$$ x \equiv \pm a^n \pmod p $$

Here $a^n$ is an integer is not divisible by $p$, because $p \not \mid a \implies p \not \mid a^n $.

And so $a^{2n}$ is a quadratic residue of prime $p$.

Exercise (7.2).3

Factorise the following integers:

(a) $18^2 + 1 = 325$

(b) $30^2 + 1 = 901$

(c) $53^2 + 1 = 2810$

(d) $60^2 + 1 = 3601$

(e) $24^2 + 1 = 577$

(f) $104^2 + 1 = 10 817$

(g) $302^2 + 1 = 91 205$

(h) $1014^2 + 1 = 1 028 197$

We use the fact that odd prime factors $p$ of an integer of the form $x^2 +1$ satisfy $p \equiv 1 \pmod 4$. The first of these are

$$ 5 , 13 , 17,  29 , 37 , 41 , 53 , 61 , 73 , 89 , \ldots$$

(a) We try prime factor 5. 

$ 325 = 5^2 \times 13 $

(b) We try factors 13 and 17.

$ 901 = 17 \times 53 $

(c) We try factor 5 which leads to an even number, leaving 281 as prime.

$ 2810 = 5 \times 2 \times 281 $

(d) We try factor 13.

$ 3601 = 13 \times 277 $

(e) Trying all the primes up to $\lfloor \sqrt{577} \rfloor=24$ tells us 577 is prime.

(f) We try factor 29.

$ 10817 = 29 \times 373 $

Trying all the primes up to $ \lfloor \sqrt{373} \rfloor = 19$ tells us 373 is prime.

(g) We try factors 5, 17, 29, 37.

$ 91205 = 5 \times 17 \times 29 \times 37 $

(h) We try factor 109.

$ 1028197 = 109 \times 9433 $

Trying primes up to $ \lfloor \sqrt{9433} \rfloor = 97 $ tells us 9433 is prime.

Exercise (7.2).2

Determine whether the following integers are quadratic residues of 47:

(a) 46

(b) 95

(c) 90

(d) 58

(e) 90 × 58

(a) Using Proposition (7.9) we have

$$ (\frac{46}{47}) = (\frac{-1}{47}) = (-1)^{\frac{47-1}{2}} = (-1)^{23} = -1 $$

By Definition (7.7) of the Legendre Symbol, 46 is not a quadratic residue of 47.

(b) Using Proposition (7.9) we have

$$ (\frac{95}{47}) = (\frac{1}{47}) = 1 $$

And so 95 is a quadratic residue of 47.

(c) Using Proposition (7.9) we have

$$ (\frac{90}{47}) = (\frac{-1 \times 4}{47}) = (\frac{-1}{47}) \times (\frac{2^2}{47}) = -1 \times 1 = -1   $$

And so 90 is not a quadratic residue of 47.

(d) Using Proposition (7.9) we have

$$ (\frac{58}{47}) = (\frac{11}{47}) \equiv (11)^{23} \equiv (11^4)^5 \times 11^3 \equiv (24)^5 \times 15 \equiv 25 \times 15 \equiv -1 \pmod {47}$$

And so 58 is not a quadratic residue of 47.

(e) Using Proposition (7.9) we have

$$ (\frac{90 \times 58}{47}) = (\frac{90}{47})  \times (\frac{58}{47}) = -1 \times -1 = 1$$

And so $90 \times 58$ is a quadratic residue of 47.

Exercise (7.2).1

Show that the following integers are quadratic residues of 31:

(a) 35

(b) 71

(c) 56

(d) 94

(e) 47

Let's remind ourselves of Proposition (7.9). 

Let $p$ be an odd prime and $a, b$ be integers such that $p \not \mid a$ and $p \not \mid b$. We have

(a) If $a \equiv b \pmod p$ then $(\frac{a}{p}) = (\frac{b}{p})$. 

(b) $(\frac{a^2}{p})=1$.

(c) $(\frac{a \times b}{p}) = (\frac{a}{p}) \times (\frac{b}{p})$, multiplicative property.

(a) Using Proposition (7.9)(a) and (b) we have

$$ (\frac{35}{31}) = (\frac{4}{31})= (\frac{2^2}{31}) = 1 $$

And so by Definition (7.7) of a Legendre Symbol, 35 is a quadratic residue of 31.

(b) Similarly

$$ (\frac{71}{31}) = (\frac{9}{31}) = (\frac{3^2}{31}) = 1 $$

And so 71 is a quadratic root of 31.

(c) Similarly

$$ (\frac{56}{31}) = (\frac{25}{31}) = (\frac{5^2}{31}) = 1$$

And so 56 is a quadratic residue of 31.

(d) Similarly

$$ (\frac{94}{31}) = (\frac{1}{31}) = (\frac{1^2}{31})= 1$$

And so 94 is a quadratic residue of 31.

(e) Similarly

$$ (\frac{47}{31}) = (\frac{16}{31}) = (\frac{4^2}{31}) = 1$$

And so 47 is a quadratic residue of 31.

Exercise (7.1).13

Prove that the multiplicative inverse of a quadratic residue of $p$ is also a quadratic residue of $p$.

Euler's Criterion gives us

$$ a^{\frac{p-1}{2}} \equiv 1 \pmod p $$

By definition of multiplicative inverse, we have

$$ a \times a^{-1} \equiv 1 \pmod p $$

Raising this to index $\frac{p-1}{2}$

$$ \begin{align} (a)^{\frac{p-1}{2}} \times (a^{-1})^{\frac{p-1}{2}} & \equiv 1^{\frac{p-1}{2}} \pmod p \\ \\   1 \times (a^{-1})^{\frac{p-1}{2}} & \equiv 1 \pmod p \\ \\ (a^{-1})^{\frac{p-1}{2}} & \equiv 1 \pmod p  \end{align}$$

This is Euler's Criterion that tells us $a^{-1}$ is a quadratic residue of $p$.

Exercise (7.1).12

Prove that if $a$ is a quadratic residue of $p$ where $p \equiv 3 \pmod 4$ then the quadratic congruence

$$ x^2 \equiv a \pmod p $$

has the solutions

$$ x \equiv \pm a^{\frac{p+1}{4}} \pmod p $$

Solve the following quadratic congruences (all moduli are prime):

(a) $x^2 \equiv 3 \pmod {83}$

(b) $x^2 \equiv 2 \pmod {2^{13}-1}$

(c) $x^2 \equiv 5 \pmod {127}$

We're given $a$ is a quadratic residue of prime $p$. By Euler's Criterion we have

$$ a^{\frac{p-1}{2}} \equiv 1 \pmod p$$

We can multiply through by $a$ because $p \not \mid a$, 

$$ a^{\frac{p+1}{2}} \equiv a \equiv x^2 \pmod p$$

And so by proposition (3.14b)

$$ x \equiv \pm a^{\frac{p+1}{4}} \pmod p$$

We need to ensure the index $\frac{p+1}{4}$ is an integer. Since $p \equiv 3 \pmod 4$, then for some integer $k$ we have $p=4k+3$, and so $\frac{p+1}{4} = \frac{4k+4}{4} = k+1$, an integer.

And so $ x^2 \equiv a \pmod p $ has solutions $ x \equiv \pm a^{\frac{p+1}{4}} \pmod p $ for $p \equiv 3 \pmod 4$.

(a) We first check that 3 is a quadratic residue of 83, using Euler's Criterion (7.5).

$$ 3^{\frac{83-1}{2}} \equiv 3^41 \equiv (3^8)^5 \times 3 \equiv 4^5 \times 3 \equiv 1 \pmod {83} $$

So 3 is a quadratic residue of 83.

Because $83 \equiv 3 \pmod 4$, the above result gives us

$$ x \equiv \pm 3^{\frac{83+1}{4}} \equiv \pm 3^21 \equiv \pm 70 $$

That is, $x \equiv 13 \pmod {83}$ and $x \equiv 70 \pmod {83}$.

(b) We first check that 2 is a quadratic residue of $2^{13}-1$, using Euler's Criterion (7.5).

$$ 2 ^ {\frac{2^{13}-1 -1}{2}} \equiv  2 ^ {2^{12}-1} \equiv 2^{4095}  \pmod {2^{13}-1}$$

We note that $2^{13}  \equiv 1 \pmod {2^{13}-1}$ and so 2 is a quadratic residue of $2^{13}-1$

$$ 2^{4095} \equiv (2^{13})^{315} \equiv 1^{315} \equiv 1  \pmod {2^{13}-1}$$

Because $2^{13}-1 \equiv 3 \pmod 4$, the above result gives us

$$ x \equiv \pm 2^{\frac{2^{13}-1+1}{4}} \equiv  \pm 2^{2048} \equiv (2^{13})^157 \times 2^7 \equiv 128  $$

That is, $x \equiv 128 \pmod {2^{13}-1}$ and $x \equiv 8063 \pmod {2^{13}-1}$.

(c) We first check 5 is a quadratic residue of 127, by Euler's Criterion.

$$ 5^{\frac{127-1}{2}} \equiv 5^63 \equiv (5^7)^9 \equiv 20^9 \equiv -1 \pmod {127} $$

This means the congruence has no solutions.

Exercise (7.1).11

Prove the following results for an odd prime $p$:

(a) The product of two quadratic non-residues of $p$ is a quadratic residue of $p$.

(b) The product of a quadratic residue and quadratic non-residue of $p$ is a quadratic non-residue.

(c) The square of a quadratic residue of $p$ is a quadratic residue.

(a) Consider two quadratic non-residues, $a$ and $b$, of odd prime $p$.

By Euler's Criterion (7.5) and Proposition (7.6) we have

$$ a^{\frac{p-1}{2}} \equiv b^{\frac{p-1}{2}} \equiv -1 \pmod p $$

And so, 

$$ (ab)^{\frac{p-1}{2}} \equiv 1 \pmod p $$

By Euler's Criterion (7.5), this tells us the product of two quadratic non-residues is a quadratic residue.

(b) Consider a quadratic residue $a$, and a quadratic non-residue $b$, of odd prime $p$.

By Euler's Criterion (7.5) and Proposition (7.6) we have

$$ \begin{align} a^{\frac{p-1}{2}} & \equiv 1 \pmod p \\ \\  b^{\frac{p-1}{2}} & \equiv -1 \pmod p \end{align}$$

And so,

$$ (ab)^{\frac{p-1}{2}} \equiv -1 \pmod p $$

By Euler's Criterion (7.5), this tells us the product of a quadratic residue and quadratic non-residue of $p$ is a quadratic non-residue.

(c) Consider a quadratic residue $a$ of odd prime $p$.

By Euler's Criterion (7.5) and Proposition (7.6) we have

$$ a^{\frac{p-1}{2}} \equiv 1 \pmod p $$

And so, 

$$ (a^2)^{\frac{p-1}{2}} \equiv 1 \pmod p $$

By Euler's Criterion (7.5), this tells us the square of a quadratic residue of $p$ is a quadratic residue.

Note: I think the author's solution to part (c) is wrong.

Exercise (7.1).10

Prove that if $a$ is a quadratic residue of $p$ then $a$ is not a primitive root of $p$.

If $a$ is a quadratic residue of $p$ then we know $p \not \mid a$, and so by Euler's Criterion, 

$$ a^{\frac{p-1}{2}} \equiv 1 \pmod p $$

This means $a$ is not a primitive root of $p$, because that would require the smallest index $j$ of $a^j \equiv 1 \pmod p$ to be $j=p-1$.

Exercise (7.1).9

Prove Proposition (7.6).

Let's remind ourselves of Proposition (7.6). 

Let $a$ be any integer and $p$ an odd prime, then

$$ a^{\frac{p-1}{2}} \equiv \pm 1 \pmod p $$

provided $p \not \mid a$.

We start with Fermat's Little Theorem (4.1), applicable since $p \not \mid a$,

$$ a^{p-1} \equiv 1 \pmod p $$

Since $p-1$ is even, we have by Proposition (3.14)(b)

$$ a^{\frac{p-1}{2}} \equiv \pm 1 \pmod p $$

Exercise (7.1).8

(i) Show that the quadratic congruence $ax^2 + bx + c \equiv 0 \pmod p$ where $p \not \mid a$ can be written as

$$ y^2 \equiv m \pmod p $$

(ii) Solve the following quadratic congruences, all moduli are prime:

(a) $2x^2 + 2x + 1 ≡ 0 \pmod {29}$

(b) $5x^2 + 9x + 4 ≡ 0 \pmod {101}$

(c) $7x^2 + 9x + 3 ≡ 0 \pmod {41}$

(d) $2x^2 + 20x + 49 ≡ 0 \pmod {61}$

(i) We "complete the square" for the expression $ax^2 + bx + c$. 

$$ ax^2 + bx + c = a \biggl ( x^2 + \frac{bx}{a}  + \frac{b^2}{4a^2} \biggr ) + (c - \frac{b^2}{4a}) = a \biggl ( x + \frac{b}{2a} \biggr ) ^2 + (c - \frac{b^2}{4a}) $$

This suggests we multiply throughout by $4a$

$$ 4a(ax^2 + bx + c) = 2^2a^2 \biggl ( x + \frac{b}{2a} \biggr ) ^2 + (4ac - b^2) =  ( 2ax + b ) ^2 + (4ac - b^2) $$

Going back to the congruence and multiplying by $4a$ gives

$$ \begin{align} ax^2 + bx + c & \equiv 0 \pmod p \\ \\   4a(ax^2 + bx + c) & \equiv 0 \pmod p \tag{*} \\ \\ ( 2ax + b ) ^2 + (4ac - b^2) &  \equiv 0 \pmod p \\ \\ ( 2ax + b ) ^2 & \equiv (b^2 - 4ac) \pmod p  \end{align}$$

So the congruence can be written in the form $y^2 \equiv m \pmod p$, where $y = (2ax + b)$ and $m = (b^2-4ac)$.

Because $p \not \mid a$, multiplying by $4a$ at line (*) does not introduce incorrect solutions to the congruence. That is, we can't conclude that $4a \equiv 0 \pmod p$. Note that this does require $p \ne 2$, not made clear in the exercise.

(ii)

(a) We can rewrite  $2x^2 + 2x + 1 ≡ 0 \pmod {29}$ as

$$ (4x + 2)^2 \equiv 25 \pmod {29} $$

This gives us $(4x+2) \equiv \pm 5 \pmod {29}$, which gives us $4x \equiv 32 \pmod {29}$, and $4x \equiv 80 \pmod {29}$. The solutions for $x$ are $x \equiv 8 \pmod {29}$ and $x \equiv 20 \pmod {29}$.

(b) We can rewrite $5x^2 + 9x + 4 ≡ 0 \pmod {101}$ as

$$ (10x + 9)^2 \equiv 1 \pmod {101} $$

This gives us $(10x + 9) \equiv \pm 1 \pmod {101}$, which gives us $10x \equiv 800 \pmod {101}$, and $10x \equiv 1000 \pmod {101}$.  The solutions for $x$ are $x \equiv 80 \pmod {101}$ and $x \equiv 100 \pmod {101}$.

(c) We can rewrite $7x^2 + 9x + 3 ≡ 0 \pmod {41}$ as

$$ (14x+9)^2 \equiv 38  \pmod {41} $$

Trial and error does not appear to find a value congruent to $38 \pmod {41}$ that is a square, so we use Euler's Criterion to check whether a solution exists.

We have $41 \not \mid 38$, and

$$ 38^{\frac{41-1}{2}} \equiv 38^{20} \equiv (38^2)^10 \equiv 9^10 \equiv 3486784401 \equiv -1 \pmod {41} $$

This means the congruence has no solution.

(d) We can rewrite $2x^2 + 20x + 49 ≡ 0 \pmod {61}$ as

$$ (4x + 20)^2 \equiv 8 \pmod {61} $$

Trial and error does not appear to find a value congruent to $8 \pmod {61}$ that is a square, so we use Euler's Criterion to check whether a solution exists.

We have $61 \not \mid 8$, and

$$ 8^{\frac{61-1}{2}} \equiv 8^{30} \equiv (8^6)^5 \equiv (27)^5 \equiv -1 \pmod {61} $$

This means the congruence has no solution.

Exercise (7.1).7

Prove the following results for the odd prime $p$:

(a) If $a$ is a quadratic residue then $p-a$ is a quadratic residue if and only if $p \equiv 1 \pmod 4$.

(b) If $a$ is a quadratic residue then $p-a$ is a quadratic non-residue if and only if $p \equiv 3 \pmod 4$.

Since $a$ is a quadratic residue, then $p \not \mid a$. That is, there is no integer $k$ such that $pk = a$. 

If we consider $pj = p-a$ for some integer $j$, we have $p(1-j) = a$. This is not possible since there is no integer $k=(1-j)$ such that $pk=a$. And so $p \not \mid p-a$. 

This means we can use Euler's Criterion (7.5) which tells us that $p-a$ is a quadratic residue of $p$ if and only if 

$$ (p-a)^{\frac{p-1}{2}} \equiv (-a)^{\frac{p-1}{2}} \equiv 1 \pmod p $$

We write odd prime $p$ as $p=4x +t$, where $x$ is an integer and $t$ is one of 1 or 3 only. Why? Because $t=0$ or $t=2$ would mean $p$ is even and not an odd prime.

If $t=1$, that is $p \equiv 1 \pmod 4$, then $p-a$ is a quadratic residue of $p$ if and only if 

$$ (-a)^{2x} \equiv 1 \pmod p $$

Since $a$ is a quadratic residue, Euler's Criterion tells us that $a^{2x} \equiv 1 \pmod p$. Multiplying by $(-1)^{2x} = 1$ gives the desired $(-a)^{2x} \equiv 1 \pmod p$.

If $t=3$, that is $p \equiv 3 \pmod p$, then $p-a$ is a quadratic residue of $p$ if and only if 

$$ (-a)^{2x+1} \equiv 1 \pmod p $$

Since $a$ is a quadratic residue, Euler's Criterion tells us that $a^{2x+1} \equiv 1 \pmod p$. Multiplying by $(-1)^{2x+1} = -1$ gives $(-a)^{2x+1} \equiv -1 \pmod p $. This means the requirement for $p-a$ to be a quadratic residue is not met.

We have concluded that if $a$ is a quadratic residue of odd prime $p$, then

(a) $p-a$ is a quadratic residue if and only if $p \equiv 1 \pmod 4$.

(b) $p-a$ is a quadratic non-residue if and only if $p \equiv 3 \pmod 4$.

Exercise (7.1).6

Prove that $-1$ is a quadratic residue of an odd prime $p$ if and only if $p \equiv 1 \pmod 4$.

Let's remind ourselves of Euler’s Criterion (7.5). 

Let $p$ be an odd prime such that $p \not \mid a$. Then $a$ is a quadratic residue of $p$ if and only if $a^{\frac{p−1}{2}} \equiv 1 \pmod p$.

We write the odd prime $p$ as $p=4k + t$ where $t$ can only be one of 1 or 3, and $k$ is some integer. 

Since $p \not \mid -1$, Euler's Criterion then tells us that $-1$ is a quadratic residue of $p$ if and only if 

$$ (-1)^{\frac{p−1}{2}} \equiv (-1)^{\frac{4k + t −1}{2}} \equiv 1 \pmod p $$

If $t=3$, that is $p \equiv 3 \pmod 4$, then

$$ (-1)^{\frac{4k + t −1}{2}} \equiv (-1)^{\frac{4k + 2}{2}} \equiv (-1)^{2k + 1} \equiv -1 \not \equiv 1 \pmod p$$

If $t=1$, that is $p \equiv 1 \pmod 4$, then

$$ (-1)^{\frac{4k + t −1}{2}} \equiv (-1)^{\frac{4k + 0}{2}} \equiv (-1)^{2k} \equiv 1 \pmod p$$

So $-1$ is a quadratic residue of $p$ if and only if $p \equiv 1 \pmod 4$ means $-1$ is a quadratic residue of $p$.

Exercise (7.1).5

Solve the following quadratic congruences:

(a) $x^2 + 2x + 2 \equiv 0 \pmod {23}$

(b) $x^2 + 4x + 2 \equiv 0 \pmod {23}$

(c) $x^2 + 6x + 5 \equiv 0 \pmod {23}$

(a) We rewrite the expression by "completing the square".

 $$ x^2 + 2x + 2 \equiv (x+1)^2 + 1 \equiv 0 \pmod {23} $$

So we need to solve

 $$ (x+1)^2  \equiv 22 \pmod {23} $$

We first use Euler's Criterion (7.5) to test whether 22 is a quadratic residue of 23.

Since $23 \not \mid 22$ and $22^{\frac{23-1}{2}} \equiv (-1)^{11} \equiv  -1 \pmod {23}$ and so 22 does not have a square root modulo 23.

(b) We rewrite the expression by "completing the square".

 $$ x^2 + 4x + 2 \equiv (x+2)^2 - 2 \equiv 0 \pmod {23} $$

So we need to solve

 $$ (x+2)^2  \equiv 2 \pmod {23} $$

We first use Euler's Criterion (7.5) to test whether 2 is a quadratic residue of 23.

Since $23 \not \mid 2$ and $2^{\frac{23-1}{2}} \equiv (2)^{11} \equiv 2048 \equiv 1 \pmod {23}$ and so 2 has a square root modulo 23.

By Proposition (7.3) $(x+2)^2 \equiv 2 \pmod {23}$ has 2 solutions.

The following calculations shows that $(x+2)\equiv 5 \pmod{23}$ is a solution to $(x+2)^2 \equiv 2 \pmod{23}$.

x+2	(x+2)^2 mod 23
1	1
2	4
3	9
4	16
5	2

We can use Proposition (3.14b) to identify the second solution as $(x+2) \equiv -5 \equiv 18 \pmod {23}$.

So the solutions to the quadratic congruence are $x \equiv 3 \pmod {23}$ and $x \equiv 16 \pmod {23}$.

(c) We rewrite the expression by "completing the square".

 $$ x^2 + 6x + 5 \equiv (x+3)^2 -4  \equiv 0 \pmod {23} $$

So we need to solve

 $$ (x+3)^2  \equiv 4 \pmod {23} $$

We first use Euler's Criterion (7.5) to test whether 4 is a quadratic residue of 23.

Since $23 \not \mid 4$ and $4^{\frac{23-1}{2}} \equiv (4)^{11} \equiv 4194304 \equiv 1 \pmod {23}$ and so 2 has a square root modulo 23.

By Proposition (7.3) $(x+3)^2 \equiv 4 \pmod {23}$ has 2 solutions.

By insprection $(x+3) \equiv 2 \pmod {23}$ is a solution to $(x+3)^2 \equiv 4 \pmod {23}$. 

Proposition (3.14b) tells us the second solution is $(x+3) \equiv -2 \equiv 21 \pmod {23}$.

So the solutions to the quadratic congruence are $x \equiv 22 \pmod {23}$ and $x \equiv 18 \pmod {23}$.

Exercise (7.1).4

Determine the square root of the following:

(a) $2 \pmod {17}$

(b) $16 \pmod {17}$

(c) $5 \pmod {17}$

(a) We first use Euler's Criterion (7.5) to test whether 2 is a quadratic residue of 17.

Since $17 \not \mid 2$ and $2^{\frac{17-1}{2}} \equiv 2^8 \equiv 1 \pmod {17}$ and so 2 does have a square root modulo 17.

By Proposition (7.3) $x^2 \equiv 2 \pmod {17}$ has 2 solutions.

The following calculations tell us that $x \equiv 6 \pmod {17}$ is a solution to $x^2 \equiv 2 \pmod {17}$.

x	x^2 mod 17
1	1
2	4
3	9
4	16
5	8
6	2

We can use Proposition (3.14b) to identify the second solution as $x \equiv -6 \equiv 11 \pmod {17}$.

So the two square roots of $2 \pmod {17}$ are $x \equiv 6 \pmod {17}$ and $x \equiv 11 \pmod {17}$.

(b) By inspection we can see that $4^2 \equiv 16 \pmod {17}$. 

By Proposition (7.3) $x^2 \equiv 16 \pmod {17}$ has 2 solutions. 

We can use Proposition (3.14b) to identify the second solution as $x \equiv -4 \equiv 13 \pmod {17}$.

So the two square roots of $16 \pmod {17}$ are $x \equiv 4 \pmod {17}$ and $x \equiv 13 \pmod {17}$.

(c) We first use Euler's Criterion (7.5) to test whether 5 is a quadratic residue of 17.

Since $17 \not \mid 5$ and $5^{\frac{17-1}{2}} \equiv 5^8 \equiv -1 \pmod {17}$ and so 5 does not have a square root modulo 17.

Exercise (7.1).3

Determine whether the following are quadratic residues of prime 37:

(a) 6

(b) 2

(c) 12

(d) 5

We'll be using Euler’s Criterion (7.5). 

Let $p$ be an odd prime such that $p \not \mid a$. Then $a$ is a quadratic residue of $p$ if and only if $a^{\frac{p−1}{2}} \equiv 1 \pmod p$.

(a) $37 \not \mid 6$ and

$$ 6^{\frac{37-1}{2}} \equiv 6^{18} \equiv (6^3)^6 \equiv (31)^6 \equiv -1 \pmod {37} $$

Therefore 6 is not a quadratic residue of 37.

(b) $37 \not \mid 2$ and

$$ 2^{\frac{37-1}{2}} \equiv 2^{18} \equiv 262144  \equiv -1 \pmod {37}  $$

Therefore 2 is not a quadratic residue of 37.

(c) $37 \not \mid 12$ and

$$ 12^{\frac{37-1}{2}} \equiv 12^{18} \equiv (12^3)^6 \equiv 26^6 \equiv 308915776 \equiv 1 \pmod {37}  $$

And so 12 is a quadratic residue of 37.

(d) $37 \not \mid 5$ and

$$ 5^{\frac{37-1}{2}} \equiv 5^{18} \equiv (5^3)^6 \equiv 14^6 \equiv 7529536 \equiv -1 \pmod {37}  $$

Therefore 5 is not a quadratic residue of 37.

Exercise (7.1).2

Determine the number of quadratic residues of the following primes:

(a) 1223

(b) 3571

(c) 104 729

(d) 179 424 673

We'll be using Proposition (7.4). 

Let $p$ be an odd prime. Then there are exactly $\frac{p-1}{2}$ quadratic residues, and $\frac{p-1}{2}$ quadratic non-residues of $p$.

(a) The prime 1223 has $\frac{1223-1}{2} = 611$ quadratic residues.

(b) The prime 3571 has $\frac{3571-1}{2} = 1785$ quadratic residues.

(c) The prime 104729 has $\frac{104729-1}{2} = 52364$ quadratic residues.

(d) The prime 179424673 has $\frac{179424673-1}{2} = 89712336$ quadratic residues.

Exercise (7.1).1

Find $x^2 \pmod p$ for all the least positive residues of the following. 

In each case plot the graph of $x$ against $x^2 \pmod p$ for:

(a) $p= 5$

(b) $p= 17$

(c) $p= 19$

For each of these primes $p$ solve $x^2 \equiv 2 \pmod p$ and the equivalent quadratic Diophantine equation 

$$x^2 = 2 + py$$

(a) The following table shows the values of $x^2 \pmod 5$.

x	x^2 mod 5
1	1
2	4
3	4
4	1

The following is a plot of $x^2 \pmod 5$ against $x$.

The table and graph show the congruence $x^2 \equiv 2 \pmod 5$ has no solutions, and so the quadratic Diophantine equation $x^2 = 2 + 5y$ has no solutions.

(b) The following table shows the values of $x^2 \pmod {17}$.

x	x^2 mod 17
1	1
2	4
3	9
4	16
5	8
6	2
7	15
8	13
9	13
10	15
11	2
12	8
13	16
14	9
15	4
16	1

The following is a plot of $x^2 \pmod {17}$ against $x$.

The table and graph shows the congruence $x^2 \equiv 2 \pmod 5$ has solutions $x \equiv 6 \pmod {17}$ and $x \equiv 11 \pmod {17}$.

Using $y=\frac{x^2-2}{17}$, the solutions to the Diophantine equation $x^2 = 2 + 17y$ are $(x,y) = (6,2)$ and $(x,y) = (11,7)$.

(c) The following table shows the values of $x^2 \pmod {19}$.

x	x^2 mod 19
1	1
2	4
3	9
4	16
5	6
6	17
7	11
8	7
9	5
10	5
11	7
12	11
13	17
14	6
15	16
16	9
17	4
18	1

The following is a plot of $x^2 \pmod {19}$ against $x$.

The table and graph show the congruence $x^2 \equiv 2 \pmod {19}$ has no solutions, and so the quadratic Diophantine equation $x^2 = 2 + 19y$ has no solutions.