Exercise (6.3).12

Determine which of the following congruences are solvable:

(a) $x^3 \equiv 89 \pmod {197}$

(b) $x^2 \equiv 89 \pmod {197}$

(c) $x^2 \equiv 197 \pmod {89}$

(d) $x^2 \equiv 218 \pmod {111}$

We will be using Proposition (6.17). Let $n$ have a primitive root and $a$ and $n$ be relatively prime. The congruence $x^m \equiv a \pmod n$ has a solution if and only if $a^{\phi(n)/g} \equiv 1 \pmod n$ where $g = \gcd (m, \phi (n))$. Additionally, there are exactly $g$ incongruent solutions.

(a) We have $\gcd(89,197)=1$ so we can use Proposition (6.17), and also Euler's Theorem.

Euler's Theorem tells us $89^{\phi(197)} \equiv 1 \pmod {197}$, and noting $\gcd(3, 196)=1$, 

$$ 89^{\frac{\phi(197)}{\gcd(3,196)}}\equiv 89^{\frac{\phi(197)}{1}} \equiv 89^{\phi(197)} \equiv 1 \pmod {197}$$

By Proposition (6.17), the cubic congruence has a solution, and in fact has 1 incongruent solution modulo 197.

(b) We have $\gcd(89,197)=1$ so we can use Proposition (6.17), and also Euler's Theorem.

Euler's Theorem tells us $89^{\phi(197)} \equiv 1 \pmod {197}$, and noting $\gcd(2, 196)=2$, 

$$ 89^{\frac{\phi(197)}{\gcd(2,196)}}\equiv 89^{\frac{\phi(197)}{2}} \equiv 89^{98} \pmod {197}$$

Noting that:

• $89^2 \equiv 7921 \equiv 41 \pmod {197}$
• $41^7 \equiv 194754273881 \equiv 6 \pmod {197}$

$$ 89^{98} \equiv (89^2)^49 \equiv (41)^49 \equiv (41^7)^7 \equiv 6^7 \equiv 46656 \equiv -1 \pmod {197}$$

And so $89^{98} \not \equiv 1 \pmod{197}$, which means the given congruence has no solutions.

(c) We have $\gcd(89,197)=1$ so we can use Proposition (6.17), and also Euler's Theorem.

Euler's Theorem tells us $197^{\phi(89)} \equiv 1 \pmod {89}$, and noting $\gcd(2,88)=2$, 

$$ 197^{\frac{\phi(89)}{\gcd(2,88)}} \equiv 197^{\frac{88}{2}} \equiv 197^{44} \pmod {89} $$

Noting that:

• $ 197^2 \equiv 38809 \equiv 5 \pmod {89} $
• $ 5^{11} \equiv 48828125 \equiv 55 \pmod {89} $

$$ 197^{44} \equiv (197^2)^{22} \equiv 5^{22} \equiv (5^{11})^2 \equiv 55^2 \equiv -1 \pmod {89} $$

And so $197^{44} \not \equiv 1 \pmod {89}$, which means the given congruence has no solutions.

(d) We can simplify the congruence by noting that $218 \equiv -4 \pmod {111}$, and so

$$ x^2 \equiv 218 \equiv -4 \pmod {111} $$

We have $\gcd(111, 218)=1$ so we can use Proposition (6.17), and also Euler's Theorem.

Euler's Theorem tells us that $(-4)^{\phi(111)} \equiv 1 \pmod {111}$, and noting $\gcd(2,72)=2$,

$$ (-4)^{\frac{72}{2}} \equiv (-4)^{36} \pmod {111} $$

Noting that $ (-4)^9 \equiv -262144 \equiv 38 \pmod {111} $,

$$ (-4)^{36} \equiv ((-4)^9)^4 \equiv 38^4 \equiv 2085136 \equiv 1 \pmod {111} $$

This means $(-4)^{72} \equiv 218^{72} \equiv 1$ and so the congruence has 2 solutions.

Note: Proposition (6.17) requires $n$ to have a primitive root. Primes have primitive roots but this isn't covered until later in the book. The author's solutions don't show that $n$ has a primitive root.

Exercise (6.3).11

Determine the integers $a$ such that $1 \le a \le 16$ and $ax^6 \equiv 8 \pmod {17}$ has solutions.

