# Prime numbers primitive roots and $\Phi$?

Let's $s$ be the sum of the primitive roots of a prime number $p$.

One observation is that $\dfrac{s+x}{p}$ is an integer when $x = \{-1, 0, 1\}$.

So one could categorize each $p$ in one of $3$ categories: $c_{-1}$, $c_0$ or $c_1$.

Let's call $r_0$ the ratio of number of $c_0$ and number of primes $\left(\text{i.e.}\,\dfrac{\text{number of$c_0$}}{\text{number of primes}}\right)$.

After observation of the $1650$ first primes, I am under the impression that $r_0$ converges by oscillating to $\dfrac{1}{\Phi}$, with $\Phi$ being $\dfrac{1+V_5}{2}$.

Is it true?

If yes:

1. Is it a well-known result?
2. Is there some documentation out there?
3. What about $r_{-1}$ & $r_1$? Do they also converge to a calculable value? So far, I have $r_{-1}=0.18612922347362182$ and $r_1=0.19594997022036928$.

I'm limited in my observation by using only a spreadsheet program and going till the $2000^{th}$ prime should be exhausting enough! Please excuse my bad English. Maybe I should mention also I am not a mathematics student or anything; I just like playing with numbers.

Examples:

1. Primitives roots of $29$ ($10^{th}$ prime) $= \{2,15,3,10,8,11,14,27,18,21,19,26\}$, sum $= 174$, and $\dfrac{174}{29} = 6 \implies 29$ is a $c_0$ prime.

2. Primitives roots of $43$ ($14^{th}$ prime) $= \{3,29,5,26,12,18,19,34,20,28,30,33\}$, sum $= 257$, and $\dfrac{257+1}{43} = 6 \implies 43$ is a $c_1$ prime.

3. Primitives roots of $11$ ($5^{th}$ prime) $= \{2,6,7,8\}$, sum $= 23$, and $\dfrac{23-1}{11} = 2 \implies 11$ is a $c_{-1}$ prime.

See the graph below for an illustration.

• Can you prove that $s$ is equivalent to either $-1, 0,$ or $1\bmod p$? (i.e. that all primes belong to one of your classes?) Also, do you know how to typeset in LaTeX? It makes questions much more readable. – Carl Schildkraut Mar 14 '18 at 18:33
• For the first $4\ 203$ primes (the primes below $40\ 000$) , I get ratio $0.620509$ , which is quite close. To get substantially further , we would need a nice criterion for a prime whether it divides the sum of its primitive roots. – Peter Mar 14 '18 at 18:47
• Just a comment: If $p\equiv 1\bmod 4$, then $x$ is a primitive root iff $-x$ is. – Carl Schildkraut Mar 14 '18 at 18:54
• What does the graph illustrate? – an4s Mar 14 '18 at 18:55
• @Peter, I think your comments are strong enough to be an answer now. And the answer to my main question is no, which made the following ones irrelevant. Thank you again for your interrest and computer-time! :) – jerome artarpoat Mar 14 '18 at 20:14

Based on Carl's criterion, the probability for residue $0$ is asymptotically

$$1-\prod_p (1-\frac{1}{\phi(p^2)})=1-\prod_p (1-\frac{1}{p(p-1)})=0.626044\cdots$$ where $p$ runs over the primes and $\phi(n)$ denotes the totient-function.

The reason is that for a large prime $q$, the probability that $q$ is not of the form $kp^2+1$, is $1-\frac{1}{\phi(p^2)}$ for every prime $p$ because $\phi(p^2)$ residues are possible modulo $p^2$

Hence the probability that $q$ has not the form $kp^2+1$ for any prime (hence is squarefree) is the product of $1-\frac{1}{\phi(p^2)}$ over the primes upto $\lceil \sqrt{q} \rceil$ if we assume indepence which should hold if $q$ is large enough.

• Why is this true? – Carl Schildkraut Mar 15 '18 at 13:59
• I fixed the error that $1-$ was missing before the products. The indepence might not hold strictly, but we have this problem also if we want to calculate the probability that a number is squarefree, for example. The coincidence with numerical calculations however is so good that I am pretty sure that the product gives the asymptotic probability. – Peter Mar 15 '18 at 14:34
• I wonder whether there is a nice formula for this number. – Peter Mar 15 '18 at 14:35
• It equals $1-C_A$ where $C_A$ is Artin's constant. Given that we call this Artin's constant and not something else, I would wager that this has no known closed form. – Carl Schildkraut Mar 15 '18 at 14:59

We claim that the sum of the primitive roots $\bmod p$ is equivalent to $\mu(p-1)\bmod p$, where $\mu$ is the Mobius function.

To prove this, we are going to do something similar to Mobius inversion. Letting $g$ be any primitive root $\bmod p$, we can represent the primitive roots $\bmod p$ as the set of values of $g^k$, where $\gcd(k,p-1)=1$. So, the sum of all of these is

$$\sum_{k=0}^{p-2} g^k[\gcd(k,p-1)=1],$$

where the Iverson bracket $[\gcd(k,p-1)=1]$ is $1$ if the condition is true, and $0$ otherwise. This can be expanded, using the property that

$$\sum_{d|n} \mu(d) = [n=1],$$

as

$$\sum_{k=0}^{p-2} g^k\sum_{d|k,\ d|p-1} \mu(d).$$

Switching the indices of summation and setting $k=dm,$

$$\sum_{d|p-1} \mu(d)\sum_{m=0}^{\left(\frac{p-1}{d}\right)-1} g^{md}.$$

The inside sum is a geometric series, and we can simply use the formula for the sum of one to get that it equals

$$\frac{g^{p-1}-1}{g^d-1}.$$

If the denominator is not $0\bmod p$, then this is $0\bmod p$ (as $g^{p-1}\equiv 1\bmod p$); so, the only term we don't need to neglect is that where $d=p-1$, at which point the sum if $1$ and the sum reduces to $\mu(p-1),$ finishing the proof.

Edit: What follows is not terribly accurate numerical analysis - that of Peter in his answer is more accurate.

Now, it's probably pretty difficult to get exact distribution statistics on $\mu(p-1)$ as the connection between the factorizations of consecutive integers is not very well-hashed-out. However, we can get some heuristics based on the generic properties of the Mobius function:

First off, the distribution of $1$s should be the same as the distribution of $-1$s, so it suffices to find the distribution of $0$s. If $p\equiv 1\bmod 4$, then $p-1$ is not squarefree, so $\mu(p-1)=0$.

We know that the probability that $\mu(n)\neq0$ is $6/\pi^2$. However all of these numbers are not $0\bmod 4$, so the probability that a number that is $2\bmod 4$ (specifically, $p-1$) has $\mu(n)\neq0$ should be

$$\frac{4}{3}\left(\frac{6}{\pi^2}\right) = \frac{8}{\pi^2}.$$

Thus, the probability that a prime $p$ has $\mu(p-1)=0$ should be

$$\frac{1}{2}\left(1+1-\frac{8}{\pi^2}\right) = 1-\frac{4}{\pi^2},$$

and each of $\pm 1$ has probability $\frac{2}{\pi^2}$.

• The primes upto $10^9$ give probability $0.6260545\cdots$ , whereas $1-\frac{4}{\pi^2}=0.594715\cdots$ – Peter Mar 15 '18 at 7:37
• Nevertheless (+1) for the criterion which is both enlightning and useful to calculate the probability – Peter Mar 15 '18 at 8:07