Product of three primitive roots mod prime number

294 Views Asked by At

Let $p$ be a prime number, and let $a,b,c$ be primitive roots mod $p$ (repetitions allowed). Is it true, in general, that $a\cdot b\cdot c$ is a primitive root?

I have proved that $ab$ cannot be a primitive root mod $p$. I have also tried a few numerical calculations, each showing that the statement is true.

2

There are 2 best solutions below

2
On BEST ANSWER

Given a number $a$ of multiplicative order $n$, so that $a^n \equiv 1 \pmod p$ but $a^{\ell} \not \equiv 1 \pmod p$ for positive $\ell < n$, then we know the orders of powers of $a$.

In particular, the order of $a^k$ is $\frac{n}{\gcd(n,k)}$.

To explain the comment from lulu, if you choose a primitive root $g$ for a prime $p \equiv 1 \pmod 3$, say $p = 3m + 1$, then the order of $g$ is $3m$. And so the order of $g^3$ is $m$. So clearly $g^3$ is not a primitive root in this case.


Requiring the three primitive roots to be distinct is not enough. For instance, $2,3,14$ are all primitive roots mod $19$ but their product is $8$, which is $2^3$ (and which is not a primitive root by the first part of this answer).

I didn't know if this should be true or not, so I wrote a quick program to find primitive roots and test their products.

0
On

The theorem that the product of any $3$ distinct primitive roots $\pmod p$ for $p$ prime is always a primitive root $\pmod p$ is true only when $p$ has exactly $4$ primitive roots or when $p$ is a Fermat prime.

The part about $4$ primitive roots follows because the product of all primitive roots $\equiv 1\pmod p$ unless $p=3$, in which case there is an odd number of primitive roots. Thus the product of any $3$ distinct primitive roots is the multiplicative inverse of the remaining primitive root, and so is itself a primitive root.

The part about Fermat primes holds because every quadratic nonresidue $\pmod F$ is a primitive root for any Fermat prime $F$, and the product of $3$ nonresidues is a nonresidue.

For the rest, if $q\mid\phi(p-1)$ for some prime $q\ge7$ then we can find $0<i<j<k<q$ such that $i+j+k\equiv0\pmod q$, hence $3$ primitive roots $\pmod p$ whose product is not a primitive root. For example, if $p=29$ then $p-1=28=4\cdot7$. Now, $1+2+4\equiv0\pmod7$, so start with a primitive root $\pmod{29}$ such as $g=2$. Then select exponents $e\equiv1\pmod4$ and $e\equiv\{1,2,4\}\pmod7$. The chinese remainder theorem produces $e\in\{1,9,25\}$ so $g^e\in\{2,19,11\}$ and now $2\cdot19\cdot11\equiv12\pmod{29}$ and indeed $12^4\equiv1\pmod{29}$.

If $5\mid(p-1)$ then let $r=\phi(p-1)/4$. If $r=1$, then there are only $4$ primitive roots $\pmod p$, and the theorem is true (for $p=11$). Otherwise we can find exponents $i,\,j,\,k$ such that $i\equiv1\pmod5$, $j\equiv2\pmod5$, and $k\equiv2\pmod5$, $\gcd(i,p-1)=\gcd(j,p-1)=\gcd(k,p-1)=1$ and $j\ne k$. Then for any primitive root $g\pmod p$, $\left(g^i\cdot g^j\cdot g^k\right)^{(p-1)/5}\equiv1\pmod p$.

For example, let $p=31$. Then $p-1=6\cdot5$ and we want $\{i,j,k\}\equiv\{1,2,2\}\pmod5$ and $\{i,j,k\}\equiv\{1,1,5\}\pmod6$. Then the chinese remainder theorem says $i=1,\,j=7,\,k=17$. We know that $g=3$ is a primitive root $\pmod{31}$, thus so are ${g^1,\,g^7,\,g^{17}}\equiv\{3,\,17,\,22\}\pmod{31}$, but $3\cdot17\cdot22\equiv6\pmod{31}$ and $6^6\equiv1\pmod{31}$.

Finally, if $3\mid(p-1)$, let $r=\phi(p-1)/2$. Then if $r=1$ we only have $2$ primitive roots $\pmod7$, $r=2$ means we only have $4$ primitive roots $\pmod{13}$ and the theorem is true, while if $r\ge3$ we can always find $i\equiv j\equiv k\equiv1\pmod{3}$, $\gcd(i,p-1)=\gcd(j,p-1)=\gcd(k,p-1)=1$, but $i\ne j,\,i\ne k,\,j\ne k$. Then for any primitive root $g$ $\pmod p$, $g^i$, $g^j$, and $g^k$ are all primitive roots $\pmod p$, but $\left(g^i\cdot g^j\cdot g^k\right)^{(p-1)/3}\equiv1\pmod p$.

For example, let $p=19$. Then $i=1,\,j=7,\,k=13$ satisfy the above condition and $g=2$ is a primitive root $\pmod{19}$. Then $g^1=2$, $g^7\equiv14$, and $g^{13}\equiv3\pmod{19}$ are all primitive roots $\pmod{19}$ but $2\cdot14\cdot3\equiv8\pmod{19}$ and $8^6\equiv1\pmod{19}$.

If no other prime than $2$ divides $p-1$ then $p$ is a Fermat prime and the theorem is true. Simple proposition, but it sure takes a long time to type all that MathJax in.