We re-use the table of indices from Exercise (6.3).8, using as a primitive root modulo 17.

a mod 17	ind_3(a)
1	16
2	14
3	1
4	12
5	5
6	15
7	11
8	10
9	2
10	3
11	7
12	13
13	4
14	9
15	6
16	8

We use Propositions (6.15) and (6.16) on $ax^6 \equiv 8 \pmod {17}$ to give

$$ \begin{align} \text{ind}_3 (a)+  6 \; \text{ind}_3 (x)  & \equiv \text{ind}_3 (8) \pmod {\phi(17)} \\ \\   6 \; \text{ind}_3 (x)  & \equiv 10 - \text{ind}_3 (a) \pmod {16}  \end{align} $$

For this linear congruence to have a solution, we $\gcd(16, 6)=2$ must divide $10 - \text{ind}_3 (a)$.

The following table shows these calculations for $1 \le a \le 16$.

a mod 17	Ind_3(a)	10 – ind_3(a) mod 2
1	16	0
2	14	0
3	1	1
4	12	0
5	5	1
6	15	1
7	11	1
8	10	0
9	2	0
10	3	1
11	7	1
12	13	1
13	4	0
14	9	1
15	6	0
16	8	0

We can see the values of $1 \le a \le 16$ such that $ax^6 \equiv 8 \pmod {17}$ has solutions are

$$ a = 1, 2, 4, 8, 9, 13, 15, 16 $$

Exercise (6.3).10

Use this table of the primitive root 2 of 13 to answer the questions below.

a mod 13	Ind_2(a)
1	12
2	1
3	4
4	2
5	9
6	5
7	11
8	3
9	8
10	10
11	7
12	6

(a) Solve the congruence $7^x \equiv 3 \pmod {13}$.

(b) Find the least non-negative remainder after $5^{100} × 7^{50} × 9^{99}$ is divided by 13.

(c) Determine the integers $1 \le a \le 12$ such that $x^a \equiv 9 \pmod {13}$ has no solutions.

(a) We use Propositions (6.15) and (6.16) on $7^x \equiv 3 \pmod {13}$ to give

$$ \begin{align} x \; \text{ind}_2 (7)  & \equiv \text{ind}_2 (3) \pmod {\phi(13)} \\ \\  11x & \equiv 4 \pmod {12}  \end{align} $$

Since $g=\gcd(12,11)=1$ and $g \mid 4$, this linear congruence has 1 unique solution modulo 12. 

Testing values of $x$ from 1 to 15 gives us the solution $x \equiv 8 \pmod {12}$.

(b) We need to find the least positive $x$ such that

$$ 5^{100} × 7^{50} × 9^{99} \equiv x \pmod {13} $$

We use Propositions (6.15) and (6.16) on $5^{100} × 7^{50} × 9^{99} \equiv x \pmod {13} $ to give

$$ \begin{align} 100 \; \text{ind}_2 (5)  + 50 \; \text{ind}_2 (7)  + 99 \; \text{ind}_2 (9)& \equiv \text{ind}_2 (x) \pmod {12} \\ \\  100(9) + 50(11) + 99(8) & \equiv \text{ind}_2 (x) \pmod {12}  \\ \\ \text{ind}_2 (x) & \equiv 10 \pmod{12} \end{align} $$

The table of indices gives us $x=10$. And so 10 is as the least positive remainder after $5^{100} × 7^{50} × 9^{99}$ is divided by 13.

(c) We use Propositions (6.15) and (6.16) on $x^a \equiv 9 \pmod {13}$ to give

$$ \begin{align} a \; \text{ind}_2 (x)  & \equiv \text{ind}_2 (9) \pmod {\phi(13)} \\ \\  a \; \text{ind}_2 (x) & \equiv 8 \pmod {12}  \end{align} $$

For the linear congruence not to have a solution, we require $g \not \mid 8$ where $g = \gcd(12,a)$. 

The following calculations show for which $1 \le a \le 12$, the $\gcd(12,a)$ does not divide 8.

a	gcd(12,a)	8 mod gcd(12,a)
1	1	0
2	2	0
3	3	2
4	4	0
5	1	0
6	6	2
7	1	0
8	4	0
9	3	2
10	2	0
11	1	0
12	12	4

So the values of $a$ which lead to $x^a \equiv 9 \pmod {13}$ having no solutions, are $a=3, 6, 9, 12$.

