Exercise (7.4).6

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.

Exercise (7.4).5

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 $

Exercise (7.4).4

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:

• If $p \equiv 1 \pmod 4$, then $ (\frac{p}{3}) \times (\frac{3}{p}) =1$. Since the Legendre Symbols can only be 1 or -1, this is only true if both are 1 or -1. That is $ (\frac{p}{3})= (\frac{3}{p}) $
• If $p \equiv 3 \pmod 4$, then $ (\frac{p}{3}) \times (\frac{3}{p}) =-1$. Since the Legendre Symbols can only be 1 or -1, this is only true if one is -1 and the other 1. That is $ (\frac{p}{3})= -(\frac{3}{p}) $

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

Exercise (7.4).3

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

Exercise (7.4).2

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.

Exercise (7.4).1

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.

Exercise (7.3).15

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