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