Exercise (6.3).9

By using the table you established in the previous question, determine the least non-negative residue $x$ such that

$$ 7^{100}6^{100} \equiv x \pmod {17} $$

The table of indices was calculated as follows.

a mod 17	ind_3(a)
1	16
2	14
3	1
4	12
5	5
6	15
7	11
8	10
9	2
10	3
11	7
12	13
13	4
14	9
15	6
16	8

(a) We use Propositions (6.15) and (6.16) on $7^{100}6^{100} \equiv x \pmod {17}$ to give

$$ \begin{align} 100 \; \text{ind}_3 (7) + 100\text{ind}_3(6) & \equiv \text{ind}_3 (x) \pmod {\phi(17)} \\ \\  100(11 + 15) & \equiv \text{ind}_3 (x) \pmod {16} \\ \\ 2600 & \equiv \text{ind}_3 (x) \pmod {16} \\ \\ \text{ind}_3 (x) & \equiv 8 \pmod{16} \end{align} $$

Using the table of indices, we conclude the least non-negative residue $x$ is 16.

Exercise (6.3).8

Show that 3 is a primitive root modulo 17. Complete the following table:

a mod 17	ind_3(a)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Solve the following equations:

(a) $x^4 \equiv 4 \pmod {17}$

(b) $12x^8 \equiv 5 \pmod {17}$

(c) $12x^8 \equiv 6 \pmod {17}$

(d) $5^x \equiv 3 \pmod {17}$

The table of indices is calculated as follows. It confirms that 3 is a primitive root modulo 17 because the order of 3 modulo 17 is $\phi(17)=16$.

a mod 17	ind_3(a)
1	16
2	14
3	1
4	12
5	5
6	15
7	11
8	10
9	2
10	3
11	7
12	13
13	4
14	9
15	6
16	8

(a) We use Propositions (6.15) and (6.16) on $x^4 \equiv 4 \pmod {17}$ to give

$$ \begin{align} \text{ind}_3 (x^4) & \equiv \text{ind}_3 (4) \pmod {\phi(17)} \\ \\  4 \; \text{ind}_3 (x) & \equiv 12 \pmod {16}  \end{align} $$

Since $g = \gcd(16,4)=4$ and $g \mid 12$, this linear congruence has 4 incongruent solutions modulo 16.

Dividing through by 4

$$ \text{ind}_3 (x) \equiv 3 \pmod {4} $$

The four solutions modulo 16 are $\text{ind}_3(x) = 3, 7, 11, 15$. The table gives us the general solution for $x$,

$$ x \equiv  10, 11, 7, 6 \pmod {17} $$

(b) We use Propositions (6.15) and (6.16) on $12x^8 \equiv 5 \pmod {17}$ to give

$$ \begin{align} \text{ind}_3 (12x^8) & \equiv \text{ind}_3 (5) \pmod {\phi(17)} \\ \\ 13 +  8 \; \text{ind}_3 (x) & \equiv 5 \pmod {16} \\ \\  8 \; \text{ind}_3 (x) & \equiv 8 \pmod {16}   \end{align} $$

Since $g = \gcd(16,8)=8$ and $g \mid 8$, this linear congruence has 8 incongruent solutions modulo 16.

Dividing through by 8

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

The 8 solutions modulo 16 are $\text{ind}_3(x) = 1, 3, 5, 7, 9, 11, 13, 15$. The table gives us the general solution for $x$,

$$ x \equiv 3, 10, 5, 11, 14, 7, 12, 6 \pmod {17} $$

(c) We use Propositions (6.15) and (6.16) on $12x^8 \equiv 6 \pmod {17}$ to give

$$ \begin{align} \text{ind}_3 (12x^8) & \equiv \text{ind}_3 (6) \pmod {\phi(17)} \\ \\ 13 +  8 \; \text{ind}_3 (x) & \equiv 15 \pmod {16} \\ \\  8 \; \text{ind}_3 (x) & \equiv 2 \pmod {16}   \end{align} $$

Since $g = \gcd(16,8)=8$ but $g \not \mid 2$, this linear congruence has no solutions.

(d) We use Propositions (6.15) and (6.16) on $5^x \equiv 3 \pmod {17}$ to give

