[Math] Proofs with primitive roots

elementary-number-theoryprimitive-roots

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?

Best Answer

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

Related Question