Let $p>3$ be a prime number. Prove that the product of all primitive roots between 1 and $p-1$ is congruent 1 modulo $p$.
Problem
Source: VI International Festival of Young Mathematicians Sozopol, Theme for 10-12 grade
Tags: number theory, Primitive Roots
11.01.2020 19:13
Let $g$ be a primitive root modulo $p$. A basic observation is that the set of all primitive roots modulo $p$ is $\{g^k:(k,p-1)=1\}$. To see this, suppose $g^{kd}\equiv 1\pmod{p}$. Since $g$ is a primitive root, this yields $p-1\mid kd$. In particular if $(p-1,k)=1$, then $p-1\mid d$ is obtained, implying $g^k$ is indeed a primitive root. Conversely, taking $k=\frac{p-1}{(k,p-1)}$ in case $(p-1,k)>1$ yields in this case $g^k$ is not a primitive root. Hence, the product of all primitive roots modulo $p$ are of form $g^N$ where $N=\sum_{k:(k,p-1)=1}k$. Now, observe that the set $S=\{k:(k,p-1)=1\}$ can be partitioned into (disjoint) pairs of form $(k,p-1-k)$: indeed $(k,p-1)=1\iff (p-1-k,p-1)=1$, and $k=p-1-k$ iff $k=(p-1)/2$ which is not coprime with $p-1$. Hence, $\sum_{k:(k,p-1)=1} k = (p-1)\varphi(p-1)/2$ where $\varphi(n)$ is Euler's function. But since $p>3$, $\varphi(p-1)/2$ is an integer, hence $g^N\equiv 1\pmod{p}$ by Fermat's theorem.
11.01.2020 19:24
Note that if $r$ is a primitive root, then so is $r^{-1}$, and $r \not \equiv r^{-1} \pmod{p}$ for $p>3$, hence we're done.
28.03.2021 05:35
ubermensch wrote: Note that if $r$ is a primitive root, then so is $r^{-1}$, and $r \not \equiv r^{-1} \pmod{p}$ for $p>3$, hence we're done. Lol of previous solution