$$ \begin{align} x \; \text{ind}_3 (5) & \equiv \text{ind}_3 (3) \pmod {\phi(17)} \\ \\ 5x & \equiv 1 \pmod {16} \end{align} $$

Since $g = \gcd(16,5)=1$ and $g \mid 1$, this linear congruence has 1 incongruent solution modulo 16.

Testing values between 1 and 15 gives us the solution

$$ x \equiv 13 \pmod{16} $$

Exercise (6.3).7

Assume that 2 is a primitive root of modulo 19. Solve the following:

(a) $6x^5 \equiv 7 \pmod {19}$

(b) $4x^9 \equiv 4 \pmod {19}$

(c) $x^6 \equiv 7 \pmod {19}$

We start by building a table of indices and the corresponding reduced residue system.

ind_2(a)	a = 2^(ind_2) 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) We use Propositions (6.15) and (6.16)  on $6x^5 \equiv 7 \pmod {19}$ to give

$$ \begin{align} \text{ind}_2 (6x^5) & \equiv \text{ind}_2 (7) \pmod {\phi(19)} \\ \\  \text{ind}_2 (6) +  5\;\text{ind}_2 (x) & \equiv \text{ind}_2 (7) \pmod {18} \\ \\ 5\;\text{ind}_2 (x) &  \equiv 10 \pmod {18} \end{align} $$

Since $g = \gcd(18,5)=1$ and $g \mid 10$, this linear congruence has 1 incongruent solution modulo 18.

Dividing through by 5

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

This has one solution $\text{ind}_2 = 2$. The table gives us the general solution for $x$,

$$ x \equiv 4 \pmod {19} $$

(b) We use Propositions (6.15) and (6.16)  on $4x^9 \equiv 4 \pmod {19}$ to give

$$ \begin{align} \text{ind}_2 (4) + 9\; \text{ind}_2 (x) & \equiv \text{ind}_2(4) \pmod {\phi(19)} \\ \\  9\; \text{ind}_2 (x) & \equiv 0  \pmod {18} \end{align} $$

Since $\gcd(18,9)=9$ and $g \mid 0$, there are 9 incongruent solutions modulo 18.

Dividing through by 9

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

The nine solutions modulo 18 are $\text{ind}_2 (x) = 0, 2, 4, 6, 8, 10, 12, 14, 16$. The tables of indices gives us the solutions for $x$,

$$ x \equiv 1, 4, 16, 7, 9, 17, 11, 6, 5 \pmod {19} $$

(c) We use Propositions (6.15) and (6.16)  on $x^6 \equiv 7 \pmod {19}$ to give

$$ \begin{align} 6 \; \text{ind}_2 (x) & \equiv \text{ind}_2 (7) \pmod {\phi(19)} \\ \\  6 \; \text{ind}_2 (x) & \equiv 6 \pmod {18)} \end{align} $$

Since $\gcd(18,6)=6$ and $g \mid 6$, there are 6 incongruent solutions modulo 18.

Dividing through by 6

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

The six solutions modulo 18 are $\text{ind}_2 (x) = 1, 4, 7, 10, 13, 16$. The table of indices gives us the solutions for $x$,

$$ x \equiv 2, 16, 14, 17, 3, 5 $$

Exercise (6.3).6

Determine a primitive root modulo 11.

By using this primitive root, solve the following congruence equations:

(a) $2x^4 \equiv 7 \pmod {11}$

(b) $3x^2 \equiv 5 \pmod {11}$

(c) $5x^5 \equiv 6 \pmod {11}$

We'll use Proposition (6.15): Let $r$ be a primitive root of $n$

$$ a \equiv b \pmod n \quad \implies \quad \text{ind}_r (a) = \text{ind}_r (b)$$

We'll also use Proposition (6.16): Let $r$ be a primitive root of $n$ and $\text{ind}_r (a)$ be the index of $a$ relative to $r$. Then we have the following results:

(a) $\text{ind}_r (ab) ≡ \text{ind}_r (a) + \text{ind}_r (b) \pmod {\phi (n)}$

(b) $\text{ind}_r (ak) ≡ k \; \text{ind}_r(a) \pmod {\phi (n)}$

(c) $\text{ind}_r (1) ≡ 0 \pmod {\phi (n)}$ and $\text{ind}_r (r) ≡ 1 \pmod {\phi (n)}$

