Exercise (6.3).20

Prove Proposition (6.11).

Let's remind ourselves of Proposition (6.11).

Let $\gcd (r, n) = 1$ and $r_1, r_2, r_3, \ldots , r_{\phi (n)}$ be integers relatively prime to $n$. If $r$ is a primitive root of $n$, then

$$ r, r^2, r^3, \ldots, r^{\phi(n)} $$

are congruent modulo $n$ to $r_1, r_2, r_3, \ldots , r_{\phi(n)}$ in some order.

Assuming the integers $r_1, r_2, r_3, \ldots , r_{\phi (n)}$ are pair-wise incongruent modulo $n$, then the set $\{ r_1, r_2, \ldots, r_{\phi(n)} \}$ is a reduced residue system modulo $n$.

We will first show the set $\{  r, r^2, r^3, \ldots, r^{\phi(n)} \}$ is also a reduced residue system modulo $n$. We need to show:

• the set has cardinality $\phi(n)$
• $\gcd(r^k, n)=1$ for $1 \le k \le \phi(n)$
• $r^j \not \equiv r^k \pmod n$ where $j \ne k$ for $1 \le j,k \le \phi(n)$

The set $\{  r, r^2, r^3, \ldots, r^{\phi(n)} \}$ clearly has cardinality $\phi(n)$.

We're given $\gcd(r,n)=1$, and so $\gcd(r^k,n)=1$ for any positive integer $k$, and in particular $1 \le k \le \phi(n)$.

To show $j \ne k \implies r^j \not \equiv r^k \pmod n$, we prove the contrapositive $r^j \equiv r^k \pmod n \implies j = k$.

Using Proposition (6.6) we have, noting that $r$ primitive means the order of $r$ modulo $n$ is $\phi(n)$,

$$r^j \equiv r^k \pmod n \quad \iff \quad j \equiv k \pmod {\phi(n)}$$

Since $1 \le j,k \le \phi(n)$, this means $j = k$.

And so the set $\{  r, r^2, r^3, \ldots, r^{\phi(n)} \}$ is also a reduced residue system modulo $n$

We now show that any two reduced residue systems modulo $n$ are congruent. That is, every element in one set is congruent to an element in the other, and vice versa.

We will do this by showing that any reduced residue system $X$ modulo $n$ is congruent to the reduced residue system of least positive residues $R$ modulo $n$. So we need to show both

1. for all $x \in X$, there is a congruent $r \in R$
2. for all $r \in R$, there is a congruent $x \in X$

(1) For every $x \in X$, using the division algorithm, we can write $x = r +kn$ where $r,k$ are integers and $0 \le s < n$. In fact the constraint is stronger $0 < r < n$ because $r=0$ would mean $x=kn$ which is not coprome to $n$. Here $r$ is the least positive residue of $x$ modulo $n$. Also, $x=r+kn$ means $x \equiv s \pmod n$, so $x$ is congruent to $r$. 

For $r$ to be a member of $R$ we also need to show $\gcd(r,n)=1$. Using the Lemma A, which we prove below, we can say $\gcd(x,n) = \gcd(x- kn, n)$ and so $\gcd(r,n) = 1$.

And so for every $x \in X$, there is a congruent $r$ in $R$.

(2) The argument is similar to (1) with the difference being that we use Lemma A to say $\gcd(r,n)=\gcd(r+kn,n)$ and so $\gcd(x,n)=1$.

By showing that any two reduced residue systems are congruent, we have shown that $\{  r, r^2, r^3, \ldots, r^{\phi(n)} \}$ is congruent to $\{ r_1, r_2, \ldots, r_{\phi(n)} \}$.

Lemma A

We will show that

$$ \boxed{ \gcd(x,n) = \gcd(x+kn,n) }$$

Let $g=\gcd(x,n)$ and $h=\gcd(x+kn,n)$. This gives us

$$ g \mid x, \quad g \mid n, \quad h \mid n, \quad h \mid x+kn $$

Here $g$ divides any linear combination of $x$ and $n$, and $h$ divides any linear combination of $n$ and $x+kn$. This gives us

$$ g \mid x + kn, \quad h \mid x $$

