2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ No. If $p\equiv 1 \pmod 3$ then $a^3$ is a counterexample. For example, $3$ is a primitive root mod $7$ but $3^3\equiv -1$ is not. $\endgroup$ – lulu Apr 3 '16 at 18:37
  • $\begingroup$ @lulu How did you conclude this general counterexample? $\endgroup$ – Joshhh Apr 3 '16 at 18:42
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the explanation. How does the answer change if one demands that all three must be distinct (assuming $\phi(p-1)\geq 3$)? $\endgroup$ – Joshhh Apr 3 '16 at 18:52
  • $\begingroup$ It turns out that even if all three are distinct, it might not be enough. $\endgroup$ – davidlowryduda Apr 3 '16 at 19:32
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.