Exercise (6.4).8

Let $r_1$ and $r_2$ be incongruent primitive roots modulo $p$ where $p$ is an odd prime. Show that $r_1 \times r_2$ is not necessarily a primitive root modulo $p$.

We will show this with a counter-example.

We start with $r_1=2, r_2=3, p=5$, noting that 2 and 3 are both primitive roots of 5.

We now show that $r_1 \times r_2 = 6$ is not a primitive root of 5.

The following calculations show that 6 is not a primitive root of 5 because the smallest index of 6 such that the result is congruent to 1 is not $\phi(5)=4$.

n	2^n mod 5	3^n mod 5	6^n mod 5
1	2	3	1
2	4	4	1
3	3	2	1
4	1	1	1

We can also see this by noting that $6 \equiv 1 \pmod 5 \implies 6^n \equiv 1 \pmod 5$ for any positive integer $n$.

Exercise (6.4).7

Prove Proposition (6.18).

Let's 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$.

Since $r$ is a primitive root modulo $p$, then we know the least positive integer $k$ such that $r^k \equiv 1 \pmod p$ is $k=\phi(n)=p-1$.

Let's now consider the least positive integer $k$ such that $(r^m)^k \equiv 1 \pmod p$. 

$$ (r^m)^k \equiv r^{mk} \equiv 1 \pmod p $$

Since $p-1$ is the least positive index of $r$ to give a result congruent to 1, this means

$$ p - 1 \mid mk $$

If $\gcd(m,p-1)=1$ then $p-1 \not \mid m$ and so $p-1 \mid k$. The least positive $k$ for which this is true is $k=p-1$. 

This means the least positive integer $k$ such that $(r^m)^k \equiv 1 \pmod p$ is $k=p-1\phi(p)$, and so $r^m \pmod p$ is also a primitive root modulo $p$.

Note: the author's solution uses Corollary (6.9) which states that if $a$ modulo $n$ has order $k$, then $a^s$ has order $k$ if and only if $\gcd(s,k) =1$. Given the order of $r \pmod p$ is $p-1$, and since $\gcd(m, p-1)=1$, the corollary tells us $r^m$ has order $p-1$.

Exercise (6.4).6

Let $p$ be an odd prime. Prove that if $p \not \mid r$ and $r \not \equiv 1 \pmod p$ then

$$ 1 + r + r^2 + \ldots  + r^{p-3} + r^{p-2} \equiv 0 \pmod p $$

If $r \equiv 1 \pmod p$, then determine the least non-negative residue $x$ in

$$ 1 + r + r^2 + \ldots + r^{p-3} + r^{p-2} \equiv x \pmod p $$

We start by noting the geometric series formula

$$ 1 + r + r^2 + \ldots  + r^{p-3} + r^{p-2} = \frac{1-r^{p-1}}{1-r} $$

We want to avoid division, so we start by multiplying the series by $1-r \pmod p$, and noting Fermat's Little Theorem $r^{p-1} \equiv 1 \pmod p$ is applicable,

$$ (1 + r + r^2 + \ldots  + r^{p-3} + r^{p-2})(1-r)  \equiv 1 - r^{p-1} \equiv 0 \pmod p $$

Since we know $1-r \not \equiv 0 \pmod p$, it must be that the series is equivalent to $0$ modulo $p$, that is

$$ 1 + r + r^2 + \ldots  + r^{p-3} + r^{p-2} \equiv 0 \pmod p $$

If $r \equiv 1 \pmod p$, then

$$ 1 + r + r^2 + \ldots + r^{p-3} + r^{p-2} \equiv \overbrace{1 + 1 + 1 \ldots 1}^{(p-1)} \equiv p-1 \pmod p $$

So the least non-negative residue is $p-1$.

Exercise (6.4).5

Determine the least non-negative residues $x$ in the following:

(a) $x \equiv 1 + 2 + 2^2 + 2^3+2^4 + 2^5 \pmod 7$

(b) $x \equiv 1 + 3 + 3^2 + 3^3+3^4 + 3^5 \pmod 7$

(c)  $x \equiv 1 + 3 + 3^2 + 3^3 + 3^4 + 3^5+3^6 + 3^7 + 3^8 + 3^9 \pmod {11}$

(d) $x \equiv 1 + 2 + 2^2 + 2^3 + 2^4 + 2^5+2^6 + 2^7 + 2^8 + 2^9 + 2^{10} + 2^{11} \pmod {13}$

What do you notice about your results?

(a) We have

$$ \begin{align} x & \equiv 1 + 2 + 2^2 + 2^3+2^4 + 2^5 \pmod 7 \\ \\ & \equiv 1 + 2 + 4 + 1 + 2 + 4 \pmod 7 \\ \\ & \equiv 7 + 7 \pmod 7 \\ \\ & \equiv 0 + 0 \pmod 7 \\ \\ & \equiv 0 \pmod 7 \end{align} $$

(b) We have

