Determine the integers $x$ and $y$ such that $x^2 + y^2 = 178$.
Prime factorisation gives us $178 = 2 \times 89$. By the Sum of Two Squares Theorem (8.5), factors 2 and $89 \equiv 1 \pmod 4$ tells us 178 can be written as a sum of two squares.
Experimenting with small numbers immediately gives us
$$ 178 = 3^2 + 13^2 $$
Show that if $\gcd (x, y) = 1$ and $x^2 + y^2 = z^2$ then $\gcd (x, z) = \gcd (y, z) = 1$.
Let $g=\gcd(x,z)$. This means, that for some integers $x',z'$ we have $x=gx'$ and $z=gz'$. And so
$$ x^2 + y^2 = z^2 \quad \implies \quad g^2(z'^2 - x'^2) = y^2 $$
This means $g$ is a factor of $y$.
But if $g$ is a factor of $y$ and $x$ then $g=1$ since we know $\gcd(x,y)=1$. And so $\gcd(x,z)=1$.
By a symmetric argument $\gcd(y,z)=1$.
And so, the constraints $\gcd (x, y) = 1$ and $x^2 + y^2 = z^2$ imply $\gcd (x, z) = \gcd (y, z) = 1$.
Show the Pythagorean triple identity
$$ (a^2 + b^2)^2 = (a^2 − b^2)^2 + (2ab)^2 $$
by using sum of squares identity.
We remind ourselves of the Conversion Identity (8.1) for the remaining exercises:
$$ (a^2 + b^2) (c^2 + d^2) = (ac− bd)^2 + (ad + bc)^2 $$
By equating $a=c$ and $b=d$, the Conversion Identity immediately gives us
$$ (a^2 + b^2)^2 = (a^2− b^2)^2 + (2ab)^2 $$
This is a question on Pythagorean triples.
Convert the following squares to sum of two non-zero squares:
(a) $5^2$ (b) $17^2$ (c) $29^2$ (d) $202^2$
(a) It is clear that
$$ 5^2 = 3^2 + 4^2 $$
Many people have this Pythagorean triple memorised from school education.
We will use the Conversion Identity (8.1) for the remaining exercises:
$$ (a^2 + b^2) (c^2 + d^2) = (ac− bd)^2 + (ad + bc)^2 $$
(b) We have
$$ 17^2 = (4^2 + 1^2)(4^2 + 1^2) = (16-1)^2 + (4+4)^2 = 15^2 +8^2 $$
(c) We have
$$ 29^2 = (5^2 + 2^2)(5^2 + 2^2) = (25-4)^2 + (10+10)^2 = 21^2 +20^2 $$
(d) We have $202^2=2^2\times 101^2$, and so
$$ 101^2 = (10^2 + 1^2)(10^2 + 1^2) = (100-1)^2 + (10+10)^2 = 99^2 +20^2 $$
And finally,
$$ 202^2 = 2^2 \times (99^2 +20^2 ) = 198^2 + 40^2 $$
Prove the following identity for any integers $a$, $b$, $c$, and $d$:
$$ (a^2 + b^2) × (c^2 + d^2) = (ac + bd)^2 + (ad− bc)^2 $$
This is another sum of squares identity like (8.1).
We expand the LHS:
$$ (a^2 + b^2) × (c^2 + d^2) = a^2c^2 + a^2d^2 + b^2c^2 + b^2d^2 $$
We expand the RHS:
$$ (ac + bd)^2 + (ad− bc)^2 = a^2c^2 + b^2d^2 + \cancel{2abcd} + a^2d^2 + b^2c^2 - \cancel{2abcd} = a^2c^2 + a^2d^2 + b^2c^2 + b^2d^2 $$
The LHS = RHS, and so
$$ (a^2 + b^2) × (c^2 + d^2) = (ac + bd)^2 + (ad− bc)^2 $$
Show that any integer $n > 1$ can be written as $n = p_1 \times p_2 × \ldots × p_r × N^2$ where $p$’s are distinct primes.
By the fundamental theorem of arithmetic, any integer larger than 1 can be written uniquely as a product of primes.
$$ n = p_1^{k_1} \times p_2^{k_2} \times \ldots \times p_x^{k_x}$$
Each prime factors $p_i$ appears $k_i$ times in this product.
There are two cases for $k_i$, even $k_i=2m$ and odd $k_i=2m+1$, for some positive number $m$.
Case $k_i$ even
We can write each prime factor that appears an even number of times as
$$ p_i^{k_i} = p_i^{2m} = (p_i^m)^2 $$
And so each $p_i$, which appears an even number of times in the prime factorisation of $n$, is a factor of $N^2$.
Case $k_i$ odd
Similarly, we can write each prime factor that appears an odd number of times as
$$ p_i^{k_i} = p_i^{2m+1} = p_i \times (p_i^m)^2 $$
And so each $p_i$ which appears an odd number of times in the prime factorisation of $n$, appears once in the product of unique primes, and the remaining even number of $p_i$ are factors of $N^2$.
And so any integer $n>1$ can be written as a product of distinct primes and a perfect square $N^2$.
Prove Lemma (8.2).
Let's remind ourselves of Lemma (8.2).
If prime $p \equiv 1 \pmod 4$ then there exist positive integers $x$ and $y$ such that $x^2 + y^2 = kp$ where $k < p$ and it is a positive integer.
We can write $x^2 + y^2 = kp$ as
$$ x^2 \equiv -y^2 \pmod p $$
Since $p \equiv 1 \pmod 4$, by Proposition (7.11) we have
$$ (\frac{-1}{p}) = 1$$
By definition of the Legendre symbol
$$ (\frac{y^2}{p}) = 1 $$
Using the multiplicity of the Legendre symbol
$$ (\frac{-y^2}{p}) = (\frac{-1}{p}) \times (\frac{y^2}{p}) = 1 \times 1 = 1 $$
But $(\frac{-y^2}{p})=1$ means that the following has integer solutions for $x$,
$$ x^2 \equiv - y^2 \pmod p $$
That is, $x^2 + y^2 = kp$ has solutions.
Because $(-x)^2 = x^2$ and $(-y)^2 = y^2$, we can additionally state that positive integer solutions exist.
We now need to show that $k < p$ still permits solutions.
If $x \pmod p$ is a solution, so is $-x \equiv p-x \pmod p$. This means that if solutions exist, they include solutions in the range $0 \le x < \frac{p}{2}$.
This means
$$ 0 \le x^2 + y^2 < (\frac{p}{2})^2 + (\frac{p}{2})^2 = \frac{p^2}{2} = \frac{p}{2} \times p $$
That is, solutions to $x^2 + y^2 =kp$ exist when $k < \frac{p}{2} < p$.
Prove the following:
Let $p$ be prime such that $p ≡ 1 \pmod 4$ and $k$ be a natural number. We can write $n = p^k$ as a sum of two squares.
There are two cases for $k$, even $k=2m$ and odd $k=2m+1$, for some integer $m$.
Case $k$ even
If $k$ is even, then $n=p^{2m}=(p^m)^2+0^2$.
Case $k$ odd
Since $p \equiv 1 \pmod 4$, we can write it as the sum of two squares, by the Sum of Two Squares Theorem (8.5). That is, for some natural numbers $a,b$
$$ p = a^2 + b^2 $$
If $k$ is odd, then
$$ n = p^{2m+1}=p^{2m} \times (a^2+b^2) = (p^m)^2 \times (a^2+b^2) = a^2(p^m)^2 + b^2(p^m)^2 = (ap^m)^2+(bp^m)^2 $$
In both cases we have shown $n$ can written as the sum of two squares.
Prove that if we can write the natural number $n$ as a sum of two squares then we can also write $k^2n$ as a sum of two squares.
We're given that we can write $n$ as the sum of two squares. Let these be $x^2$ and $y^2$.
$$ \begin{align} n & = x^2 + y^2 \\ \\ k^2n & = k^2(x^2 + y^2) \\ \\ & = (kx)^2 + (ky)^2 \end{align}$$
And so $k^2n$ can also be written as the sum of two squares.
Show that the positive integer $n^k$ where $k$ is an even positive integer can be written as a sum of two squares.
Since $k$ is even, we can write it as $k=2m$. And so
$$ n^k = n^{2m} = (n^m)^2 + 0^2 $$
And so $n^k$ where $k$ is even, can be written as the sum of two squares.
Show that $2^n$, where $n$ is a natural number, can be written as sum of two squares.
There are two cases for $n$, even and odd.
In both cases we can express $2^n$ as a sum of two squares.
Show the following identities concerning Pythagorean triples:
(a) $(3n)^2 + (4n)^2 = (5n)^2$
(b) $(2n)^2 + (n^2− 1)^2 = (n^2 + 1)^2$
(c) $(2mn)^2 + (n^2− m^2)^2 = (n^2 + m^2)^2$
(a) We proceed as follows
$$ \begin{align} (3n)^2 + (4n)^2 & = (3^2 + 4^2)n^2 \\ \\ & = 5^2n^2 \\ \\ & = (5n)^2 \end{align} $$
(b) We proceed as follows
$$ \begin{align} (2n)^2 + (n^2− 1)^2 & = 4n^2 + (n^2)^2 + 1 - 2n^2 \\ \\ & = 2n^2 + (n^2)^2 + 1 \\ \\ & = (n^2 + 1)^2 \end{align} $$
(c) We proceed as follows
$$ \begin{align} (2mn)^2 + (n^2− m^2)^2 & = 4m^2n^2 + n^4 + m^4 -2n^2m^2 \\ \\ & = 2m^2n^2 + n^4 + m^4 \\ \\ & = (n^2 + m^2)^2 \end{align} $$
Convert the following integers into sum of two squares:
(a) 2016
(b) 2015
(c) 2017
Hint: 2017 is prime. Consider the square root of 2017.
(d) 2018
Hint: $2018= 2 \times 1009$ and determine $1009− 28^2$.
(e) $2019= 3 \times 673$
(f) 2020
(a) The prime factorisation is $2016 = 2^5 × 3^2 × 7$.
Since $7 \equiv 3 \pmod 4$ and appears with an odd power, by Corollary (8.8) the number 2016 can't be written as a sum of two squares.
(b) The prime factorisation if $2015 = 5 \times 13 \times 31$.
Since $31 \equiv 3 \pmod 4$ and appears with an odd power, by Corollary (8.8) the number 2015 can't be written as a sum of two squares.
(c) Taking the hint $\lfloor \sqrt{2017} \rfloor = 44$ gives us
$$ 2017 = 44^2 + 9^2 $$
(d) The prime factorisation is $2018= 2 \times 1009$. Taking the hint we have $1009-28^2=15^2$. And so
$$ 2018 = (1^2+1^2) \times (28^2 + 15^2) $$
By the Conversion Identity (8.1)
$$ 2018 = (28-15)^2 +(15+28)^2 = 13^2+43^2$$
(e) The prime factorisation is $2019=3 \times 673$.
Since $3 \equiv 3 \pmod 4$ and appears with an odd power, by Corollary (8.8) the number 2019 can't be written as a sum of two squares.
(f) The prime factorisation is $2020=2^2 \times 5 \times 101$.
Rewriting,
$$ 2020 = 2^2 \times (2^2 + 1^2) \times (10^2 + 1^2) = (4^2 + 2^2) \times (10^2 + 1^2) $$
By the Conversion Identity (8.1)
$$ 202 = (40-2)^2 + (4+20)^2 = 38^2 + 24^2 $$
Convert the following integers into sum of two squares:
(a) 202 (b) 205 (c) 180
We will use Sum of Two Squares Theorem (8.5).
Let $m$ be a positive integer given by $m = p_1 \times p_2 \times \ldots × p_r × N^2$ where the $p$’s are distinct primes. Then $m$ can be expressed as a sum of two squares, provided every prime $p_j$ satisfies $p_j = 2$ or $p_j \equiv 1 \pmod 4$ for $j= 1, \ldots , r$.
We will also use the Conversion Identity (8.1).
For any integers $a$, $b$, $c$, and $d$ we have
$$ (a^2 + b^2) (c^2 + d^2) = (ac− bd)^2 + (ad + bc)^2 $$
(a) The prime factorisation is $202=2 \times 101$. We note that $101=1 \pmod 4$.
This gives us
$$ 202 = (1^2+1^2) \times (10^2 + 1^2) $$
Using the Conversion Identity (8.1)
$$ 202 = (10-1)^2 + (1+10)^2 = 9^2 + 11^2$$
(b) The prime factorisation is $5 \times 41$. We note that $5 \equiv 41 \equiv 1 \pmod 4$.
This gives us
$$ 205 = (2^2 + 1^2) \times (5^2 + 4^2) $$
Using the Conversion Identity (8.1)
$$ 202 = (10-4)^2 + (8+5)^2 = 6^2 + 13^2 $$
(c) The prime factorisation of $180 = 2^2 \times 3^2 \times 5 = 6^2 \times 5$. We note that $5 \equiv 1 \pmod 4$.
This gives us
$$ 180 = (6^2 + 0^2) \times (2^2+1^2) $$
Using the Conversion Identity (8.1)
$$ 180 = (12-0)^2 + (6+0)^2 = 12^2 + 6^2$$
Express the following into sum of two squares:
(a) 256 (b) 281 (c) 512 (d) 2048
(a) $256 = 16^2 + 0^2$
(b) $281=16^2 + 5^2$
(c) $512 = 16^2 + 16^2$
(d) $2048 = 32^2 + 32^2$
Convert the following integers into sum of two squares:
(a) 36 (b) 37 (c) 101 (d) 170 (e) 229
(a) $36 = 6^2 + 0^2$
(b) $37 = 6^2 + 1^2$
(c) $101 = 10^2 + 1^2$
(d) $170 = 7^2 + 11^2$
Interestingly, $170 = 13^2 + 1^2$ is also true.
(d) $229 = 2^2 + 15^2$
Prove that there are infinitely many primes of the form $3n - 1$.
For the purpose of contradiction assume there are a finite number $k$ of primes $p_1, p_2, \ldots, p_k$ of the form $3n-1$.
Consider the number
$$ N=3\times p_1 \times p_2 \times \ldots p_k - 1 $$
which is of the form $3n-1$.
Since $N>1$ it has prime factors. Any such prime factor, let's call it $q$, is not 3 or any of the $p_1, p_2, \ldots, p_k$ because that would mean $p_i \mid 1$ which is not possible.
Is $q$ of the form $3n-1$? Since $N \equiv -1 \pmod 3$ that means an odd number of the prime factors of $N$ are congruent to $-1 \pmod 3$, that is, of the form $3n-1$. That is, at least one.
The existence of at least one prime factor of $N$ of the form $3n-1$ which is not one of the $p_1, p_2, \ldots, p_k$ contradicts the assumption there are a finite number of primes of the form $3n-1$.
Assume $3 \not \mid x$. Show that one of the prime factors of $x^2 + 3$ is of the form $12n + 7$.
If prime $p$ is a factor of $x^2+3$ then $x^2 \equiv -3 \pmod p$. This means $(\frac{-3}{p}) = 1$.
If a prime factor is of the form $12n+7$, for some integer $n$, then it must be that $(\frac{-3}{12n+7}) = 1$. This is what we need to show.
$$ \begin{align} (\frac{-3}{12n+7}) & = (\frac{-1}{12n+7}) \times (\frac{3}{12n+7}) \\ \\ &= (-1) \times (\frac{3}{12n+7}) \tag{Proposition (7.11)} \\ \\ & = (-1) \times -(\frac{12n+7}{3}) \tag{Corollary (7.17)} \\ \\ & = (-1) \times -(\frac{1}{3}) \\ \\ &= -1 \times -1 = 1 \end{align} $$
And so a prime of the form $12n+7$ is a factor of $x^2+3$.
Note: Primes of a different form may also satisfy $(\frac{-3}{p}) = 1$, and therefore also be factors of $x^2+3$.
Prove the following for prime $p$ where $p \not \mid 7$:
$$ (\frac{7}{p}) = 1 \quad \text{if } p \equiv \pm 1, \pm 3, \pm 9 \pmod {28} $$
Factorise the following:
(a) $120^2− 7 = 14393$
(b) $354^2− 7 = 125309$
We consider the six cases $p \equiv \pm 1, \pm 3, \pm 9 \pmod {28}$.
Case $p \equiv 1 \pmod {28}$
We write $p=28k + 1 $ for some integer $k$. Then, using Corollary (7.17),
$$ (\frac{7}{p}) = (\frac{7}{28k + 1}) = (\frac{28k + 1}{7}) = (\frac{1}{7}) = 1 $$
Case $p \equiv -1 \pmod {28}$
We write $p=28k + 1 $ for some integer $k$. Then, using Corollary (7.17),
$$ (\frac{7}{p}) = (\frac{7}{28k - 1}) = -(\frac{28k - 1}{7}) =-(\frac{-1}{7}) = -(-1)= 1 $$
Case $p \equiv 3 \pmod {28}$
We write $p=28k + 3 $ for some integer $k$. Then, using Corollary (7.17),
$$ (\frac{7}{p}) = (\frac{7}{28k + 3}) = -(\frac{28k + 3}{7}) = -(\frac{3}{7}) =+(\frac{7}{3})= -(\frac{1}{3}) = 1 $$
Case $p \equiv -3 \pmod {28}$
We write $p=28k + 3 $ for some integer $k$. Then, using Corollary (7.17),
$$ (\frac{7}{p}) = (\frac{7}{28k - 3}) = (\frac{28k - 3}{7}) = (\frac{2^2}{7}) = 1 $$
Case $p \equiv 9 \pmod {28}$
We write $p=28k + 9 $ for some integer $k$. Then, using Corollary (7.17) and Proposition (7.15),
$$ (\frac{7}{p}) = (\frac{7}{28k + 9}) = (\frac{28k +9 }{7}) = (\frac{2}{7}) = 1 $$
Case $p \equiv -9 \pmod {28}$
We write $p=28k + 9 $ for some integer $k$. Then, using Corollary (7.17) and Proposition (7.15),
$$ (\frac{7}{p}) = (\frac{7}{28k - 9}) = -(\frac{28k -9 }{7}) = -(\frac{5}{7}) = -(\frac{7}{5}) = -(\frac{2}{5})= -(-1) = 1 $$
All the cases confirm that for prime $p$ where $p \not \mid 7$:
$$ (\frac{7}{p}) = 1 \quad \text{if } p \equiv \pm 1, \pm 3, \pm 9 \pmod {28} $$
A prime factor $p$ of $x^2-7$ means $x^2 \equiv 7 \pmod p$. We have just shown that $p \equiv \pm 1, \pm 3, \pm 9 \pmod {28}$. The first of such primes are
$$ 3, 19, 29, 31, 37, 47, 53, 59, 83, 103, 109, 113, 131, 137, 139, 149, 167, 193, 197, 199 $$
(a) Trying factor 37 gives
$ 14393 = 37 \times 389 $
Trying prime factors up to $\lfloor \sqrt{389} \rfloor = 19$ tells us 389 is prime.
(b) Trying factors 29 amd 149 gives
$125309 = 29^2 \times 149 $
The following table shows some of the odd primes for which 5 is a quadratic residue and quadratic non-residue:
| prime p | 3 | 7 | 11 | 13 | 17 | 19 | 23 | 29 | 31 |
| (5/p) | -1 | -1 | 1 | -1 | -1 | 1 | -1 | 1 | 1 |
(i) Predict the congruence describing the primes for which 5 is a quadratic residue and the primes for which 5 is a quadratic non-residue. Prove your predicted formula.
(ii) Factorise the following integers:
(a) $104^2 − 5 = 10 811$
(b) $504^2 − 5 = 254 011$
(i) The table suggests the congruence describing the primes for which 5 is a quadratic residue or not is
$$ (\frac{5}{p}) = \begin{cases} 1& p \equiv \pm 1 \pmod {10} \\ -1 & p \equiv \pm 3 \pmod {10} \end{cases}$$
We'll consider the four cases, $p \equiv \pm 1 \pmod {10}$ and $p \equiv \pm 3 \pmod {10}$, in turn. There are no other cases as $p=10k+x$ where $x$ is not $\pm1$ or $\pm3$ would mean $p$ is not prime.
Case $p \equiv 1 \pmod {10}$
We write $p=10k + 1 $ for some integer $k$. Then, using Corollary (7.17),
$$ (\frac{5}{p}) = (\frac{5}{10k + 1}) = (\frac{10k + 1}{5}) = (\frac{1}{5}) = 1 $$
Case $p \equiv -1 \pmod {10}$
We write $p=10k - 1 $ for some integer $k$. Then, using Corollary (7.17),
$$ (\frac{5}{p}) = (\frac{5}{10k - 1}) = (\frac{10k - 1}{5}) = (\frac{-1}{5}) = (\frac{2^2}{5}) = 1 $$
Case $p \equiv 3 \pmod {10}$
We write $p=10k + 3 $ for some integer $k$. Then, using Corollary (7.17), and Proposition (7.15),
$$ (\frac{5}{p}) = (\frac{5}{10k + 3}) = (\frac{10k + 3}{5}) = (\frac{3}{5}) = (\frac{5}{3}) = (\frac{2}{3}) = -1 $$
Case $p \equiv -3 \pmod {10}$
We write $p=10k + 3 $ for some integer $k$. Then, using Corollary (7.17), and Proposition (7.15),
$$ (\frac{5}{p}) = (\frac{5}{10k - 3}) = (\frac{10k - 3}{5}) = (\frac{-3}{5}) = (\frac{2}{3}) = -1 $$
These four cases have shown that
$$ (\frac{5}{p}) = \begin{cases} 1& p \equiv \pm 1 \pmod {10} \\ -1 & p \equiv \pm 3 \pmod {10} \end{cases}$$
(ii) A prime factor $p$ of $x^2-5$ means $x^2 \equiv 5 \pmod p$. We have just shown that $p \equiv \pm 1 \pmod {10}$. The first of such primes are
$$ 11, 19, 29, 31, 41, 59, 61, 71, 79, 89, 101, 109, 131, 139, 149, 151, 179, 181, 191, 199, 211, 229, 239, 241, 251, 269 $$
(a) Trying factor 19 gives us
$10811 = 19 \times 569$
Trying factors up to $\lfloor \sqrt{569}\rfloor = 23$ tells us 569 is prime.
(b) Trying factors 19 and 29 gives us
$254011 = 19x29 × 461$
Trying factors up to $\lfloor \sqrt{461}\rfloor = 21$ tells us 461 is prime.
Show that if p ≡ 1 (mod 4) then
$$ \sum_{a=1}^{(p-1)/2} (\frac{a}{p}) = 0 $$
where $(\frac{a}{p})$ is the Legendre symbol.
Hint: You may find the result of question 7 of Exercises 7.1 helpful.
From Exercise (7.1).7 we have that if $a$ is a quadratic residue of $p$ then so is $p-a$ if and only if $p \equiv 1 \pmod 4$. This means the number of quadratic residues in the range $[1, \frac{p-1}{2}]$ is the same as the number in the range $[\frac{p+1}{2},p-1]$. Similarly for quadratic non-residues.
Proposition (7.4) tells us that there are $\frac{p-1}{2}$ quadratic residues, and $\frac{p-1}{2}$ quadratic non-residues, modulo odd prime $p$.
This means there are $\frac{p-1}{4}$ quadratic residues, and $\frac{p-1}{4}$ quadratic non-residues, in the range $[1, \frac{p-1}{2}]$.
The Legendre symbol for a quadratic residue is 1, and for a non-residue is -1. Since there are an equal number of quadratic residues and non-residues in the range $[1, \frac{p-1}{2}]$, the sum of the Legendre symbols is zero. And so,
$$ \sum_{a=1}^{(p-1)/2} (\frac{a}{p}) = 0 $$
Let $p \equiv 1 \pmod 4$. Show that the Legendre symbols $(\frac{2a}{p}) = (\frac{a}{p})$ where $a$ is odd and $p \not \mid a$.
I believe this is a false statement. The statement is true for $p \equiv 1 \pmod 8$.
The following is a counter-example.
Counter-Example
We take $p=5$ which satisfies $p \equiv 1 \pmod 4$.
We also take $a=3$ which satisfies the condition $a$ is odd, and $p \not \mid a$.
The Legendre symbols are as follows.
$$ (\frac{2 \times 3}{5}) = (\frac{2}{5}) \times (\frac{3}{5}) = -1 \times (\frac{5}{3}) =-1 \times (\frac{2}{3}) = -1 \times -1 = 1 $$
$$ (\frac{3}{5}) = (\frac{5}{3}) = (\frac{2}{3}) = -1 $$
So $(\frac{2a}{p}) = (\frac{a}{p})$ does not hold under the given conditions.
Note: the author's official solution considers $p \equiv 1 \pmod 8 \implies p \equiv 1 \pmod 4$ but does not consider $p \equiv -3 \pmod 8 \implies p \equiv 1 \pmod 4$.
Prove that if the prime $p= 8k + 1$ then
$$p \mid (2^{\frac{p-1}{2}} - 1) $$
By Proposition (7.15), if $p \equiv 1 \pmod 8$ then 2 is a quadratic residue of $p$. By Euler's Criterion
$$ 2^{\frac{p-1}{2}} \equiv 1 \pmod p $$
That is,
$$p \mid (2^{\frac{p-1}{2}} - 1) $$
Determine the least positive residues $x$ in the following cases (1993 is prime):
(a) $25^{997} \equiv x \pmod {1993}$
(b) $26^{997} \equiv x \pmod {1993}$
(a) We observe that $5^2 \equiv 25 \pmod {1993}$, and $1993 \not \mid 25$, and so by Euler's Criterion (7.5)
$$ 25^{\frac{1993-1}{2}} \equiv 25^{996} \equiv 1 \pmod {1993}$$
Multiplying through by 25 gives us
$$ 25^{997} \equiv 25 \pmod {1993}$$
And so the least positive residue is $x=25$.
(b) We try to apply the same technique as in part (a). To do this we need to establish whether 26 is a quadratic residue of 1993.
We proceed
$$ \begin{align} (\frac{26}{1993}) & = (\frac{2}{1993}) \times (\frac{26}{1993}) \\ \\ &= 1 \times (\frac{26}{1993}) \tag{Proposition 7.15} \\ \\ & = (\frac{1993}{13}) = (\frac{2^2}{13}) = 1 \tag{Corollary 7.17} \end{align} $$
And so 26 is a quadratic residue of 1993, and so by Euler's Criterion
$$ 26^{\frac{1993-1}{2}} \equiv 26^{996} \equiv 1 \pmod {1993}$$
Multiplying through by 26 gives us
$$ 26^{997} \equiv 26 \pmod {1993}$$
And so the least positive residue is $x=26$.
Prove that there are infinitely many primes of the form $3m + 1$ without using Dirichlet’s Theorem.
Hint: You may find the result of question 5 helpful.
For the purpose of contradiction we assume there are a finite number $k$ of primes $p_1, p_2, \ldots, p_k$ of the form $3m+1$, where $m$ is some positive integer.
We construct a number $N$ as follows
$$ N = (p_1 \times p_2 \times \ldots p_k )^2 + 3 $$
This $N$ is of the form $3m+1$ for some integer $m$.
There are two cases for $N$, prime and composite. Let's consider each in turn.
Case $N$ prime
If $N$ is prime, then it is larger than any of the $p_1, p_2, \ldots, p_k$ primes.
We've established that $N$ is of the form $3m+1$. This contradicts the assumption that the only primes of the form $3m+1$ are $p_1, p_2, \ldots, p_k$.
Case $N$ composite
If $N$ is composite it has an odd prime factor $p$, and so
$$ (p_1 \times p_2 \times \ldots p_k)^2 \equiv -3 \pmod p $$
Exercise (7.4).5 tell us $(\frac{-3}{p})=1 \iff p \equiv 1 \pmod 6$. That is, $p=6k+1$ for some integer $k$. Rewriting as $p=3(2k)+1$ means $p$ is of the form $3m+1$.
This $p$ is not one of the $p_1, p_2, \ldots, p_k$ because none of these divide $N=(p_1 \times p_2 \times \ldots p_k)^2 + 3$. If one $p_i$ did divide $N$ then it would have to divide 3, a contradiction.
This $p$ contradicts the assumption that the only primes of the form $3m+1$ are $p_1, p_2, \ldots, p_k$.
Both cases for $N$ contradict the assumption there are a finite number of primes of the form $3m+1$, and so there are infinitely many primes of this form.
Prove that the odd prime divisors of the integer $n^2 + 1$ are of the form $4k + 1$.
If odd prime $p$ is a factor of $n^2+1$ then
$$ n^2 \equiv -1 \pmod p $$
From Proposition (7.11) extended by the result from Exercise (7.1).6 we know that $(\frac{-1}{p})=1 \iff p \equiv 1 \pmod 4$. That is, $p=4k+1$ for some integer $k$.
Let $p= 13$ and $a = 16$. Show that
$$\sum_{k=1}^{(p-1)/2} \lfloor \frac{a \times k}{p} \rfloor = 23 $$
but $g= 2$ where $g$ is as defined in Gauss’s Lemma. Explain why Lemma (7.20) fails in this case.
The following table shows the calculations which confirm the sum is 23.
| k | floor (16k/13) |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
| 5 | 6 |
| 6 | 7 |
| 23 |
The Lemma is not applicable because it requires $a$ to be odd, but here $a=16$ is even.
Prove Lemma (7.20).
Let's remind ourselves of Lemma (7.20).
Let $p$ be an odd prime and $a$ also be odd such that $p \not \mid a$. Let $g$ be the number of negative residues as defined in Gauss’s Lemma (7.14). We have
$$\sum_{k=1}^{(p-1)/2} \lfloor \frac{a \times k}{p} \rfloor \equiv g \pmod 2 $$
We start with the division algorithm and write $ak$ as
$$ ak = p \times \lfloor \frac{ak}{p} \rfloor + r $$
where $r$ is the least positive residue of $ak$ modulo $p$.
Next we'll consider the set $R$ of values of $r$ for $1 \le k \le \frac{p-1}{2}$.
$$ R = \{s_1, s_2, \ldots, r_h, \quad t_1, t_2, \ldots, t_g\}$$
where the residues $1 \le s_i \le \frac{p-1}{2}$ and $\frac{p+1}{2} \le t_i \le (p-1)$. Here $g$, by definition, is the number of least positive residues larger than $\frac{p-1}{2}$, and $g+h=\frac{p-1}{2}$.
We'll show the residues are distinct, a fact we'll use later. Consider two residues $r_1, r_2 \in R$.
$$ r_1 \equiv r_2 \pmod p \implies ak_1 \equiv ak_2 \pmod p \implies k_1\equiv k_2 \pmod p $$
Since $1 \le k_1,k_2 \le \frac{p-1}{2}$, this means $k_1=k_2$. That is, no two residues are congruent modulo $p$, and since the set $R$ is of least positive residues, they are all less than $p$, and so incongruence also means inequality.
We now construct another set $S$ from $R$ by replacing those elements $t_i$ with $p-t_i$. Note that since $\frac{p+1}{2} \le t_i \le (p-1)$, this means $1 \le p - t_i \le \frac{p-1}{2}$.
$$ S = \{s_1, s_2, \ldots, r_h, \quad p-t_1, p-t_2, \ldots, p-t_g\}$$
We'll show that $S=\{1,2,3, \ldots, \frac{p-1}{2}\}$. To do this we first note that there are $\frac{p-1}{2}$ elements of $S$ all less than or equal to $\frac{p-1}{2}$. We also need to show no two elements are the same. We know all the $s_i$ are distinct, and all the $t_i$ are distinct. Let's consider whether $s_i$ and $p-t_i$ are distinct.
$$ s_i \equiv p-t_i \pmod p \implies s_i + t_i \equiv 0 \pmod p \implies a (k_1 + k_2) \equiv 0 \pmod p \implies k_1 +k_2 \equiv 0 \pmod p $$
This is a contradiction since $2 \le k_1+k_2 \le p-1$, and so no two elements of $S$ are congruent.
Since $S$ has $\frac{p-1}{2}$ incongruent elements, all of value less than or equal to $\frac{p-1}{2}$, then it must be that
$$ S = \{1, 2, 3, \ldots , \frac{p-1}{2} \}$$
Let's consider the sum of the elements of $S$,
$$ \sum_{k=1}^{(p-1)/2}k = \sum_{i=1}^{h} s_i + \sum_{i=1}^{g} p-t_i \tag{i}$$
Let's also consider the sum of $ak$ over $1 \le k \le \frac{p-1}{2}$,
$$ \sum_{k=1}^{(p-1)/2} ak = \sum_{k=1}^{(p-1)/2}p \lfloor \frac{ak}{p} \rfloor +\sum_{i=1}^{h} s_i + \sum_{i=1}^{g} t_i \tag{ii} $$
Subtracting (ii) from (i),
$$ (a-1)\sum_{k=1}^{(p-1)/2} k = p \sum_{k=1}^{(p-1)/2} \lfloor \frac{ak}{p} \rfloor -pg + 2\sum_{i=1}^{g} t_i $$
Taking modulo 2 means removing terms that are even, noting that $(a-1)$ is even,
$$ pg \equiv p \sum_{k=1}^{(p-1)/2} \lfloor \frac{ak}{p} \rfloor $$
Dividing by $p$ is permissible since $p \not \mid 2$
$$ \sum_{k=1}^{(p-1)/2} \lfloor \frac{ak}{p} \rfloor \equiv g \pmod 2 $$
This is the desired result.
Note: this solution was helped by Esenstein's Lemma (proofwiki).
Prove Corollary (7.17).
We remind ourselves of Prove Corollary (7.17).
Let p and q be distinct odd primes, then
$$ (\frac{p}{q}) = \begin{cases} (\frac{q}{p}) & \text{ if } p \equiv 1 \pmod 4 \text{ or } q \equiv 1 \pmod {4} \\ -(\frac{q}{p}) & \text{ if } p \equiv q \equiv 3 \pmod {4} \end{cases} $$
We use the result we proved in Exercise (7.4).3. If $p$ and $q$ are distinct odd primes then
$$ (\frac{p}{q}) \times (\frac{q}{p}) = \begin{cases} 1 & \text{ if } p \equiv 1 \pmod {4} \text{ or } q \equiv 1 \pmod {4} \\ -1 & \text{ if } p \equiv q \equiv 3 \pmod {4} \end{cases}$$
Let's consider each of the two cases in turn.
If $p \equiv 1 \pmod 4$ or $q \equiv 1 \pmod 4$ then
$$ (\frac{p}{q}) \times (\frac{q}{p}) = 1$$
This is only possible if $ (\frac{p}{q})$ and $(\frac{q}{p})$ are both 1 or both -1, that is $(\frac{p}{q}) = (\frac{q}{p})$. The corollary holds for this case.
If $p \equiv q \equiv 3 \pmod 4$ then
$$ (\frac{p}{q}) \times (\frac{q}{p}) = -1$$
This is only possible $ (\frac{p}{q}) = 1$ and $(\frac{q}{p})=-1$, or $ (\frac{p}{q}) = -1$ and $(\frac{q}{p})=1$. That is $(\frac{p}{q}) = -(\frac{q}{p})$. The corollary holds for this case.
We have shown Corollary (7.17) holds for all possible cases of $p$ and $q$.
Determine
$$ \sum_{k=1}^{(q-1)/2} \lfloor \frac{k \times p}{q} \rfloor + \sum_{k=1}^{(p-1)/2} \lfloor \frac{k \times q}{p} \rfloor $$
for the primes $p= 17$ and $q= 13$. Also interpret your answer geometrically by counting the lattice points above and below the line $y=\frac{q}{p}x$.
For $p= 17$ and $q= 13$, we have
$$ \begin{align} \sum_{k=1}^{6} \lfloor \frac{k \times 17}{13} \rfloor + \sum_{k=1}^{8} \lfloor \frac{k \times 13}{17} \rfloor & = \lfloor \frac{17}{13} \rfloor + \lfloor \frac{34}{13} \rfloor + \lfloor \frac{51}{13} \rfloor + \lfloor \frac{68}{13} \rfloor + \lfloor \frac{85}{13} \rfloor + \lfloor \frac{102}{13} \rfloor \\ \\ & + \lfloor \frac{13}{17} \rfloor + \lfloor \frac{26}{17} \rfloor + \lfloor \frac{39}{17} \rfloor + \lfloor \frac{52}{17} + \lfloor \frac{65}{17} \rfloor + \lfloor \frac{78}{17} \rfloor + \lfloor \frac{91}{17} \rfloor + \lfloor \frac{104}{17} \rfloor \\ \\ & = (1 + 2 + 3 + 5 + 6 + 7) + (0 + 1+2+3+3+4+5+6) \\ \\ & = 24 + 24 = 48 \end{align}$$
Alternatively we can use Eisenstein's Lemma (7.19)
$$ \sum_{k=1}^{6} \lfloor \frac{k \times 17}{13} \rfloor + \sum_{k=1}^{8} \lfloor \frac{k \times 13}{17} \rfloor = (\frac{13-1}{2}) \times (\frac{17-1}{2}) = 6 \times 8 = 48 $$
The following graph (link) illustrates the lattice points above and below the line $y=\frac{13}{17}x$.
We can see that below the line there are columns of lattice points of heights 1, 2, 3, 3, 4, 5, 6, corresponding to the calculation above.
Similarly, above the line there are rows of lattice points of length 1, 2, 3, 5, 6, 7, also corresponding to the calculation above.
However we count the lattice points, the total is $8 \times 6 = 48$.
Prove that there are infinitely many primes of the form $8k- 1$ without using Dirichlet’s Theorem.
Hint: Suppose there are a finite number of primes $p_1, p_2, \ldots , p_k$ of this form and consider the integer $(4p_1p_2\ldots p_k)^2− 2$ and then use Proposition (7.15).
We assume, for the purpose of contradiction, there are finite primes $p_1, p_2, \ldots, p_k$ of the form $8k-1$, where $k$ is a positive integer.
Let's consider a constructed number $N=(p_1p_2 \ldots p_k)^2-2$, noting that $p_i \equiv -1 \pmod 8$,
$$ N \equiv (p_1p_2 \ldots p_k)^2 -2 \equiv (-1 \times -1 \ldots -1)^2 -2 \equiv 1-2 \equiv -1 \pmod 8 $$
This means $N$ is of the form $8k-1$.
We have two cases for $N$, prime or composite.
Case $N$ prime
If $N$ is prime, then we have found another prime of the form $8k-1$ that is larger than any of the $p_1, p_2, \ldots, p_k$ of the form $8k-1$. This contradicts the assumption there are only $k$ primes of form $8k-1$.
Case $N$ composite
If $N$ is composite, then it has a prime factor, which we can call $q$. This means
$$ (p_1p_2 \ldots p_k)^2 \equiv 2 \pmod q $$
By Proposition (7.15) this means $q \equiv \pm 1 \pmod 8$.
Let's consider each of these two options.
For all the possible cases, we have shown the assumption of a finite number of primes of the form $8k-1$ leads to a contradiction. And so there are an infinite number of primes of the form $8k-1$.
Show that the prime factors $p > 3$ of the integer $n^2 - n + 1$ are of the form 6k + 1.
Hint: Use the result of question 5 and let $p \mid (n^2− n + 1)$, and then consider $(2n− 1)^2$.
By the previous exercise, $ (2n-1)^2 \equiv -3 \pmod p $ requires any prime $p>3$ to conform to $p \equiv 1 \pmod 6$, that is $p=6k+1$ for some integer $k$.
We note that
$$ (2n-1)^2 = 4n^2 -4n +1 = 4(n^2 -n + 1) - 3 $$
This means such a $p$ divides $4(n^2 -n + 1)$. But $p \not \mid 4$ and so $p \mid (n^2 -n + 1)$.
And so we conclude the prime factors $p > 3$ of the integer $n^2 - n + 1$ are of the form 6k + 1.
Prove that for prime $p > 3$ we have
$$ (\frac{-3}{p}) = \begin{cases} (1 & \text{ if } p \equiv 1 \pmod {6} \\ -1 & \text{ if } p \equiv 5 \pmod {6} \end{cases}$$
Determine the prime factorisation of the following:
(a) $104^2 + 3 = 10 819$
(b) $236^2 + 3 = 55 699$
(c) $362^2 + 3 = 131 047$
We remember that the Legendre Symbol is multiplicative (Proposition 7.9)(c). This tells us
$$ (\frac{-3}{p}) = (\frac{-1}{p}) \times (\frac{3}{p}) $$
Proposition (7.11) tells us, for an odd prime $p$,
$$ (\frac{-1}{p}) = \begin{cases} 1 & \text{ if } p \equiv 1 \pmod {4} \\ -1 & \text{ if } p \equiv 3 \pmod {4} \end{cases}$$
We also have the result we proved in Exercise (7.3)(11), that for a prime $p>3$,
$$ (\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} $$
The following table summarises these results for an odd prime $p \pmod {12}$. The rows coloured grey are excluded as any integer with the corresponding congruence modulo 12 is not prime.
| p mod 12 | (-1/p) | (3/p) | (-1/p)(3/p) | p mod 6 |
| 1 | 1 | 1 | 1 | 1 |
| 2 | ||||
| 3 | -1 | |||
| 4 | ||||
| 5 | 1 | -1 | -1 | 5 |
| 6 | ||||
| 7 | -1 | -1 | 1 | 1 |
| 8 | ||||
| 9 | 1 | |||
| 10 | ||||
| 11 | -1 | 1 | -1 | 5 |
We can read off the desired result directly, for prime $p>3$,
$$ (\frac{-3}{p}) = \begin{cases} 1 & \text{ if } p \equiv 1 \pmod {6} \\ -1 & \text{ if } p \equiv 5 \pmod {6} \end{cases}$$
For the following exercises we require prime factors $p$ such that $x^2 \equiv -3 \pmod p$. By the above result we require primes that are congruent to 1 modulo 6. The first of these are
$$ 7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97, 103, 109, 127, 139, 151, 157, 163, 181, 193, 199 $$
(a) Trying factor 31 gives
$ 10819 = 31 \times 349 $.
Testing prime factors up to $\lfloor \sqrt{349} \rfloor = 18$ tells us 349 is prime.
(b) Trying prime factors 7, 73 and 109 gives
$ 55 699 = 7 \times 73 \times 109 $
(c) Trying prime factors 7, 97, and 193 gives
$ 131 047 = 7 \times 97 \times 193 $
Prove that for prime $p > 3$ we have
$$ (\frac{3}{p}) = \begin{cases} (\frac{p}{3}) & \text{ if } p \equiv 1 \pmod {4} \\ -(\frac{p}{3}) & \text{ if } p \equiv 3 \pmod {4} \end{cases}$$
We start with the result from the previous exercise. For distinct odd primes $p$ and $q$,
$$ (\frac{p}{q}) \times (\frac{q}{p}) = \begin{cases} 1 & \text{ if } p \equiv 1 \pmod {4} \text{ or } q \equiv 1 \pmod {4} \\ -1 & \text{ if } p \equiv q \equiv 3 \pmod {4} \end{cases}$$
Setting $q=3$, requires $p>3$ since $p$ and $q$ are odd and distinct. This gives
$$ (\frac{p}{3}) \times (\frac{3}{p}) = \begin{cases} 1 & \text{ if } p \equiv 1 \pmod {4} \\ -1 & \text{ if } p \equiv 3 \pmod {4} \end{cases}$$
We consider each case:
We have shown that for prime $p > 3$,
$$ (\frac{3}{p}) = \begin{cases} (\frac{p}{3}) & \text{ if } p \equiv 1 \pmod {4} \\ -(\frac{p}{3}) & \text{ if } p \equiv 3 \pmod {4} \end{cases}$$
Show that if $p$ and $q$ are distinct odd primes then
$$ (\frac{p}{q}) \times (\frac{q}{p}) = \begin{cases} 1 & \text{ if } p \equiv 1 \pmod {4} \text{ or } q \equiv 1 \pmod {4} \\ -1 & \text{ if } p \equiv q \equiv 3 \pmod {4} \end{cases}$$
We start with the Law of Quadratic Reciprocity.
$$ (\frac{p}{q}) \times (\frac{q}{p}) = (-1)^{\frac{p-1}{2} \times \frac{q-1}{2}} $$
We write the distinct odd primes $p$ and $q$ as $p=4m + s$ and $4n + t$, where $m,n$ are integers and $s,t$ can be one of 1 or 3.
This means
$$ (\frac{p}{q}) \times (\frac{q}{p}) = (-1)^{(2m+\frac{s-1}{2}) \times(2n+\frac{t-1}{2})} $$
The index of $(-1)$ is
$$ (2m+\frac{s-1}{2}) \times(2n+\frac{t-1}{2}) $$
This index is even when either or both $s=1$ or $t=1$. This corresponds to $p \equiv 1 \pmod 4$ or $q \equiv 1 \pmod 4$. An even index means $ (\frac{p}{q}) \times (\frac{q}{p}) = 1$.
The index is odd when both $s=3$ and $t=3$. This corresponds to $p \equiv 3 \pmod 4$ and $q \equiv 3 \pmod 4$. An odd index means $ (\frac{p}{q}) \times (\frac{q}{p}) = -1$.
We have shown that if $p$ and $q$ are distinct odd primes then
$$ (\frac{p}{q}) \times (\frac{q}{p}) = \begin{cases} 1 & \text{ if } p \equiv 1 \pmod {4} \text{ or } q \equiv 1 \pmod {4} \\ -1 & \text{ if } p \equiv q \equiv 3 \pmod {4} \end{cases}$$
Evaluate parts (c) and (d) of Example 7.19.
We want to determine
$$ (-1)^{(\frac{p-1}{2}) \times (\frac{q-1}{2})} $$
(c) $p \equiv 1 \pmod 4$ and $q \equiv 3 \pmod 4$
(d) $p \equiv 3 \pmod 4$ and $q \equiv 1 \pmod 4$
(c) We write $p=4x + 1$ and $q=4y+3$ for some integers $x,y$. And so
$$ (-1)^{(\frac{p-1}{2}) \times (\frac{q-1}{2})} = (-1)^{(2x) \times (2y+1)} = 1$$
because the index is even.
(d) We write $p=4x + 3$ and $q=4y+1$ for some integers $x,y$. And so
$$ (-1)^{(\frac{p-1}{2}) \times (\frac{q-1}{2})} = (-1)^{(2x+1) \times (2y)} = 1$$
because the index is even.
Determine which of the following congruences are solvable (all moduli are prime):
(a) $x^2 \equiv 12 \pmod {89}$
(b) $x^2 \equiv 40 \pmod {101}$
(c) $x^2 \equiv 36 \pmod {1223}$
(d) $x^2 \equiv 89 \pmod {197}$
(e) $x^2 \equiv 197 \pmod {89}$
(a) The Legendre Symbol tells us whether 12 is a quadratic residue of 89.
$$ (\frac{12}{89}) = (\frac{2^2}{89}) \times (\frac{3}{89}) = (1) \times (\frac{89}{3}) = (\frac{2}{3}) = -1 $$
And so $x^2 \equiv 12 \pmod {89}$ has no integer solutions.
(b) The Legendre Symbol tells us whether 40 is a quadratic residue of 101.
$$ (\frac{40}{101}) = (\frac{2^2}{101}) \times (\frac{2}{101}) \times (\frac{5}{101}) = (1) \times (-1) \times (\frac{101}{5}) = -(\frac{1}{5}) = -1 $$
And so $x^2 \equiv 40 \pmod {101}$ has no integer solutions.
(c) The Legendre Symbol tells us whether 36 is a quadratic residue of 1223.
$$ (\frac{36}{1223}) = (\frac{6^2}{1223}) = 1 $$
And so $x^2 \equiv 36 \pmod {1223}$ does have integer solutions.
(d) The Legendre Symbol tells us whether 89 is a quadratic residue of 197.
$$ (\frac{89}{197}) = (\frac{197}{89}) = (\frac{19}{89})= (\frac{89}{19}) = (\frac{13}{19}) = (\frac{19}{13}) = (\frac{6}{13}) = (\frac{2}{13}) \times (\frac{3}{13}) = (-1) \times (1) = -1$$
And so $x^2 \equiv 89 \pmod {197}$ has no integer solutions.
(e) The Legendre Symbol tells us whether 197 is a quadratic residue of 89.
$$ (\frac{197}{89}) = (\frac{19}{89}) = (\frac{89}{19}) = (\frac{13}{19}) = -1 $$
And so $x^2 \equiv 197 \pmod {89}$ has no integer solutions.
Note that we could have used the Law of Quadratic Reciprocity for this exercise.
$$ (\frac{197}{89}) \times (\frac{89}{197}) = (\frac{197}{89}) \times (-1) = (-1)^{\frac{89-1}{2} \times {\frac{197-1}{2}}} = (-1)^{44 \times 98} = 1 $$
And so $(\frac{197}{89})$ must be -1.
By using the Law of Quadratic Reciprocity find the first primitive root of the prime modulo 223. By using this primitive root, find the square root of $32 \pmod {223}$.
If $r$ is a primitive root of 223 the smallest $j$ such that $r^j \equiv 1 \pmod {223}$ is $j=\phi(223)=222$. We have
$$ r^{222} = 1 \pmod {223} $$
The factors of 222 are $1, 2, 3, 6, 37, 74, 111$, and are the only ones we need to test against candidate values for $r$.
However, recognising that 2, 3, 6 and 37 are factors of 74 and 111, we should test the larger 74 and 111 first to more efficiently determine whether a candidate value of $r$ is primitive or not. That is, if $r^{74} \equiv 1 \pmod {223}$ or $r^{111} \equiv 1 \pmod {223}$ then we don't need to test the smaller factors.
Let's try $r=2$. We want to evaluate $2^{111} \pmod {223}$. By Euler's Criterion $2^{\frac{223-1}{2}} \equiv 2^{111} \equiv 1 \pmod {223}$ if an only if $(\frac{2}{223})=1$. By Proposition (7.15) we have $ (\frac{2}{223}) = 1 $. And so $2^{111}\equiv 1 \pmod {223}$.
This means 2 is not a primitive root of 223.
Let's try $r=3$. We want to evaluate $3^{111} \pmod {223}$. By Euler's Criterion $3^{111} \equiv 1 \pmod {223}$ if and only if $(\frac{3}{223}) =1$. By the result of Exercise (7.3).3(i) we have $(\frac{3}{223}) = -1$. And so $3^{111} \not \equiv 1 \pmod {223}$.
Let's try $3^74$,
$$$ 3^{74} \equiv (3^2)^{37} \equiv (9^6)^6 \times 9 \equiv (32)^6 \times 9 \equiv 183 \pmod {223} $
And so $3^{37} \not \equiv 1 \pmod {223}$.
The following table shows the calculations for smaller factors of 222.
| j | 3^j | 3^j mod 223 |
| 1 | 3 | 3 |
| 2 | 9 | 9 |
| 3 | 27 | 27 |
| 6 | 729 | 60 |
Since none of these factors results in a congruence of 1 modulo 223, we conclude that 3 is indeed a primitive factor of 223.
We need to find $x$ such that
$$ x^2 \equiv 32 \pmod {223} $$
The following table of indices may help.
| n | a = 3^n | a = 3^n mod 223 |
| 1 | 3 | 3 |
| 2 | 9 | 9 |
| 3 | 27 | 27 |
| 4 | 81 | 81 |
| 5 | 243 | 20 |
| 6 | 729 | 60 |
| 7 | 2187 | 180 |
| 8 | 6561 | 94 |
| 9 | 19683 | 59 |
| 10 | 59049 | 177 |
| 11 | 177147 | 85 |
| 12 | 531441 | 32 |
| 13 | 1594323 | 96 |
We can read off that $3^{12} \equiv 32 \pmod {223}$. This means
$$ 3^{12} \equiv (\pm 3^6)^2 \equiv (\pm 60)^2 \equiv 32 \pmod {223} $$
And so the square roots of 32 are $60 \pmod {223}$ and $163 \pmod {223}$.
(Note we didn't use the fact that 3 is a primitive root of 223 to calculate the square roots more algebraically).