3
$\begingroup$

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?

$\endgroup$
10
  • $\begingroup$ How can we extend the definition of a square-free integer to a residue mod $p$ (prime)? It does not seem a well-defined notion to me. After all $2$ is a square-free integer, but to say $2$ is a square-free residue mod $3$ doesn't make as much sense because $2 \equiv 8 \pmod{3}$. $\endgroup$ – hardmath Oct 19 '14 at 5:02
  • $\begingroup$ To be more accurate ,if n is an integer | 1 < n < p and n not square-free then is the possibility of n being a primitive root mod p unlikely? $\endgroup$ – user128932 Oct 19 '14 at 5:10
  • $\begingroup$ @hardmath I saw another question like this, and I think the point is to take the "standard" residues. Of course, this is a "bad idea", for the reasons you say. Even if the question were made much more specific, it would still be extremely difficult to answer, because it's walking the line between very deep theorems like Chebotarev density, and utter nonsense. $\endgroup$ – Slade Oct 19 '14 at 5:11
  • 1
    $\begingroup$ @user128932 I think it will hard to get anyone to take the question seriously without some very precise notion of "unlikely". What statistical distribution are you using? I would suspect that being squarefree and being a primitive root are totally unrelated concepts, in the sense that they should be statistically independent, with the "appropriate" distributions. But I'm not going to write the question for you. In general, this is a very difficult kind of question to ask, let alone answer: see Artin's conjecture. $\endgroup$ – Slade Oct 19 '14 at 5:15
  • $\begingroup$ Another way of putting this is of all integers from 1 to 100, say; how many are primitive roots mod 101 and of those how many are square-free integers. I just thought it was an interesting question , not utter nonsense. $\endgroup$ – user128932 Oct 19 '14 at 5:23
2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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).

$\endgroup$
11
  • 1
    $\begingroup$ Now the number of squarefree integers up to $N$ is, asymptotically, $(6/\pi^2)N$. So if you look at 40 "random" integers (yes, I know there's no such thing as a uniform distribution on the integers) you'd expect about $240/\pi^2=24.3...$ of them to be squarefree. 26 is close enough for me to take this as (weak) evidence that primitive roots are not much likelier to be squarefree than other integers are. Perhaps more experiments are in order. $\endgroup$ – Gerry Myerson Oct 20 '14 at 1:04
  • 2
    $\begingroup$ @GerryMyerson: Scaling the computation up is straightforward except for our old nemesis, determining which integers are square-free. For that I have nothing better than factoring, so I'm going to pick a modestly larger prime $p=234007$ for which trial division is practical. $\endgroup$ – hardmath Oct 20 '14 at 12:59
  • 1
    $\begingroup$ I used Wolfram Alpha site to see that all the least residue primitive roots of 13 are 2,6,7,11 ; all square free. 17 has only 12 as a non-square free primitive root. 19 has no non-square free primitive roots ( they are 2,3,10,13,14,15. 23 has only 20 as a non-square free primitive root.29 has only 8,18,27 .31 has only 12 and 24. 37 has only 18 ,20, 24 ,and32. So for primes 3 to 37 less than a quarter of the least residues are primitive roots and non- squarefree. $\endgroup$ – 201044 Jun 3 '15 at 14:41
  • $\begingroup$ So do all primes have least residue primitive roots that when expressed in mod 10 or in decimal form, less than half of these least residues can be considered non-square-free ( when expressed in base 10 or decimal form)? $\endgroup$ – 201044 Jun 20 '15 at 5:29
  • $\begingroup$ @201044: I'm not sure what your question is, but being square-free does not depend on what radix (base) is used to represent an integer. The empirical evidence here is that all reduced residue primitive roots have a similar fraction of square-free values as the integers generally do, $6/\pi^2 \approx 0.61$. No proof of this was given here. $\endgroup$ – hardmath Jun 20 '15 at 12:39

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.