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

Exercise (6.4).15

Prove that the product of all the incongruent primitive roots of a prime $p$ is congruent to $1 \pmod p$.

We proved this in the previous Exercise (6.4).13.

Exercise (6.4).14

Let $r$ be a primitive root modulo prime $p$. Prove that the multiplicative inverse of $r \pmod p$ is also a primitive root modulo $p$.

We proved this in the previous Exercise (6.4).13.

Exercise (6.4).13

The integers 2, 3, 10, 13, 14, and 15 are the primitive roots modulo 19.

Determine the least non-negative residue $x$ in the product

$$ x \equiv 2 \times 3 \times 10 \times 13 \times 14 \times 15 \pmod {19} $$

We could do this numerically but we'll try to make use of the fact the numbers are all the primitive roots modulo 19.

We will

• Step 1: Show that for every primitive root $a$ modulo prime $p$, the multiplicative inverse $a^{-1}$ is also a primitive root.
• Step 2: Show that a primitive root $a$ and its multiplicative inverse $a^{-1}$ are not congruent, $a \not \equiv a^{-1}$.
• Step 3: Pair up all the primitive roots $\{a, a^{-1}\}$ and show the product of each pair is congruent to 1, which means the product of all the primitive roots is congruent to 1. 

Step 1

Let $a$ be a primitive root modulo prime $p$, and $a^{-1}$ be the multiplicative inverse. Also, let $k$ be the order of $a^{-1}$. 

$$ (a^{-1})^k \equiv 1 \pmod p $$

Multiplying both sides by $a^k$,

$$ (a^{-1})^k \times a^k \equiv (a^{-1}a)^k \equiv 1 \equiv a^k \pmod p $$

The smallest $k$ such that $a^k \equiv 1 \pmod p$ is $\phi(p)$, and so $a^{-1}$ is also a primitive root modulo $p$. 

A multiplicative inverse of a primitive root $a$ exists because we can write $a^{\phi(p)} \equiv a \times a^{\phi(p)-1} \equiv 1 \pmod p$.

Step 2

Now let's consider $a \equiv a^{-1} \pmod p$. Multiplying both sides by $a$ gives

$$ a^2 \equiv a^{-1} \times a \equiv 1 \pmod p  $$

Since $p$ is prime, by proposition (3.14)

$$ a^2 \equiv1 \pmod p \iff a \equiv \pm 1 \pmod p $$

This is only true for primes $p=2$ and $p=3$. For prime $p=2$, the primitive root is $1 \equiv -1 \pmod 2$. For prime $p=3$, the primitive root is $2 \equiv -1 \pmod 3$.

For primes larger than 3, 1 is not a primitive roots because the order of 1 is 1 not $\phi(p)=p-1$. Similarly for primes larger than 3, the order of $-1 \equiv p-1$ is 2, not $\phi(p)=p-1$.

And so for primes $p>3$, a primitive root $a$ and its multiplicative inverse $a^{-1}$ are not congruent. 

Step 3

Since every primitive root $a$ modulo prime $p$ has an incongruent multiplicative inverse $a^{-1}$ that is also a primitive root, we can pair them all up as $\{a, a^{-1}\}$. The product of the elements of each pair, being inverses of each other, is congruent to 1. 

And so the product of all the primitive roots of a prime $p>3$ is 1.

Conclusion

We can use this result to conclude the product of the primitive roots of 19 is congruent to 1 modulo 19.

Numerical Calculation

Let's calculate the solution to verify our result above.

$$ \begin{align} x & \equiv 2 \times 3 \times 10 \times 13 \times 14 \times 15 \pmod {19} \\ \\ & \equiv 163800 \pmod {19} \\ \\ & \equiv 1 \pmod {19} \end{align} $$

Note: This solution was inspired by (link).

Exercise (6.4).12

Let $p$ be an odd prime of the form $p \equiv 1 \pmod 4$. Also let $r$ be a primitive root modulo $p$. Prove that $-r$ is also a primitive root of $p$.

We proved this as a lemma in the previous Exercise (6.4).11. We can interpret $p \equiv 1 \pmod 4$ as $\frac{p-1}{2}$ is even, using $p -1 = 4k \implies \frac{p-1}{2} = 2k$ for some integer $k$.

Exercise (6.4).11

The incongruent primitive roots modulo 17 are 3, 5, 6, 7, 10, 11, 12, and 14.

Determine the order of:

(a) $-3 \pmod {17}$

(b) $-5 \pmod {17}$

(c) $-6 \pmod {17}$

(d) $-7 \pmod {17}$

(e) $-10 \pmod {17}$

(f) $-11 \pmod {17}$

(g) $-12 \pmod {17}$

(h) $-14 \pmod {17}$

We note that the all the values are negations of known primitive roots. So we'll first prove a general lemma that.

Lemma. For prime $p$ where $\frac{p-1}{2}$ is even, if $a$ is a primitive root of $p$, then the order of $-a$ is $p-1$.

If $k$ is the order of $(-a)$, we have

$$ (-a)^k \equiv 1 \pmod p $$

We consider two cases for $k$, even and odd.

If $k$ is even, we have

$$ (-a)^k \equiv (a)^k \equiv 1 $$

Because $a$ is a primitive root, the smallest positive $k$ is $k=p-1$.

If $k$ is odd, we have