Together these facts give us

$$ g \mid  x+kn \land g \mid n \implies g \mid h $$

$$ h \mid  x \land h \mid n \implies h \mid g $$

And so we conclude $h=g$, that is,

$$ \gcd(x,n) = \gcd(x+kn,n) $$

Exercise (6.3).19

Let $p$ be prime and $\gcd (a, p) = 1$. Prove that $x^m \equiv a \pmod p$ has a solution if and only if a $a^{\frac{p-1}{g}} \equiv 1 \pmod p$ where $g = \gcd (m, p− 1)$.

We'll use Proposition (6.17) which states that if $n$ has a primitive root and $a$ and $n$ are 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.

Since $p$ is prime, it has a primitive root (stated on page 255, but proven later in the book). We're given $a$ and $p$ are relatively prime. And so the premises of Proposition (6,17) are satisfied. This means the conclusion that $x^m \equiv a \pmod p$ has a solution if and only if 

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

where $g=\gcd(m, \phi(p)) = \gcd(m, p-1)$.

The statement to be proven is simply Proposition (6.17) with $n$ as prime $p$.

Exercise (6.3).18

Let $r$ be a primitive root of an odd prime $p$. Prove that

$$ \text{ind}_r (p-1) = \frac{p-1}{2} $$

Since $r$ is a primitive root of $p$, and noting that $\phi(p)=p-1$, we have by definition

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

Lemma (4.3) tells us

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

However $r^{\frac{p-1}{2}} \equiv  1 \pmod p$ does not hold because $\phi(p)=p-1$ is the smallest index $k$ such that $r^k \equiv 1 \pmod p$, and $\frac{p-1}{2}$ is smaler thabn $p-1$. 

This leaves $ r^{\frac{p-1}{2}} \equiv  -1 \equiv p-1 \pmod p $ as the only possibility, and is equivalent to

$$ \text{ind}_r (p-1) = \frac{p-1}{2} $$

Exercise (6.3).17

Solve $x^{14} \equiv 27  \pmod {37}$ by using the primitive root 2 of modulo 37.

We are given that 2 is a primitive root modulo 37.

We prepare the following table of indices

ind_2(a) = n	2^n	a = 2^n mod 37
1	2	2
2	4	4
3	8	8
4	16	16
5	32	32
6	64	27
7	128	17
8	256	34
9	512	31
10	1024	25
11	2048	13
12	4096	26
13	8192	15
14	16384	30
15	32768	23
16	65536	9
17	131072	18
18	262144	36
19	524288	35
20	1048576	33
21	2097152	29
22	4194304	21
23	8388608	5
24	16777216	10
25	33554432	20
26	67108864	3
27	134217728	6
28	268435456	12
29	536870912	24
30	1073741824	11
31	2147483648	22
32	4294967296	7
33	8589934592	14
34	17179869184	28
35	34359738368	19
36	68719476736	1

Applying Proposition (6.15) and (6.16) to $x^{14} \equiv 27 \pmod {37}$ gives us

$$ 14 \times \text{ind}_2(x) \equiv \text{ind}_2(27) \pmod{36} $$

Using the table of indices, we have

$$ 14 \times \text{ind}_2(x) \equiv 6 \pmod{36} $$

This has solutions if $g=\gcd(36,14)=2$ divides 6, which it does. In fact there are $g=2$ incongruent solutions modulo 36.

Dividing by 2

$$ 7 \times \text{ind}_2(x) \equiv 3 \pmod{18} $$

We can't obtain $\text{ind}_2(x)$ directly, but we do notice that $7 \times 3 \equiv 21 \equiv 3 \pmod{18}$, and so the two incongruent solutions are $ \text{ind}_2(x) = 3$ and $ \text{ind}_2(x) = 21$ modulo 36.

From these, the table of indices gives us

$$ x \equiv 8 \pmod {37} \quad \text{ and } \quad x \equiv 29 \pmod {37} $$

Exercise (6.3).16

Show that 7 is a primitive root and use this to solve $7x^6 \equiv 6  \pmod {13}$.

Also find solutions to the non-linear Diophantine equation $7x^6 = 6 + 13y$.