---

The following calculations show that 2 is a primitive root of 11.

n	2^n	2^n mod 11
2	4	4
5	32	10
10	1024	1

The following table shows the reduced residue system for 11, and the index for each residue. We can read, for example, the index of 8 relative to 2 is 3, modulo 11.

ind_2(a)	a ≡ 2^(ind_2) mod 11
1	2
2	4
3	8
4	5
5	10
6	9
7	7
8	3
9	6
10	1

(a) Applying Proposition (6.15) to $2x^4 \equiv 7 \pmod {11}$ gives us

$$ \text{ind}_2(2x^4) = \text{ind}_2(7) $$

And then using Proposition (6.16)

$$ \begin{align} \text{ind}_2(2) + 4\;\text{ind}_2(x)  & \equiv \text{ind}_2(7) \pmod{10} \\ \\ 4\;\text{ind}_2(x)  & \equiv \text{ind}_2(7)  - \text{ind}_2(2) \pmod{10}  \end{align}$$

The table of indices above gives us $ \text{ind}_2(2) = 1$ and $ \text{ind}_2(7)=7$, and so

$$ 4 \; \text{ind}_2(x)  \equiv 6  \pmod{10}$$

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

By Proposition (3.10), we can divide through by 2, changing the modulo to $\frac{10}{\gcd(2,10)}$,

$$ 2 \; \text{ind}_2(x)  \equiv  3 \equiv 8 \pmod{5}$$

And again, dividing through by 2, 

$$  \text{ind}_2(x)  \equiv  4  \pmod{5}$$

And so the two solutions are $\text{ind}_2(x) = 4$ and  $\text{ind}_2(x)= 9$. The table of indices resolves these to

$$ x \equiv  5 \pmod {11} \quad \text{and} \quad x \equiv 6 \pmod {11}$$

The following calculations show the equation $2x^4 \equiv 7 \pmod {11}$ is valid for a selection of $x \equiv 5 \pmod {11}$ and $x \equiv 6 \pmod {11}$.

x eq 5 mod 11	2x^4 mod 11		x eq 6 mod 11	2x^4 mod 11
5	7		6	7
16	7		17	7
27	7		28	7
38	7		39	7
49	7		50	7
60	7		61	7

(b) Applying Proposition (6.15) to $3x^2 \equiv 5 \pmod {11}$ gives us

$$ \text{ind}_2(3x^2) = \text{ind}_2(5) $$

And then using Proposition (6.16)

$$ \begin{align} \text{ind}_2(3)+ 2\; \text{ind}_2(x) & \equiv \text{ind}_2(5) \pmod {10}\\ \\  2\; \text{ind}_2(x) & \equiv 6  \pmod {10} \end{align}$$

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

Dividing through by 2,

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

And so the two solutions are $\text{ind}_2(x) = 3$ and $x \equiv =8$. The table of indices resolve these to

$$ x \equiv  3 \pmod {11} \quad \text{and} \quad x \equiv 8 \pmod {11}$$

(c) Applying Proposition (6.15) to $5x^5 \equiv 6 \pmod {11}$ gives us

$$ \text{ind}_2(5x^5) = \text{ind}_2(6) $$

And then using Proposition (6.16)

$$ \begin{align} \text{ind}_2(5)+ 5\; \text{ind}_2(x) & \equiv \text{ind}_2(6) \pmod {10}\\ \\  5\; \text{ind}_2(x) & \equiv 5  \pmod {10} \end{align}$$

Since $g = \gcd(10,5)=5$ and $g \mid 5$, this linear congruence has 5 incongruent solutions modulo 10.

Dividing through by 5,

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

And so the five solutions are $\text{ind}_2(x) = 1, 3, 5, 7, 9$. The table of indices resolve these to

$$ x \equiv 2, 8, 10, 7, 6 \pmod {11} $$

Exercise (6.3).5

Show that 7 is not a primitive root modulo 19.

We remind ourselves of Definition (6.10) which states that if $a \pmod n$ has order $\phi (n)$ then $a$ is called a primitive root modulo $n$ or just a primitive root of $n$.

We first note that $\gcd(7,19)=1$ and so the order exists. The order is a factor of $\phi(19)=18$. These factors are 1, 2, 3, 6, 9, 18 and are the only ones we need to test.

