About primitive roots and square free numbers.

Question

Are primitive roots either a prime or not a quadratic residue ; with few exceptions? If ($m^2$ n) is a primitive root then n is a non-quadratic residue. Given there are $\phi{(p-1})$ primitive roots mod p then for some large prime p ; are more than $\phi{(p-1)}$/2 of them that are not quadratic residues?

Answer 1

Following @GerryMyerson's suggestion, I did a similar calculation for a significantly larger prime, $p=234007$. The agreement of the fraction of squarefree primitive roots modulo that prime with $6/\pi^2$ is still more striking. There are $46341$ squarefree numbers out of $76104$ primitive roots, while multiplying the latter by $6/\pi^2$ gives an "expected" number of $46265.7$ or so.

The prime $p=234007$ was haphazardly selected as the smallest one greater than $234000$. Primality was first checked by Android phone app Prime Factors by Ivon Liu (there are several similarly named Android apps). Primality is also confirmed by finding a primitive root, a nonzero residue modulo $234007$ with multiplicative order $\phi(234006)=\phi(2)\phi(3)\phi(43)\phi(907)=76104$.

The strategy is to generate all the primitive roots modulo $234007$ and count how many are squarefree and how many are not.

First calculate that $7$ is a primitive root, by showing:

$$ 7^{234006} = 1 \pmod{234007} $$

$$ 7^{234006/2} \neq 1 \pmod{234007} $$

$$ 7^{234006/3} \neq 1 \pmod{234007} $$

$$ 7^{234006/43} \neq 1 \pmod{234007} $$

$$ 7^{234006/907} \neq 1 \pmod{234007} $$

For example the SageMath Cloud allows one to check this easily from the browser, using:

sage: pow(7,234006,234007)
1

and similar commands. Or even more expeditiously:

sage: primitive_root(234007)
7

Given one primitive root, the rest may be found by raising it $\pmod{234007}$ to all the exponents $1 \le k \lt 234006$ which are coprime to $234006$, i.e. odd integers in this range that are coprime to $3,43,907$. This will generate $76104$ distinct primitive roots modulo $234007$.

Now we have a number of checks for square factors to perform. I used a list of the primes below $1000$, and in a variation on trial division had it report not squarefree if and only if there were no repeated small prime factors from this list. Since the targets being checked are less than one million, this check is adequate for the purpose.

If there is interest, I'll post the Prolog code used for generating, testing, and counting. It can be adapted pretty quickly to use with other prime moduli.

Answer 2

Checking per Gerry's suggestion, a quick spreadsheet for the 40 primitive roots mod 101 shows that twenty-six (26) of them are square-free and fourteen (14) of them are not. We are helped in this by the fact that 2 is the smallest primitive root mod 101, so taking powers of 2 with exponents coprime to 100 gives all forty of the primitive roots (reduced mod 101).