Proofs with primitive roots

Question

Please prove the following:

Let $m$ be a positive integer.

a) If a primitive root modulo $m$ exists, prove that the product of all positive integers not exceeding $m$ and relatively prime to $m$ is congruent to $-1$ modulo $m$.

b) What is the least nonnegative residue modulo $m$ of the product of all positive integers not exceeding $m$ and relatively prime to $m$, if no primitive root modulo $m$ exists?

Answer 1

For $(a),$

If $g$ is a primitive root, all positive integers not exceeding $m$ and relatively prime to $m$ will be $g^r, 1\le r\le \phi(m)$

So, the required product $$\equiv \prod_{1\le r\le \phi(m)}g^r=g^{\sum_{1\le r\le \phi(m)}r}=g^{\frac{\phi(m)(\phi(m)+1)}2}=\left(g^{\frac{\phi(m)}2}\right)^{\phi(m)+1}$$

Using this, $g^{\frac{\phi(m)}2}\equiv-1\pmod m$ as $g^{\frac{\phi(m)}2}\not\equiv1\pmod m$ as $g$ is a primitive root

and we know $\phi(m)$ is even for $m\ge3\implies\phi(m)+1$ is odd

Answer 2

First question: Let $g$ be a primitive root. Then we are being asked about the product $a_1\cdot a_2\cdots a_{\varphi(m)}$ of all numbers relatively prime to $m$.

If $i\ne j$, call $\{a_i,a_j\}$ a couple if $a_ia_j\equiv 1\pmod{m}$.

Note that the congruence $x^2\equiv 1\pmod{m}$ has $2$ solutions unless $m=1$ or $m=2$. For if $g^k$ is a solution, then $g^{2k}\equiv 1\pmod{m}$. It follows that $\varphi(m)$ divides $2k$, giving the two possibilities $k=\varphi(m)$ and $k=\varphi(m)/2$. If $m\gt 2$, these give distinct numbers.

Thus the only unpaired people are congruent to $1$ and $-1$. Pairs multiply to $1$ modulo $m$, and $1$ and $-1$ have product $-1$. The result follows.

Second question: We gave a slightly too long argument for the first question in order to prepare for the second. We will need to know that the numbers that do not have primitive roots look like. They are odd numbers that have more than one prime factor, powers of $2$ greater than $4$, and numbers divisible by $4$ and some odd prime.

Use a pairing argument similar to the previous one. The only interesting numbers are the unpaired ones, numbers $x$ such that $x^2\equiv 1$. We apply a pairing argument to these!

Note that solutions of $x^2\equiv 1\pmod{m}$ come in $\pm$ pairs. The product of such a pair is congruent to $-1$. We show there is an even number of $\pm$ pairs.

For $m$ of the form $2^k$, where $k\ge 3$, it is a standard result that there are $4$ solutions of the congruence $x^2\equiv 1\pmod{m}$, and hence $2$ $\pm$ pairs.

If $m$ is odd, and is divisible by $t$ distinct primes, where $t\gt 1$, then the number of solutions of the congruence $x^2\equiv 1\pmod{m}$ is $2^t$. For let $m$ have prime power factorization $m=p_1^{a_1}\cdots p_t^{a_t}$. Modulo each of the $p_i^{a_i}$, there are $2$ solutions, and any set of solutions modulo the $p_i$ can be spliced together with the Chinese Remainder Theorem. Thus the number of $\pm$ pairs is even if $t\gt 1$.

The same argument works for $m$ of the form $2^k b$, where $k\ge 2$ and $b$ is odd and greater than $1$.

Conclusion: Since there is an even number of pairs $\pm x$ such that $x^2\equiv 1\pmod{m}$, our product is congruent to $-1$ to an even power, that is, $1$ modulo $m$.