The following calculations show the order of $7 \pmod {19}$ is 3.

n	7^n	7^n mod 19
2	49	11
3	343	1

Because 3 is not $\phi(19)=18$, we conclude that 7 is not a primitive root.

Exercise (6.3).4

Show that 5 is a primitive root modulo 49.

We remind ourselves of Definition (6.10) which states that if $a \pmod n$ has order $\phi (n)$ then $a$ is called a primitive root modulo $n$ or just a primitive root of $n$.

We first note that $\gcd(5,49)=1$ and so the order exists. The order is a factor of $\phi(49)=42$. These factors are 1, 2, 3, 6, 7, 14, 21, 42, and are the only ones we need to test.

The following calculations show the order of $5 \pmod {49}$ is not 2, 3, 6, 7 or 14.

n	5^n	5^n mod 49
2	25	25
3	125	27
6	15625	43
7	78125	19
14	6103515625	18

The numbers grow too large for factors 21 and 42, so we use an indirect calculation.

For factor 21, 

$$ 5^{21} \equiv (5^7)^3 \equiv 19^3 \equiv 6859 \equiv 48 \pmod {49} $$

For factor 42,

$$ 5^{42} \equiv (5^{14})^3 \equiv 18^3 \equiv 6832 \equiv 1 \pmod {49} $$

And so the order of 5 modulo 49 is 42.

Because the order is $\phi(49)=42$, we conclude that 5 is a primitive root modulo 49.

Exercise (6.3).3

Show that 2 is a primitive root modulo 9.

We remind ourselves of Definition (6.10) which states that if $a \pmod n$ has order $\phi (n)$ then $a$ is called a primitive root modulo $n$ or just a primitive root of $n$.

We first note that $\gcd(2,9)=1$ and so the order exists. The order is a factor of $\phi(9)=6$. These factors are 1, 2, 3, 6, and are the only ones we need to test.

The following calculations show the order of $2 \pmod 9$ is 6.

n	2^n	2^n mod 9
2	4	4
3	8	8
6	64	1

Because the order is $\phi(9)=6$, we conclude that 2 is a primitive root modulo 9.

Exercise (6.3).2

Determine which of the following numbers are a primitive root of 11:

(a) 3 (b) 5 (c) 7

We remind ourselves of Definition (6.10) which states that if $a \pmod n$ has order $\phi (n)$ then $a$ is called a primitive root modulo $n$ or just a primitive root of $n$.

(a) Since $\gcd(3,11)=1$, the order exists.

The order is a factor of $\phi(11)=10$. These factors are 1, 2, 5, 10, and are the only ones we need to test.

The following calculations show the order of $3 \pmod {11}$ is 5.

n	3^n	3^n mod 11
2	9	9
5	243	1
10	59049	1

The order is not $\phi(11)=10$, and so 3 is not a primitive root of 11.

(b) Since $\gcd(5,11)=1$, the order exists.

The order is a factor of $\phi(11)=10$. These factors are 1, 2, 5, 10, and are the only ones we need to test.

The following calculations show the order of $5 \pmod {11}$ is 5.

n	5^n	5^n mod 11
2	25	3
5	3125	1
10	9765625	1

The order is not $\phi(11)=10$, and so 5 is not a primitive root of 11.

(c) Since $\gcd(7,11)=1$, the order exists.

The order is a factor of $\phi(11)=10$. These factors are 1, 2, 5, 10, and are the only ones we need to test.

The following calculations show the order of $7 \pmod {11}$ is 10.

n	7^n	7^n mod 11
2	49	5
5	16807	10
10	282475249	1

The order is $\phi(11)=10$, and so 7 is a primitive root of 11.

Exercise (6.3).1

Determine which of the following numbers are a primitive root of 7:

(a) 3 (b) 5

We remind ourselves of Definition (6.10) which states that if $a \pmod n$ has order $\phi (n)$ then $a$ is called a primitive root modulo $n$ or just a primitive root of $n$.

(a) Since $\gcd(3,7)=1$ then the order exists.

Here $\phi(n)=6$. The order of 3 is a factor of $\phi(n)=6$. These factors are 1,2, 3, 6. These are the only ones we need to test.

The following calculations show the order of 3 is 6 modulo 7.

n	3^n	3^n mod 7
2	9	2
3	27	6
6	729	1

