Exercise (6.4).22

(a) The prime 61 has 2 as a primitive root. Find all the primitive roots of 61.

(b) Show that the quadratic Diophantine equation $x^2 = r + 61y$, where $r$ is a primitive root of 61, has no solutions.

(c) Show that the quadratic Diophantine equation $x^2 = r + py$, where $p$ is an odd prime and $r$ is a primitive root, has no solutions.

(a) We remind ourselves of Proposition (6.18)

Let $r$ be a primitive root modulo $p$ where $p$ is prime. Then $r^m \pmod p$ is also a primitive root modulo $p$, provided $\gcd (m, p-1) = 1$.

There are $\phi(60)=12$ numbers $m$ coprime to 60, and they are $m=1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59$. The following table calculates $2^m \pmod 61$ for $m$ up to 31.

m	2^m	2^m mod 61
1	2	2
7	128	6
11	2048	35
13	8192	18
17	131072	44
19	524288	54
23	8388608	10
29	536870912	30
31	2147483648	59

For larger values of $m$ we need to calculate indirectly.

For $m=37$,

$ 2^{37} \equiv 2^{31} \times 2^6 \equiv 59 \times 64 \equiv 55 \pmod {61}$

For $m=41$, 

$ 2^{41} \equiv 2^{31} \times 2^{10} \equiv 59 \times 1024 \equiv 26 \pmod {61}$

For $m=43$, 

$ 2^{43} \equiv 2^{31} \times 2^{12} \equiv 59 \times 4096 \equiv 43 \pmod {61}$

For $m=47$, 

$ 2^{47} \equiv 2^{43} \times 2^{4} \equiv 43 \times 16 \equiv 17 \pmod {61}$

For $m=49$, 

$ 2^{49} \equiv 2^{47} \times 2^{2} \equiv 17 \times 4 \equiv 7 \pmod {61}$

For $m=53$, 

$ 2^{53} \equiv 2^{49} \times 2^{4} \equiv 7 \times 16 \equiv 51 \pmod {61}$

For $m=59$, 

$ 2^{59} \equiv 2^{53} \times 2^{6} \equiv 51 \times 64 \equiv 21 \pmod {61}$

And so the primitive roots of 61 are

$$ 2, 6, 7, 10, 17, 18, 26, 30, 31, 35, 43, 44, 51, 54, 55, 59 $$

(b) Solving  $x^2 = r + 61y$ is equivalent to solving  $x^2 = r  \pmod {61}$,

Applying Propoositions (6.15) and (6.16) to  $x^2 = r \pmod {61}$ we have

$$ 2\text{ind}_r \equiv 1 \pmod {60} $$

Here $g=\gcd(60,2)=2$ does not divide 1, and so the linear congruence has no solutions. This means $x^2 = r + 61y$ has no integer solutions.

(c) Solving  $x^2 = r + py$ is equivalent to solving  $x^2 = r  \pmod {p}$,

Applying Propoositions (6.15) and (6.16) to  $x^2 = r \pmod {61}$ we have

$$ 2\text{ind}_r \equiv 1 \pmod {p-1} $$

Again, $g=\gcd(p-1,2) = 2$ and does not divide 1, and so the linear congruence has no solutions. This means $x^2 = r + py$ has no integer solutions.

Exercise (6.4).21

Solve the non-linear Diophantine equation

$$ x^6 = 1 + 13y $$

The solutions for $x$ are the solutions to the congruence

$$ x^6 \equiv 1 \pmod {13} $$

We know 2 is a primitive root of prime 13. The following is a table of indices.

ind_2 (a)	a = 2^ind_r(a) mod 13
1	2
2	4
3	8
4	3
5	6
6	12
7	11
8	9
9	5
10	10
11	7
12	1

Applying Propoositions (6.15) and (6.16) to $ x^6 \equiv 1 \pmod 13 $ gives