$$ \begin{align} x & \equiv 1 + 3 + 3^2 + 3^3+3^4 + 3^5 \pmod 7 \\ \\ & \equiv 1 + 3 + 2 + 6 + 4 + 5 \pmod 7 \\ \\ & \equiv (6+1) + (5+2) + (4+3)  \pmod 7 \\ \\ & \equiv 0 + 0 +0 \pmod 7 \\ \\ & \equiv 0 \pmod 7 \end{align} $$

(c) We have

$$ \begin{align} x & \equiv 1 + 3 + 3^2 + 3^3 + 3^4 + 3^5+3^6 + 3^7 + 3^8 + 3^9  \pmod {11} \\ \\ & \equiv 1 + 3 + 9 + 5 + 4 + 1 + 3 + 9 + 5 + 4 \pmod {11} \\ \\ & \equiv (9 +1 + 1) + (3+3+5) + (4+9 + 5+4)  \pmod {11} \\ \\ & \equiv 11 + 11 + 22 \pmod {11} \\ \\ & \equiv 0 \pmod {11} \end{align} $$

(d) We have

$$ \begin{align} x & \equiv 1 + 2 + 2^2 + 2^3 + 2^4 + 2^5+2^6 + 2^7 + 2^8 + 2^9 + 2^{10} + 2^{11} \pmod {13} \\ \\ & \equiv 1 + 2 + 4 + 8 + 3 + 6 + 12 + 11 + 9 + 5 + 10 + 7 \pmod {13} \\ \\ & \equiv (12 + 1) + (11 + 2) + (8+5) + (9+4) + (10+3) + (6+7)  \pmod {13} \\ \\ & \equiv 0 + 0 + 0 + 0 + 0 +0 \pmod {13} \\ \\ & \equiv 0 \pmod {13} \end{align} $$

All the results are 0 modulo the given prime.

Exercise (6.4).4

Show that if $d$ is even then $(p− 1) \pmod p$ is a solution to

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

where $p$ is prime.

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 $d$ is even, we can write it as $d=2k$ for some integer $k$. And so

$$ x^{2k}  \equiv 1 \pmod p $$

We have $2k \mid p-1$ because $p-1$ is even, and so by Proposition (6.19) the congruence has $2k$ incongruent solutions.

Using $p-1 \equiv -1 \pmod p$, we have

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

Furthermore

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

That is, $(p-1)$ is a solution to $x^d -1 \equiv 0 \pmod p$. 

Exercise (6.4).3

Consider the congruence

$$ x^d - 1 \equiv  0 \pmod {19} $$

Solve this congruence for all $d$ which are the positive factors of $\phi(19)$.

What do you notice about your result when $d = \phi(19)$?

The positive factors of $\phi(19)=18$ are 1, 2, 3, 6, 9, 18. The congruences we need to solve are

(a) $ x^1 \equiv 1 \pmod {19} $

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

(c) $ x^3 \equiv 1 \pmod {19} $

(d) $ x^6 \equiv 1 \pmod {19} $

(e) $ x^9 \equiv 1 \pmod {19} $

(f) $ x^{18} \equiv 1 \pmod {19} $

From Exercise (6.3).7 we know that 2 is primitive root of 19. The following is a table of indices of root 2.

ind_2 (a)	a = 2^ind_r(a) mod 19
1	2
2	4
3	8
4	16
5	13
6	7
7	14
8	9
9	18
10	17
11	15
12	11
13	3
14	6
15	12
16	5
17	10
18	1

(a) Using Proposition (6.19), we have $1 \mid 18$, and so the congruence $ x^1 \equiv 1 \pmod {19} $ has 1 incongruent solution.

We can immediately see that $x \equiv 1 \pmod {19}$ is a solution.

(b) Using Proposition (6.19), we have $2 \mid 18$, and so the congruence $ x^2 \equiv 1 \pmod {19} $ has 2 incongruent solutions.

Applying Propositions (6.15) and (6.16) to the congruence gives

$$ 2 \times \text{ind}_r (x) \equiv 0 \pmod {18} $$

Simplifying

$$  \text{ind}_r (x) \equiv 0 \pmod {9} $$

This gives is $\text{ind}_r(a) \equiv 9,  18 \pmod {18}$.

The table of indices gives us the 2 incongruent solutions $x \equiv 1, 18  \pmod {19}$.

(c) Using Proposition (6.19), we have $3 \mid 18$, and so the congruence $ x^3 \equiv 1 \pmod {19} $ has 3 incongruent solutions.

Applying Propositions (6.15) and (6.16) to the congruence gives

$$ 3 \times \text{ind}_r (x) \equiv 0 \pmod {18} $$

Simplifying

$$  \text{ind}_r (x) \equiv 0 \pmod {6} $$

This gives is $\text{ind}_r(a) \equiv 6, 12,  18 \pmod {18}$.

The table of indices gives us the 3 incongruent solutions $x \equiv 1, 7, 11 \pmod {19}$.

