Is There a Prime Number for Which a Non-Square is a Primitive Root?

Question

For a natural number not a perfect square, is there always at least a prime number for which it is a primitive root?

Artin's conjecture on primitive roots is that there are infinitely many such primes. Do we know for sure that there is at least one?

Answer 1

We do not know that. It is typical for questions about the infinitude of primes satisfying some property that even proving the existence of at least one of those primes in sufficient generality is unproved. And sometimes it turns out that proving there is at least one such prime in sufficient generality (the type of thing what you're asking) would imply there are infinitely many such primes thanks to some trick using the sufficient generality.

For the case of Dirichlet's theorem, see Theorem A.1 here. For the case of Bunyakosvky's conjecture and Schinzel's Hypothesis H see here.

For the case of the Artin primitive root conjecture in its qualitative form (infinitely many primes, nothing about their density), here are two such arguments. They are based on correspondence with Paul Pollack.

Theorem Assume the negative of each perfect square is a primitive root mod $p$ for at least one prime $p > 3$. Then the negative of each perfect square is a primitive root mod $p$ for infinitely many primes $p > 3$.

It is reasonable to require $p > 3$ in the theorem, since if $-A^2$ is the negative of a perfect square and $3 \nmid A$ then $-A^2 \equiv 2 \bmod 3$ and thus $-A^2$ is a primitive root mod $3$. So the theorem would not be saying anything interesting if we allow $p = 3$.

Proof. Let $a = -A^2$ for $A$ in $\mathbf Z^+$ and let $S = S_a$ be the set of primes $p > 3$ such that $a \bmod p$ is a primitive root, so $S$ contains at least one prime. To show $S$ is infinite, we'll argue by contradiction.

Assume $S$ is finite and let $L$ be the product of all odd primes $q$ that divide some $p-1$ where $p \in S$. Then $L$ is odd and $L \geq 1$. (The number $L$ is an empty product, and thus is $1$ by the usual convention for empty products, if each $p \in S$ has $p-1$ equal to a power of $2$ and thus has no odd prime factors.)

Set $b = a^L = (-A^2)^L = -(A^L)^2$, so $b$ is the negative of a perfect square. By the premise of the theorem, there is an odd prime $p > 3$ such that $b \bmod p$ is a primitive root. Since $a^L \bmod p$ generates $(\mathbf Z/p\mathbf Z)^\times$, so does $a \bmod p$, so $p \in S$. Since both $a \bmod p$ and $a^L \bmod p$ have order $p-1$, we have $(L,p-1) = 1$. If $p-1$ is not a power of $2$ then $p-1$ has an odd prime factor $q$, so $q \mid L$ by the definition of $L$, but $(L,p-1) = 1$ and $q \mid (p-1) \Longrightarrow (L,q) = 1$, which contradicts the condition $q \mid L$. Therefore $p-1 = 2^k$ for some $k$, making $p = 2^k + 1$.

Since $p > 3$ we have $k \geq 2$, so $p \equiv 1 \bmod 4$. By oddness of $L$, we have the Legendre symbol calculation $$ -1 = \left(\frac{b}{p}\right) = \left(\frac{a^L}{p}\right) = \left(\frac{a}{p}\right)^L = \left(\frac{a}{p}\right) = \left(\frac{-A^2}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{A}{p}\right)^2. $$ Thus $p \nmid A$ (otherwise the Legendre symbol $(A|p)$ would be $0$), so $(A|p)^2 = 1$. Also $(-1|p) = 1$ since $p = 1 \bmod 4$, so $-1 = 1\cdot 1 = 1$, a contradiction. That proves $S$ is infinite. $\Box$

Primes of the form $2^k+1$, which came up in the proof above, are Fermat primes and it is expected there are only finitely many of them (with the last one probably being $2^{16}+1$). That leads to the following second theorem with slightly different assumptions.

Theorem. Assume for each $a$ in $\mathbf Z$ that's not $0, 1, -1$ or a perfect square, $a$ is primitive root mod $p$ for at least one odd prime $p$ that's not a Fermat prime. Then for each $a$ in $\mathbf Z$ that's not $0, 1, -1$ or a perfect square, $a$ is primitive root mod $p$ for infinitely many odd primes $p$ that are not Fermat primes.

The hypothesis is reasonable in light of the Artin primitive root conjecture and the expectation that there are only finitely many Fermat primes.

Proof. Let $a$ be an integer that's not $0, 1, -1$ or a perfect square and let $S =S_a$ be the set of odd primes $p$ that are not Fermat primes and $a \bmod p$ is a primitive root, so $S$ contains at least one prime that is not a Fermat prime. To show $S$ is infinite, we'll argue by contradiction.

Assume $S$ is finite and let $L$ be the product of all odd primes $q$ that divide some $p-1$ where $p \in S$, so $L$ is odd and $L \geq 1$. (In fact $L \geq 3$ since for each $p$ in $S$ there is an odd prime factor of $p-1$, as $p-1$ is not a Fermat prime.)

The integer $b = a^L$ fits the hypothesis of Artin's conjecture:

(1) $|b| = |a|^L \geq |a| \geq 2 > 1$, so $b$ is not $0, 1$, or $-1$.

(2) if $b$ were a square then $a$ would be too since $L$ is odd, but $a$ is not a square. Thus $b$ is not a square.

Therefore by the premise of the theorem, there is an odd prime $p$ that's not a Fermat prime and $b \bmod p$ is a primitive root. Since $a^L \bmod p$ generates $(\mathbf Z/p\mathbf Z)^\times$, so does $a \bmod p$, so $p$ is in $S$. Since both $a \bmod p$ and $a^L \bmod p$ have order $p-1$, we have $(L,p-1) = 1$. Assuming $p-1$ has an odd prime factor $q$, we have $q \mid L$ by the definition of $L$, but $(L,p-1) = 1$ and $q \mid (p-1) \Longrightarrow (L,q) = 1$, which contradicts the condition $q \mid L$. Therefore $p-1$ has no odd prime factor, so $p-1 = 2^k$ for some $k$, making $p = 2^k + 1$, which is a Fermat prime, and that contradicts the definition of $S$ (it contains no Fermat primes). That proves $S$ is infinite. $\Box$

It would be nice if the role of Fermat primes could be removed from the second theorem. Anyone who figures out a way to do that should edit this answer or (if you can't edit) leave a comment below.