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