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$.