Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A recent sci.math thread is called "mutual primitive roots".
It is about quasi's conjecture that

For each prime $q>2$,
there is a prime $p<q$ such that
$p$ is a primitive root of $q$, and
$q$ is a primitive root of $p$.

Later paragraphs show my heuristic or probabilistic argument about why the conjecture ought to be true. The argument does not prove the conjecture, but is intended to show that the conjecture has a high likelihood of being true. My PARI-gp code at the end of this question has shown that the conjecture is true for $q<500000$.

Questions: (As revised per endnote)

  • Is my argument correctly expressed and free of silly mistakes?
  • Can a simpler argument be made for the truth of the conjecture, probabilistic or not?

Heuristic/probabilistic argument: (As revised per endnote)

Let $h = \Pi(q) = (\mathrm{\#primes} < q) \approx q/\ln q$; let $g = e^\gamma \approx1.7810724$, where $\gamma$ is the Euler–Mascheroni constant, $\approx0.5772156649$; and let $d(x) = (g\cdot\log\log x+3/\log\log x)$.

Let $S_q$ denote the set of primitive roots of $q$; $|S_q|>q/d(q)$ per wikipedia.

Let $T_q = \{ p\in S_q, p \mathrm{\ prime\}}$ and let $t = |T_q|$. We expect $$t >(h/q)\cdot q/d(q) = h/d(q) \approx q/( d(q)\cdot\ln q)$$ and for any given $p \in T_q$, we expect $\mathrm{prob}\{q\in S_p\} > (1/p)\cdot p/d(p) = 1/d(p)$.

Now $$\mathrm{prob}\{ q \not\in S_p\forall p\in T_q\} < \Pi_{i=1}^t(1-1/d(p_i))$$ which is less than $$(1-1/d(q))^t \approx (1-1/d(q))^{q/( d(q)\cdot\ln q)} =B(q) $$ which [computationally] goes to zero slightly slower than geometrically as $q$ grows. (For example, $\ln(B(x)) \approx -11.5, -20.3, -36.2, -64.9$ at $x=2048, 4096, 8192, 16384$.) Edit: $\log(B(x))=x\cdot\log(1-1/d(x))/(d(x)\cdot\ln x)<-x/(d(x)^2\cdot\ln x)$. (Via Taylor series, $\ln(1-u)=-(u/1!+u^2/2!+u^3/3!+...) < -u$.) Thus, $0 < B(x) < \exp(-x/(d(x)^2\cdot\ln x))$. As $x$ increases, the latter goes so rapidly to zero that not only is the probability of the conjecture failing for any particular $q$ quite small, the probability of it failing for any $q$ at all is tiny.

PARI-gp code to verify conjecture for small $q$:

  /* 4 Dec 2011 jiw: File "mutual-roots", re: mutual primitive roots for primes p, q, with p < q, ie p primitive mod q and q primitive mod p.
  Shell code to filter for gnuplot:
     gp < mutual-roots | grep '^[0-9]*.[0-9]*$' > t
  Depending on size of qmax and pmax, in gnuplot use commands like:
     plot  [0:100000][0:100] 't', x/18, 25,55
     plot  [0:500000][0:300] 't', x/21, 87,144
     plot  [0:500000][0:300] 't', x/21, 87,144
  s=99; pmax=prime(s); qmax=precprime(100000);
  b=vectorsmall(pmax); i=t=1;
  forprime(p=2, pmax, b[p]=t; t+=p);
  forprime(p=2, pmax, c=b[p]; for(i=1,p-1,if(znorder(Mod(i,p))==p-1,r[c+i]=1)));
  forprime(q=3, qmax, g=0; qx=min(pmax,q-1); forprime(p=2, qx, g+=r[b[p]+(q%p)]); print(q,"\t",g));

Revision note: Originally I used completely wrong values for $|S_q|$ and $|S_p|$. In edit 3, I used the loose estimate $\phi(x)\ge\sqrt x, x>6$ and removed a now-irrelevant question. In edit 4 the much-larger estimate $\phi(x)>x/d(x)$ is used to get a better result. In edit 5, Taylor series for $\log(1-1/d(x))$ is used to bound $B(q)$.

share|improve this question
I'm not sure what you mean by $|S|\approx q/2$. The number of primitive roots modulo $q$ is $\phi(q-1)$, which can be considerably less than $q/2$. Also, I wonder if you are familiar with the Artin and Bateman-Horn conjectures, which attempt to give accurate heuristics for the kind of thing you are looking at. –  Gerry Myerson Dec 6 '11 at 23:29
I forgot that the number of primitive roots is ϕ(ϕ(q)) and for some reason got stuck on the idea of (q-3)/2 (which may be an upper bound?) I'll look further at Artin and Bateman-Horn. –  jwpat7 Dec 7 '11 at 0:01
@Gerry, I've removed the "q/2" errors, and now am using estimate $\phi(x)>x/(e^\gamma\log\log x+3/\log\log x)$ –  jwpat7 Dec 7 '11 at 8:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.