Since the order is also $\phi(7)=6$, then 3 is a primitive root of 7.

(b) Since $\gcd(5,7)=1$ then the order exists.

Here $\phi(n)=6$. The order of 5 is a factor of $\phi(n)=6$. These factors are 1,2, 3, 6. These are the only ones we need to test.

The following calculations show the order of 5 is 6 modulo 7.

n	5^n	5^n mod 7
2	25	4
3	125	6
6	15625	1

Since the order is also $\phi(7)=6$, then 5 is a primitive root of 7.

Exercise (6.2).16

Find the order of $2 \pmod {1001}$.

We first check $\gcd(1001, 2)=1$ which means the order exists.

The order is a factor of $\phi(1001)=720$. These factors are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 30, 36, 40, 45, 48, 60, 72, 80, 90, 120, 144, 180, 240, 360, 720. 

The following tables shows calculations for the first few factors, and shows the order is not one of the factors between 2 and 36.

n	2^n	2^n mod 1001
2	4	4
3	8	8
4	16	16
5	32	32
6	64	64
8	256	256
9	512	512
10	1024	23
12	4096	92
15	32768	736
16	65536	471
18	262144	883
20	1048576	529
24	16777216	456
30	1073741824	155
36	68719476736	911

We need undertake the calculations more indirectly, as follows, making use of these previous results

$$ 2^{40} \equiv (2^{10})^4 \equiv (23)^4 \equiv 562 \pmod {1001} $$

$$ 2^{45} \equiv (2^9)^5 \equiv (512)^5 \equiv 967 \pmod {1001} $$

$$ 2^{48} \equiv (2^{12})^4 \equiv (92)^4 \equiv 729 \pmod {1001} $$

$$ 2^{60} \equiv (2^{30})^2 \equiv (155)^2 \equiv 1 \pmod {1001} $$

And so the order of 2 modulo 1001 is 60.

Exercise (6.2).15

Determine the least positive index $x$ such that $4^x − 1$ is divisible by 83.

We need the order of 4 modulo 83, which is the least positive index of 4 congruent to 1 modulo 83.

We note $\gcd(4,83)=1$, so the order exists.

The order is a factor of $\phi(83)=82$. These factors are 1, 2, 41, 82, and these are the only ones we need to test.

The magnitudes grow rapidly large so we need to calculate indirectly, as follows.

Noting that:

• $4^2 \equiv 16 \pmod {83}$
• $16^4 \equiv 49 \pmod {83}$

we have

$$ 4^{41} \equiv (4^2)^20 \times 4 \equiv (16)^20 \times 4 \equiv (16^4)^5 \times 4 \equiv (49)^5 \times 4 \equiv  1129900996 \equiv 1 \pmod {83}$$

So the least positive index $x$ such that $4^x -1$ is divisible by 83 is 41.

Exercise (6.2).14

(a) Determine the order of $81 \pmod {105}$.

(b) Determine the order of $81 \pmod {106}$.

(a) Since $\gcd(81,105)=3 \ne 1$, the order does not exist.

(b) Since $\gcd(81, 106)=1$, the order of 81 modulo 105 exists.

Noting that $81=3^4$, we'll work in base 3, and first find the order of $3 \pmod {106}$. The order is a factor of $\phi(106)=52$. These factors are 1, 2, 4, 13, 26, 52, and these are the only ones we need to test.

The following calculations show that the order of $3 \pmod {106}$ is not 2, 4 or 13. The numbers become too large for testing factors 26 and 52.

n	3^n	3^n mod 106
2	9	9
4	81	81
13	1594323	83

Let's try a different approach.

$$ 3^{26} \equiv (3^{13})^2 \equiv (83)^2 \equiv 6889 \equiv 105 \pmod {106} $$

So 26 is not the order of 3 modulo 106.

$$ 3^{52} \equiv (3^{13})^4 \equiv (83)^4 \equiv 47458321 \equiv 1 \pmod {106} $$

So the order of 3 modulo 106 is 52.

The Order Formula (6.8) tells us that if $k$ is the order of $a \pmod n$, then the order of $a^s \pmod n$ is $k / \gcd(s,k)$. And so the order of $81 \pmod {106}$ is $52 / \gcd(4,52) = 52/4 = 13$.

The order of $81 \pmod {106}$ is 13.