(d) Using Proposition (6.19), we have $6 \mid 18$, and so the congruence $ x^6 \equiv 1 \pmod {19} $ has 6 incongruent solutions.

Applying Propositions (6.15) and (6.16) to the congruence gives

$$ 6 \times \text{ind}_r (x) \equiv 0 \pmod {18} $$

Simplifying

$$  \text{ind}_r (x) \equiv 0 \pmod {3} $$

This gives is $\text{ind}_r(a) \equiv 3, 6, 9, 12, 15, 18 \pmod {18}$.

The table of indices gives us the 6 incongruent solutions $x \equiv 1, 7, 8, 11, 12, 18 \pmod {19}$.

(e) Using Proposition (6.19), we have $9 \mid 18$, and so the congruence $ x^9 \equiv 1 \pmod {19} $ has 9 incongruent solutions.

Applying Propositions (6.15) and (6.16) to the congruence gives

$$ 9 \times \text{ind}_r (x) \equiv 0 \pmod {18} $$

Simplifying

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

This gives is $\text{ind}_r(a) \equiv 2, 4, 6, 8, 10, 12, 14, 16, 18 \pmod {18}$.

The table of indices gives us the 9 incongruent solutions $x \equiv 1, 4, 5, 6, 7, 9, 11, 16, 17 \pmod {19}$.

(f) Using Proposition (6.19), we have $18 \mid 18$, and so the congruence $ x^{18} \equiv 1 \pmod {19} $ has 18 incongruent solutions.

Applying Propositions (6.15) and (6.16) to the congruence gives

$$ 18 \times \text{ind}_r (x) \equiv 0 \pmod {18} $$

Simplifying

$$  \text{ind}_r (x) \equiv 0 \pmod {1} $$

This gives is $\text{ind}_r(a) \equiv 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 \pmod {18}$.

The table of indices gives us the 18 incongruent solutions $x \equiv  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18  \pmod {19}$.

When $d=\phi(19)=18$, Fermat's Little Theorem applies, where $a^{p-1} \equiv 1 \pmod p$ for prime $p$ and $\gcd(a,1)=1$.

Exercise (6.4).2

Solve the following congruences:

(a) $ x^3 \equiv 1 \pmod 7 $

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

(c) $ x^{11} \equiv 1 \pmod {23} $

We will use Proposition (6.19), a specialisation of Proposition (6.17) to prime modulo.

Let $p$ be prime and $d \mid (p-1)$. The congruence $x^d \equiv 1 \pmod p$ has exactly $d$ incongruent solutions.

(a) Using Proposition (6.19), we have $3 \mid 6$ and so the congruence $x^3 \equiv 1 \pmod 7$ has 3 incongruent solutions. 

We know from Exercise (6.4).1 that 3 is a primitive root of 7. We will use a table of indices of root 3.

ind_3 (a)	a = 3^ind_r(a) mod 7
1	3
2	2
3	6
4	4
5	5
6	1
7	3
8	2
9	6
10	4

Applying Propositions (6.15) and (6.16) to $x^3 \equiv 1 \pmod 7$ gives

$$ 3 \times \text{ind}_3(x) \equiv 0 \pmod 6 $$

Simplifying

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

This gives us $\text{ind}_3(x) \equiv 2, 4, 6$ as solutions. 

The table of indices gives us the 3 incongruent solutions $x \equiv 1, 2, 4 \pmod 7$.

(b) Using Proposition (6.19), we have $4 \mid 12$ and so the congruence $x^4 \equiv 1 \pmod {13}$ has $4$ incongruent solutions. 

We know from Example 6.19 that 2 is a primitive root of 13. We will use a table of indices of root 2.

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 Propositions (6.15) and (6.16) to $x^4 \equiv 1 \pmod {13}$ gives

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

Simplifying

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

This gives us $\text{ind}_2(x) \equiv 3, 6, 9, 12$ as solutions. 

The table of indices gives us the 4 incongruent solutions $x \equiv 1, 5, 8, 12 \pmod 13$.

(c) Using Proposition (6.19), we have $11 \mid2$ and so the congruence $x^11 \equiv 1 \pmod 7$ has 11 incongruent solutions. 

We know from Exercise (6.4).1 that 5 is a primitive root of 7. We will use a table of indices of root 5.

ind_5 (a)	a = 5^ind_r(a) mod 23
1	5
2	2
3	10
4	4
5	20
6	8
7	17
8	16
9	11
10	9
11	22
12	18
13	21
14	13
15	19
16	3
17	15
18	6
19	7
20	12
21	14
22	1

Applying Propositions (6.15) and (6.16) to $x^{11} \equiv 1 \pmod {23}$ gives

$$11 \times \text{ind}_5(x) \equiv 0 \pmod {22} $$

Simplifying

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

This gives us $\text{ind}_5(x) \equiv 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22$ as solutions. 

The table of indices gives us the11 incongruent solutions $x \equiv 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 \pmod {23}$.