$$ 6 \times \text{ind}_2(x \equiv 0 \pmod {12} $$

Since $g=\gcd(12,6)=6$ divides 0, the linear congruence has solutions, and in fact gas $g=6$ incongruent solutions modulo 12.

Dividing by 6 gives

$$ \text{ind}_2(x) \equiv 0 \pmod 2 $$

This gives us $\text{ind}_2(x) \equiv 2, 4, 6, 8, 10, 12 \pmod {12}$. Using the table of indices above gives us

$$ x \equiv 1, 3, 4,  9, 10, 12 \pmod {13} $$

Using $y=\frac{x^6-1}{13}$ gives us the corresponding values for $y$, and so the solutions are

$$ (x,y) \quad = \quad (1,0), \; (3,56), \; (4,315), \; (9,40880), \; (10,76923), \; (12,229691)   $$

Exercise (6.4).20

Prove Wilson’s Theorem (4.4) by using a primitive root of a prime:

If $p$ is prime then 

$$ (p - 1)! \equiv -1 \pmod p $$

Since $p$ is prime, by Proposition (6.22) we know it has a primitive root, which we can call $r$,

We know from Proposition (6.11) that the set

$$ \{ r^1, r^2, r^3, \ldots, r^{p-2}, r^{p-1} \} $$

is congruent modulo $p$ to the set

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

And so

$$ (p-1)! \equiv (p-1) \times (p-2) \times (p-3) \times \ldots \times 3 \times  2 \times 1  \pmod p $$

is congruent to

$$ r^1 \times r^2  \times r^3 \times \ldots \times r^{p-2} \times r^{p-1} \pmod p  $$

Which gives us

$$ \begin{align} (p-1) ! & \equiv r^{1 + 2 + 3 \ldots + (p-2) + (p-1) }  \pmod p \\ \\ & \equiv r^{\frac{(p-1)p}{2}} \pmod p  \end{align} $$

Fermat's Little Theorem tells us $r^{p-1} \equiv 1 \pmod p$.  We now consider two cases for $p$, odd and even.

Odd $p$

For odd $p$, we must have $r^{\frac{p-1}{2}} \equiv -1$ since $r$ is a primitive root and no smaller index than $p-1$ of $r$ can be congruent to 1 modulo $p$. Using $p$ is odd, $(-1)^p \equiv -1 \pmod p$, and so

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

Even $p$

Here $p=2$, and so we have the trivial case of 

$$ (p-1)! \equiv (2-1)! \equiv 1 \equiv -1 \pmod p   $$

Both cases conclude with Wilson's Theorem

$$ (p - 1)! \equiv -1 \pmod p $$

Exercise (6.4).19

Prove that the solutions $a$ of FlT (4.1) belong to the reduced residue system modulo $p$ where $p$ is prime:

If $a^{p−1} \equiv 1 \pmod p$ then $p \not \mid a$.

Assuming $a$ is an integer, and $p$ is prime, then to prove

$$ a^{p-1} \equiv 1 \pmod p \quad \implies \quad \ p \not \mid a $$

we can prove the logically equivalent contrapositive

$$  \ p \mid a \quad \implies \quad a^{p-1} \not  \equiv 1 \pmod p $$

If $p \mid a$, then for some integer $k$, we have $a = pk$. And so,

$$ a^{p-1} \equiv (pk)^{p-1} \equiv 0 \not \equiv 1 \pmod p $$

This is because any multiple of any power of $p$ is a multiple of $p$ and so congruent to zero modulo $p$.

By proving the contrapositive, we have shown that if $a^{p−1} \equiv 1 \pmod p$ then $p \not \mid a$.

For values of $a$ less than $p$, because $p$ is prime, the values of $a$ are by definition elements of the reduced residue system modulo $p$.

Exercise (6.4).18

Prove Proposition (6.19).

Hint: Use Lagrange’s Theorem:

Let $P(x) = c_m x^m + c_{m−1}x^{m−1} + \ldots + c_1x + c_0$ where $c_m \not \equiv 0 \pmod p$ and $p$ is prime. Then polynomial congruence $P (x) \equiv 0 \pmod p$ has at most m incongruent solutions.

Let's remind ourselves of Proposition (6.19). 

Let $p$ be prime and $d \mid (p− 1)$. The congruence

$$ x^d \equiv 1 \pmod p $$

has exactly $d$ incongruent solutions.

Since $p$ is prime, we know it has a primitive root, which we can call $r$. Applying Propositions (6.15) and (6.16) to $x^d \equiv 1 \pmod p$ gives

$$ d \times \text{ind}_r(x) \equiv 0 \pmod {p-1} $$

This linear congruence has solutions for $\text{ind}_r(x)$ if $g=\gcd(p-1,d)=d$ divides 0, which it does. There are $g=d$ incongruent solutions modulo $p-1$.

This means there are $d$ incongruent solutions for $x$ modulo $p-1$.

We can extend this to say there are $d$ incongruent solutions for $x$ modulo $p$, because we know $x \not \mid p$.

Note: The author's solution uses Lagrange's Theorem because it doesn't assume that all primes have a primitive root.

Exercise (6.4).17

(i) Show that 2 is a primitive root modulo 243.

(ii) Solve the quadratic congruence

$$ x^2 \equiv 82 \pmod {243} $$

[Note 243 is composite.]

(i) Since $243=3^5$ and 2 are co-prime, we can use Euler's Theorem which tells us

$$ 2^{\phi(243)} \equiv 1 \pmod {243} $$

We can calculate $\phi(243)$ as $ \phi(243) = \phi(2=3^5) = 3^{5-1}(3-1) = 162$, and so

$$ 2^{162} \equiv 1 \pmod {243} $$

This means the order of 2 modulo 243 divides 162. The factors of 162 are 1, 2, 3, 6, 9, 18, 27, 54, 81, 162. 

The following calculations show the order of 2 is not 1, 2, 3, 6, 9, 18 or 27.

n	2^n	2^n mod 243
1	2	2
2	4	4
3	8	8
6	64	64
9	512	26
18	262144	190
27	134217728	80

The larger factors 54 and 81 require an indirect calculation.

Testing factor 54,

$$ 2^{54} \equiv(2^{27})^2 \equiv 80^2 \equiv 6400 \equiv 82 \pmod {243} $$

Testing factor 81,

$$ 2^{81} \equiv (2^{27})^3 \equiv 80^3 \equiv 512000 \equiv 242 \pmod p $$

This leaves the factor $\phi(243)=162$ as the order of 2 modulo 243, and so 2 is a primitive root of 243.

(ii) Applying Propositions (6.15) and (6.16) to $x^2 \equiv 82 \pmod {243}$, and using the above calculation for factor 54, gives

$$ 2 \times \text{ind}_2(x) \equiv \text{ind}_2(82) \equiv 54 \pmod {162}  $$

Since $g=\gcd(162,2)=2$ divides 54, the linear congruence has 2 incongruent solutions. 

Dividing by two,

$$ \text{ind}_2(x) \equiv \text{ind}_2(82) \equiv 27 \pmod {81}  $$

The two solutions are $\text{ind}_2 \equiv 27$ and $\text{ind}_2 \equiv 108$ modulo 162.

The corresponding solutions for $x$ are $x \equiv 80 \pmod {243}$ and $x \equiv 80^4 \equiv 163 \pmod {243}$.

Exercise (6.4).16

(i) Show that 3 is a primitive root modulo $F_3 = 2^{2^3} + 1$ ($F_3$ is a Fermat prime).

(ii) Solve the quadratic congruence $x^2 \equiv −1 \pmod {F_3}$.

[The square roots of $-1 \mod {F_3}$.]

(i) If 3 is a primitive root of prime $F_3 = 2^{2^3} + 1$, then the order of 3 modulo $F_3 = 257$ is $\phi(257) = 256$.

Euler's Theorem tells us that $3^{256} \equiv 1$, and so the order of 3 must divide 256. The factors of 256 are 1, 2, 4, 8, 16, 32, 64, 128, 256. 

The following table shows the order of 3 is not 1, 2, 4, 8, 16 or 32. 

n	3^n	3^n mod 257
1	3	3
2	9	9
4	81	81
8	6561	136
16	43046721	249
32	1853020188851841	64

Larger factors are not feasible to test directly, so we do so indirectly.

Testing factor 64, 

$$ 3^{64} \equiv  (3^{32})^2 \equiv 64^2 \equiv 4096 \equiv 241 \pmod {257}$$

Testing factor 128,

$$ 3^{128} \equiv  (3^{64})^2 \equiv 241^2 \equiv 58081 \equiv 256 \pmod {257}$$

This leaves only the factor $\phi(F_3)=256$ as the order of 3 modulo $F_3$.

And so 3 is a primitive root of $F_3=2^{2^3}+1$. 

(ii) Applying Propositions (6.15) and (6.16) to $x^2 \equiv −1 \pmod {F_3}$ gives us

$$ 2 \times \text{ind}_3(x) \equiv \text{ind}_3(−1) \pmod {\phi(F_3)} $$

Using $256 \equiv -1 \pmod 257$, and $\text{ind}_3(256)=128$, 

$$ 2 \times \text{ind}_3(x) \equiv 128 \pmod {256} $$

Since $g=\gcd(256,2)=2$ and $g \mid 128$, this linear congruence has $g=2$ incongruent solutions modulo 256.

Dividing by 2,

$$ \text{ind}_3(x) \equiv 64 \pmod {128} $$

We have solutions $\text{ind}_3(x)=64$ and $\text{ind}_3(x)=192$. This gives us $x \equiv 241 \pmod {257}$ and $x \equiv 241 \times 256 \equiv 16 \pmod {257}$

So the two square roots of $-1$ are 16 and 241 modulo $F_3$.