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