Suppose that $p>3$ is prime. Prove that the products of the primitive roots of $p$ between $1$ and $p-1$ is congruent to $1$ modulo $p$.
Problem
Source:
Tags: algebra, polynomial, modular arithmetic, Primitive Roots
TomciO
25.05.2007 03:24
Just note that if $g$ is primitive root then $\frac{1}{g}$ is a primitive root as well. Because $-1$ can't be a primitive root (since the order of $-1$ is 2) the conclusion follows.
mavropnevma
19.01.2011 01:51
Alternatively, if $g$ is a primitive root, then all the other primitive roots are $g^k$, with $\gcd(p-1,k) = 1$ (there are $\varphi(p-1)$ of them), so their product is \[\prod_{\gcd(p-1,k) = 1} g^k = g^{\sum_{\gcd(p-1,k) = 1} k}.\] Since $\gcd(p-1,k) = 1$ if and only if $\gcd(p-1,p-1-k) = 1$, it follows that $\sum_{\gcd(p-1,k) = 1} k = \dfrac {1} {2} (p-1) \varphi(p-1)$, a multiple of $p-1$ (since $p>3$, it follows $\varphi(p-1)$ is even), hence the product is equal to $1$. To be punctilious, the above post states that $-1$ cannot be a primitive root (without in so many words referencing the given condition $p>3$); othervise $g$ and $\dfrac {1} {g}$will be the same element (to wit, $-1$).
me@home
19.01.2011 09:23
It is well known that $(\mathbb{Z}/p\mathbb{Z})^{\times}\equiv C_{p-1}$
Represent $C_{p-1}=\{1,a,\cdots,a^{p-2}\}$ for some arbitrary generator $a$ (we treat $a$ as an element in $\mathbb{F}_p$ when we refer to multiplication at the end of the proof).
Clearly, the set of primitive roots can be expressed as:
\[ S=\{a^n| (n,p-1)=1\} \]
(in particular, $|S|=\phi(p-1)$)
Then, the original question is to compute \[\prod_{s\in S}s\]
Indeed, we use the existence of a handy involution to do so.
Define an involution $f:S\to S$ to take the element $a^n$ to $a^{p-1-n}$. This is well-defined since $(n,p-1)=1\iff (n,p-1-n)=1$. Furthermore, this involution has no fixed points.
Indeed, the only possible fixed point is $\frac{p-1}{2}$. However, we can see that \[a^{\frac{p-1}{2}}\not\in S\]
Because $p>3$, $\frac{p-1}{2}>1$. Thus, $\left(\frac{p-1}{2},p-1\right)=\frac{p-1}{2}>1$, so by the definition of $S$, $a^{\frac{p-1}{2}}\not\in S$.
Thus, $f$ induces a partition of $S$ into pairs of the form $\{s,f(s)\}$. We compute as follows:
\[\prod_{s\in S}s=\prod_{\text{pairs}}s\cdot f(s)=\prod a^n\cdot a^{p-1-n}=\prod a^{p-1}=\prod 1=1\]
This yields the requested result.
ZetaX
30.01.2011 12:43
Another fancy way (which is much more justified at the question asking for their sum) is to see that the number in question is the constant coefficient of the cyclotomic polynomial $\Phi_{p-1}$.
AnonymousBunny
15.09.2014 22:05
)
Note that $g$ is a primitive root $\pmod{p}$ iff $g^m \equiv g^n \pmod{p} \iff m \equiv n \pmod{p-1}$. Now,
\[(g^{-1})^m \equiv (g^{-1})^n \pmod{p} \iff g^{-m} \equiv g^{-n} \pmod{p} \\ \iff -m \equiv -n \pmod{p-1} \iff m \equiv n \pmod{p-1},\]
so $g^{-1}$ is a primitive root modulo $p$ as well.
), so we just pair up the primitive roots with their inverses. The only exceptions are 1 and -1, which are their own inverses, but fortunately they aren't primitive roots $\pmod{p}$ for $p>3.$
H.HAFEZI2000
08.05.2020 20:41
let $g$ be a primitive root of $p$ then we shall assert that $g^{-1}$ is also a primitive root, assume that $(g^{-1})^x \equiv 1 \mod p$ that $x<p-1$ $(g)^x(g^{-1})^x \equiv g^x \equiv 1 \mod p$ which is a contradiction so $x=p-1$ and $g^{-1}$ is also a primitive root. thereupon because $(g^{-1})^{-1} =g$ and $g \not\equiv \pm 1$, it follows the the conclusion straightly!