The number 7 is a primitive root modulo 13 if the order of 7 modulo 13 is $\phi(13)=12$. Euler's Theorem tells us $7^{\phi(13)} \equiv 7^{12} \equiv 1 \pmod {13}$, and so we only need to test factors of 12, which are 1, 2, 3, 4, 6, 12.

n	7^n	7^n mod 13
1	7	7
2	49	10
3	343	5
4	2401	9
6	117649	12
12	13841287201	1

The above calculations show that the order of 7 modulo 13 is indeed $\phi(13)=12$, and so 7 is a primitive root modulo 13.

Before proceeding, we need to prepare a table of indices.

ind_7(a) = n	7^n	a = 7^n mod 13
1	7	7
2	49	10
3	343	5
4	2401	9
5	16807	11
6	117649	12
7	823543	6
8	5764801	3
9	40353607	8
10	282475249	4
11	1977326743	2
12	13841287201	1

Applying Propositions (6.15) and (6.16) to $7x^6 \equiv 6  \pmod {13}$ gives

$$  \text{ind}_7(7) + 6 \times \text{ind}_7 (x)  \equiv \text{ind}_7 (6)  \pmod {12} $$

Using the table of indices gives us 

$$  6 \times \text{ind}_7 (x)  \equiv 6  \pmod {12} $$

This has solutions if $g=\gcd(12,6)=6$ divides 6, which it does. In fact there are $g=6$ incongruent solutions.

Dividing through by 6

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

The 6 incongruent solutions modulo 12 are $\text{ind}_7(x) = 1, 3, 5, 7, 9, 11$.

The table of indices gives us

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

To solve  $7x^6 = 6 + 13y$, we know the form of $x$ and only need the form of $y$.

For $x = 2 + 13t$, for some integer $t$, $ y = \frac{7(2+13t)^6 - 6}{13} $.

For $x = 5 + 13t$, for some integer $t$, $ y = \frac{7(5+13t)^6 - 6}{13} $.

For $x = 6 + 13t$, for some integer $t$, $ y = \frac{7(6+13t)^6 - 6}{13} $.

For $x = 7 + 13t$, for some integer $t$, $ y = \frac{7(7+13t)^6 - 6}{13} $.

For $x = 8 + 13t$, for some integer $t$, $ y = \frac{7(8+13t)^6 - 6}{13} $.

For $x = 11 + 13t$, for some integer $t$, $ y = \frac{7(11+13t)^6 - 6}{13} $.

The author's solution only uses $t=0$, and these solutions are as follows

$$ (2, 34), \quad (5, 8413), \quad (6, 25122) $$

$$ (2, 63349), \quad (5, 141154), \quad (6, 953917) $$

Exercise (6.3).15

(a) Let $r$ be a primitive root modulo $n$. Show that if $a$ and $n$ are relatively prime then $1 \le \text{ind}_r (a) \le \phi (n)$.

(b) Prove Proposition (6.16) (c).

(a) Definition (6.12) tells us that if $r$ is a primitive root of $n$, and $\gcd(a,n)=1$, then the smallest positive index $k$ such that

$$ r^{k} \equiv 1 \pmod n $$

is called the index of $a$ relative to $r$, or $\text{ind}_r(a)$.

Since $k$ is the smallest positive index (non-zero), this means $1 \le k$.

By Euler's Theorem $r^{\phi(n)} \equiv 1 \pmod n$, and so $k \le \phi(n)$, because it is the smallest positive index satisfying the above congruence and so can't be larger than $\phi(n)$.

Combining these two facts gives us $1 \le k \le \phi(n)$, or

$$ 1 \le \text{ind}_r(a) \le \phi(n) $$

(b) Let's remind ourselves of Proposition (6.16)(c).

Let $r$ be a primitive root of $n$ and $\text{ind}_r(a)$ be the index of $a$ relative to $r$.

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

Let's first consider $\text{ind}_r(1)$,

$$ r^{\text{ind}_r(1)}  \equiv 1 \equiv r^0 \pmod n $$

By Proposition (6.6)

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

Now let's consider $\text{ind}_r(r)$