$$ ((-a)^k)^2 \equiv a^{2k}\equiv 1 \pmod p $$

Since $a$ is a primitive root, it must be that $p - 1 \mid 2k$, or equivalently $\frac{p-1}{2} \mid k$. But $\frac{p-1}{2}$ is even, and $k$ is odd. An even number cannot divide an odd number, and so we have a contradiction. This means $k$ even is not possible.

The only possibly case is $k$ even, and that leads to $k=p-1$, and so the order of $-a$ is $p-1$.

(a) Since 3 is a primitive root of prime 17, and since $\frac{17-1}{2}=8$ is even, then by the Lemma, the order of $-3$ is 16.

(b) Since 5 is a primitive root of prime 17, and since $\frac{17-1}{2}=8$ is even, then by the Lemma, the order of $-5$ is 16.

(c) Since 6 is a primitive root of prime 17, and since $\frac{17-1}{2}=8$ is even, then by the Lemma, the order of $-6$ is 16.

(d) Since 7 is a primitive root of prime 17, and since $\frac{17-1}{2}=8$ is even, then by the Lemma, the order of $-7$ is 16.

(e) Since 10 is a primitive root of prime 17, and since $\frac{17-1}{2}=8$ is even, then by the Lemma, the order of $-10$ is 16.

(f) Since 11 is a primitive root of prime 17, and since $\frac{17-1}{2}=8$ is even, then by the Lemma, the order of $-11$ is 16.

(g) Since 12 is a primitive root of prime 17, and since $\frac{17-1}{2}=8$ is even, then by the Lemma, the order of $-12$ is 16.

(h) Since 14 is a primitive root of prime 17, and since $\frac{17-1}{2}=8$ is even, then by the Lemma, the order of $-14$ is 16.

Exercise (6.4).10

Let $p$ (be an odd prime) of the form $p \equiv 3 \pmod 4$. Also let $r$ be a primitive root modulo $p$. Prove that $-r$ has order $\frac{p-1}{2}$.

We proved this as a lemma in order to solve the last Exercise (6.4).9. 

The only difference is that $p \equiv 3 \pmod 4$ means $p-1 = 2 + 4t$ for some integer $t$, that is $\frac{p-1}{2}=1+2t$, and so $\frac{p-1}{2}$ is odd, the assumption for the lemma we proved.

Exercise (6.4).9

The incongruent primitive roots modulo 19 are 2, 3, 10, 13, 14, and 15.

Determine the order of

(a) $-2 \pmod {19} $

(b) $-3 \pmod {19} $

(c) $-10 \pmod {19} $

(d) $-13 \pmod {19} $

(e) $-14 \pmod {19} $

(f) $-15 \pmod {19} $

We note that the all the values are negations of known primitive roots. So we'll first prove a general lemma that.

Lemma. For prime $p$ where $\frac{p-1}{2}$ is odd, if $a$ is a primitive root of $p$, then the order of $-a$ is $\frac{p-1}{2}$.

Since $a$ is a primitive root, $a^{p-1} \equiv 1 \pmod p$. Since $\frac{p-1}{2}$ is odd, it is an integer, so by Proposition (3.14)(b)

$$ a^{\frac{p-1}{2}} \equiv 1 \pmod p \quad \lor \quad  a^{\frac{p-1}{2}} \equiv -1 \pmod p $$

The first case is not possible because $a$ is a primitive root, and the smallest index $j$ such that $a^j \equiv 1 \pmod p$ is $j=p-1$. This leaves

$$ a^{\frac{p-1}{2}} \equiv -1 \pmod p $$

Multiplying both sides by $-1 = (-1)^{\frac{p-1}{2}}$ gives

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

This doesn't tell us the order of $-a$ as there could be a smaller positive integer $k$ such that $(-a)^k \equiv 1 \pmod p$. 

Assume $z$ is the order of $(-a)$. Then

$$ (-a)^z \equiv 1 \pmod p $$

Squaring

$$ a^{2z} \equiv 1 \pmod p $$

Since $a$ is a primitive root, $2z \ge p-1$, that is $z \ge \frac{p-1}{2}$. 

We have two facts:

• The order of $-a$ is greater than or equal to $\frac{p-1}{2}$.
• $ (-a)^{\frac{p-1}{2}} \equiv 1 \pmod p $

These two facts tell us the order of $-a \pmod p$ is $\frac{p-1}{2}$.

(a) Since 2 is a primitive root of prime 19, and since $\frac{19-1}{2}=9$ is odd, then by the Lemma, the order of $-2$ is 9.

(b) Since 3 is a primitive root of prime 19, and since $\frac{19-1}{2}=9$ is odd, then by the Lemma, the order of $-3$ is 9.

(c) Since 10 is a primitive root of prime 19, and since $\frac{19-1}{2}=9$ is odd, then by the Lemma, the order of $-10$ is 9.

(d) Since 13 is a primitive root of prime 19, and since $\frac{19-1}{2}=9$ is odd, then by the Lemma, the order of $-13$ is 9.

(e) Since 14 is a primitive root of prime 19, and since $\frac{19-1}{2}=9$ is odd, then by the Lemma, the order of $-14$ is 9.

(f) Since 15 is a primitive root of prime 19, and since $\frac{19-1}{2}=9$ is odd, then by the Lemma, the order of $-15$ is 9.

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