# Does the set of $m \in Max(ord_n(k))$ for every $n$ without primitive roots contain a pair of primes $p_1+p_2=n$?

I have made the following observation: for those n even numbers that do not have primitive roots modulo n ,$Pr(n)$, the set $M(n)$ of those $k$ having a maximum multiplicative order $ord_n(k)$ contains at least a pair of primes $p_1$ and $p_2$ whose sum is $n$, so $p_1+p_2=n$.

Context: when a number $n$ does not have primitive roots modulo n, $Pr(n)$, it is possible to generate the set $M(n)$ that will include those numbers $k$ in $[1,n]$ whose order $ord_n(k)$ is the maximum multiplicative order of $k$ in $\Bbb Z/n \Bbb Z$, also named as the maximum possible order mod n depending on the reference you use. The definition of the order $ord_n(k)$ of an integer k modulo n (or multiplicative order of $k$ in $\Bbb Z/n \Bbb Z$) is here (click). $Max(ord_n(k))$ is the maximum possible value of the Carmichael function in [1,n].

$M(n)=\{\ m: ord_n(m) = Max(ord_n(k))\ ,\ k \in [1,n]\ \}$

Test: this is the PARI/GP code to calculate $M(n)$, returns the set and the maximum order:

noprimroot(n,limitval)={
while (n<limitval,
if (n==3458 || n==4930 || n==31682 || n==82082 || n==93314 ||
n==150722 || n==324802 || n==344162 || n==798002 ||
n==898130 || n==977762 || n==1061762 ||
n==1313202 || n==1340066 || n==1633242 || n==1676402 ||
n==1947064 || n==1995266 ,n=n+2,
if(trap(,,znprimroot(n)),,
/* calculate value of maximum multiplicative order mod n */
carmfunc = znstar(n)[2][1];

wasfound = 0;
p1=0;
p2=0;
for(i=1,n,
if((gcd(i,n)==1) && (isprime(i) && (gcd(n-i,n)==1) && (isprime(n-i))),
if (((i^carmfunc)%n)==1 && (((n-i)^carmfunc)%n)==1,
p1=i; p2=n-i; wasfound=1;break
)
)
);

if (wasfound==0,print("ERROR ",n);break,print("SUCCESS ",n," ",p1," ",p2))
);
n=n+2
)
)
}


Be aware that there is a well known bug regarding the znstar function (used here to calculate the Carmichael function of $n$ that makes a infinite loop and crashes PARI/GP for some specific values (see first condition added in the code). For those values I have used the (very brute force) Python version written below.

By doing so, these are the first even number $n$ elements and their $M(n)$ sets, the first $n$ without primitive roots modulo $n$ is $n=8$:

$n=8$ and $Mo(8)=[3, 5, 7]$

$n=12$ and $Mo(12)=[5, 7, 11]$

$n=16$ and $Mo(16)=[3, 5, 11, 13]$

etc.

Test results: tested successfully the even numbers $n$'s in the interval $[1,2*10^6]$ and as far as I can see if I did not make an error in the test the following statement (1) is always true:

(1) $\forall n$ even if $\not\exists Pr(n)$ then $\exists (p_1,p_2)\ /\ (1)\ p_1,p_2 \in \Bbb P\ , (2) \ p_1,p_2 \in M(n), (3)\ p_1+p_2=n$

Meaning that for those even numbers $n$ that do not have primitive roots modulo $n$, their list of maximum multiplicative order elements to mod $n$, $M(n)$, at least contain two prime numbers $p_1$ and $p_2$ that are a Goldbach pair of $n$. With "Goldbach pair" I mean that $p_1+p_2=n$.

E.g. for the samples above:

$n=8$ and $Mo(8)=[3, 5, 7]$ , $p_1=3$ and $p_2=5$

$n=12$ and $Mo(12)=[5, 7, 11]$ , $p_1=5$ and $p_2=7$

$n=16$ and $Mo(16)=[3, 5, 11, 13]$ , $p_1=3$ and $p_2=13$

etc.

Some questions I would like to share:

My theoretical knowledge is very poor, please I would like to share with you the following questions to learn more about this:

1. Is this relationship somehow trivial due to the way that the maximum order elements are defined and calculated?

2. It is just coincidental (probabilistic) because the size of the set $M(n)$ gets big enough to contain at least a pair of primes complying with (1)?

3. Is there a counterexample of them?

4. If there are not counterexamples, and it is not a probabilistic coincidence, would it be possible based on the definition of the maximum order elements to prove that inside $M(n)$ there is always at least one pair of primes that will sum n when n is even? (if so at least the Goldbach conjecture could be true for this kind of numbers)

• $Mo(n)$ is still not clear to me, could you write it as a set? ( I presume it is a set ). – baharampuri May 18 '15 at 10:04
• @baharampuri Hi, I have added a definition as a set in the question. I have tried my best, but I am not an expert and it is complex to describe for my level of knowledge. Have a look to it, I hope it will help to understand the construction of the sets. :) – iadvd May 18 '15 at 11:59
• @baharampuri I hope now will be more clear. Please if you need more details let me know. – iadvd May 19 '15 at 13:39
• I saw the definition, thanks. – baharampuri May 19 '15 at 13:41
• 2000 is still a very small number from the perspective of primality - you still have a good 15% of the numbers (30% of the odd numbers!) smaller than that being prime, so it's very hard to make judgements from the relatively meager data here. I would want to see numerical evidence up to at least $10^7$ or so and preferably $10^9$ before really putting much weight behind this. – Steven Stadnicki May 22 '15 at 1:42