$$ r^{\text{ind}_r(1)}  \equiv r^1 \equiv r^0 \pmod n $$

By Proposition (6.6)

$$ \text{ind}_r(1) \equiv 1 \pmod {\phi(n)} $$

Exercise (6.3).14

(i) Show that 3 is a primitive root modulo 223 (223 is prime).

(ii) Solve the quadratic congruence

$$ x^2 \equiv 183 \pmod {223} $$

Find solutions to the Diophantine equation

$$ x^2 = 183 + 223y $$

(iii) Solve the cubic congruence

$$ x^3 \equiv -1 \pmod {223} $$

and the Diophantine equation

$$ x^3 + 1 = 223y$$

(i) We need to show the order of 3 modulo 223 is $\phi(223)=222$.

Because 223 is prime, we can use Euler's Theorem which tells us $3^{\phi(223)} \equiv 3^{222} \equiv 1 \pmod {223}$.

The order of 3 modulo 223 will be a factor of 222. These factors are 2, 3, 6, 37, 74, 111, 222, are the only indices of 3 we need to test. The following calculations show the order is not 2, 3 or 6.

n	3^n	3^n mod 223
2	9	9
3	27	27
6	729	60

The larger factors lead to numbers too large for a calculator so we need to calculate more indirectly.

For factor 37, we have

$$ 3^{37} \equiv (3^6)^6 \times 3 \equiv 60^6 \equiv 46656000000 \times 3 \equiv 210 \times 3 \equiv 184 \pmod {223}$$

For factor 74, we have

$$ 3^{74} \equiv (3^6)^{12} \times 3^2 \equiv 60^{12} \times 9 \equiv (60^4)^3 \times 9 \equiv 132^3 \times 9 \equiv 183 \pmod {223}$$

For factor 111, we have

$$ 3^{111} \equiv  (3^6)^{18} \times 3^3 \equiv 60^{18} \times 27 \equiv (136^3)^2 \times 27 \equiv 16^2 \times 27 \equiv 222 \pmod {223}$$

This leaves only 222 as the factor, and so the order of 3 modulo 223 is $\phi(223)=222$. 

This means 3 is a primitive root modulo 223.

(ii) We use Propositions (6.15) and (6.16) on $ x^2 \equiv 183 \pmod {223} $ to give

$$ 2 \; \text{ind}_3 (x) \equiv \text{ind}_3(183) \pmod {222} $$

By Proposition (3.16), this has a solution for $\text{ind}_3 (x)$ if $\gcd(222, 2)=2$ divides $\text{ind}_3(183)$. We have already seen that $3^{74} \equiv 183 \pmod {223}$, and so $\text{ind}_3(183) = 74$. We have $2 \mid 74$ which means there are solutions, in fact 2 incongruent solutions modulo 222.

Dividing through by 2 we have

$$ \text{ind}_3 (x) \equiv 37 \pmod {111} $$

This means the two incongruent solutions modulo 222 are $\text{ind}_3 (x) = 37$ and $\text{ind}_3(x) = 148$. We consider each in turn.

For $\text{ind}_3 (x) = 37$ we have

$$ x \equiv 3^{37} \equiv (3^6)^6 \times 3 \equiv 60^6 \times 210 \times 3 \equiv 184  \pmod {223} $$

For $\text{ind}_3 (x) = 148$ we have

$$ x \equiv 3^{148} \equiv (3^{37})^4 \equiv (184)^4 \equiv 39 \pmod {223} $$

So the two incongruent solutions are

$$ x \equiv 37 \pmod {223} \quad \text{ and } \quad x \equiv 184 \pmod {223}$$

To solve the Diophantine equation $ x^2 = 183 + 223y $ we know the form of $x$, and only need to determine $y$.

For $x = 39 + 223t$ for some integer $t$, 

$$ y = \frac{x^2 - 183}{223} = \frac{ (39+223t)^2 - 183 }{223} $$

And for $x = 184 + 223t$ for some integer $t$, 

$$ y = \frac{x^2 - 183}{223} = \frac{ (184+223t)^2 - 183 }{223} $$

So the solutions are of two forms,

$$ \biggl ( x = 39 + 223t, y = \frac{ (39+223t)^2 - 183 }{223} \biggr ) $$

$$ \biggl ( x = 184 + 223t, y = \frac{ (184+223t)^2 - 183 }{223} \biggr ) $$

Note: The author's solution only has specific solutions where $t=0$, namely $(39, 6)$ and $(184,151)$.

(iii) We use Propositions (6.15) and (6.16) on $ x^3 \equiv -1 \equiv 222 \pmod {223} $ to give

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

By Proposition (3.16), this has a solution for $\text{ind}_3 (x)$ if $\gcd(222, 3)=3$ divides $\text{ind}_3(222)$. We have already seen that $3^{111} \equiv 222 \pmod {223}$, and so $\text{ind}_3(222) = 111$. We have $3 \mid 111$ which means there are solutions, in fact 3 incongruent solutions modulo 222.

Dividing through by 3 we have

$$ \text{ind}_3 (x) \equiv 37 \pmod {74} $$

This means the three incongruent solutions modulo 222 are $\text{ind}_3 (x) = 37$, $\text{ind}_3(x) = 111$ and $\text{ind}_3(x) = 185$. We consider each in turn.

For $\text{ind}_3 (x) = 37$, from above we have

$$ x \equiv 3^{37} \equiv 184  \pmod {223} $$

For $\text{ind}_3 (x) = 111$, from above we have

$$ x \equiv (3^{37})^3 \equiv (184)^3 \equiv 222  \pmod {223} $$

For $\text{ind}_3 (x) = 185$, from above we have

$$ x \equiv (3^{37})^5 \equiv (184)^5 \equiv 40  \pmod {223} $$

So the three incongruent solutions are

$$ x \equiv 40 \pmod {223} \quad \text{ and } \quad x \equiv 184 \quad \text{ and } \equiv x \equiv 222  \pmod {223}$$

To solve the Diophantine equation $ x^3 + 1 = 223y$ we know the form of $x$, and only need to determine $y$.

For $x = 40 + 223t$ for some integer $t$, 

$$ y = \frac{x^3 + 1}{223} = \frac{(40+223t)^3 + 1}{223} $$

For $x = 184 + 223t$ for some integer $t$, 

$$ y = \frac{x^3 + 1}{223} = \frac{(184+223t)^3 + 1}{223} $$

For $x = 222 + 223t$ for some integer $t$, 

$$ y = \frac{x^3 + 1}{223} = \frac{(222+223t)^3 + 1}{223} $$

So the solutions are of three forms,

$$ \biggl ( x = 40 + 223t,  y =  \frac{(40+223t)^3 + 1}{223}  \biggr ) $$

$$ \biggl ( x = 184 + 223t,  y =  \frac{(184+223t)^3 + 1}{223}  \biggr ) $$

$$ \biggl ( x = 222 + 223t,  y =  \frac{(222+223t)^3 + 1}{223}  \biggr ) $$

Note: The author's solution only has specific solutions where $t=0$, namely $(40, 287)$, $(184,27935)$ and $(222,49063)$.

Exercise (6.3).13

Determine the number of incongruent solutions of:

(a) $x^3 ≡ 2 \pmod {29}$

(b) $x^{16} ≡ 25 \pmod {29}$

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) Since $\gcd(29,2)=1$ we can use Proposition (6.17). Noting that $\gcd(3, \phi(29))=1$, and by Euler's Theorem $2^{28} \equiv 1 \pmod {29}$, we have

$$ 2^{\frac{\phi(29)}{\gcd(3, \phi(29))}} \equiv 2^{\frac{28}{1}} \equiv 2^{28}  \equiv 1 \pmod {29}$$

And so the congruence has solutions, and in fact has 1 unique incongruent solution modulo 29.

(b) Since $\gcd(29,25)=1$ we can use Proposition (6.17). Noting that $\gcd(16,28)=4$, we have

$$ 25^{\frac{\phi(29)}{\gcd(16, \phi(29))}} \equiv 25^{\frac{28}{4}} \equiv (-4)^{7} \equiv -16384  \equiv 1 \pmod {29}$$

And so the congruence has solutions, and there are 4 unique incongruent solutions modulo 29.