5
$\begingroup$

Consider the prime numbers of the form :

$p=4 \cdot k^2+1~$ , where $~k~$ is an odd prime number .

For the first $~1200000~$ primes of this form except when $~p=4 \cdot 193^2+1~$

$2~$ is a primitive root modulo $~p$ .

Note that :

Euler's totient function is given by :

$\phi(p)=4 \cdot k^2$

One can show that :

$\operatorname{ord}_p(2) \neq k~ ,\operatorname{ord}_p(2) \neq 2k~ ,\operatorname{ord}_p(2) \neq k^2~ ,\operatorname{ord}_p(2) \neq 2k^2~ $ , hence :

$\operatorname{ord}_p(2) = 4k~ \text {or}~\operatorname{ord}_p(2) = 4k^2~ $ since it cannot be $2 ~\text{or}~ 4$ .

My question :

Is there some special reason why $~2~$ isn't primitive root modulo $~p~$ in case of number

$~p=4 \cdot 193^2+1~$ ?

  • 0
    Note that the answer to this question had already been accepted and was apparently unaccepted for non-mathematical reasons (at least no mathematical reasons have been given) after a dispute about [this question](http://math.stackexchange.com/questions/111228).2012-02-20

1 Answers 1

7

First, the restriction on $\operatorname{ord}_p(2)$ can be more succinctly stated like this: Since $4k^2+1=5\bmod8$ for $k$ odd, $\pmatrix{\frac2p}=-1$ and $2$ is not a quadratic residue $\bmod p$. Thus all factors of $2$ in $p-1$ have to be present in $\operatorname{ord}_p(2)$, and since $k$ is prime and $4$ is not an option, that leaves only $4k$ and $4k^2$.

The "probability" that $\operatorname{ord}_p(2)=4k$ is $1/k$. To see whether to expect a finite number of examples of this, and if so, roughly how many to expect, we can use $2/\log x$ for the "probability" that an odd number $x$ is prime. Then the "probability" that $k$ is prime, $p$ is prime and $\operatorname{ord}_p(2)=4k$ is

$\frac4{k\log k\log(4k^2+1)}\;.$

The expected number of examples is the sum of this "probability" over all odd integers, which converges (as the sum over $1/(k\log^2k)$ converges by the integral test) and evaluates to about $0.9136$.

We can actually do slightly better than this: We've taken into account that $4k^2+1$ has residue $1\bmod2$, but not that we also know something about its residues with respect to the other primes. To have $p\equiv0\bmod q$ for some odd prime $q$, we must have $4k^2=(2k)^2\equiv-1\bmod q$, so $-1$ must be a quadratic residue $\bmod q$, which it is if $\pmatrix{\frac{-1}q}=1$, that is if $q\equiv1\bmod4$. In this case, of the $q-1$ possible residues of $k\bmod q$, there are two that would make $4k^2+1$ divisible by $q$, whereas if $-1$ is a non-residue, there are no such residues of $k\bmod q$. The estimate $2/\log(4k^2+1)$ for the "probability" of $4k^2+1$ to be prime includes a factor $(q-1)/q$ for every odd prime, and we have to replace this by $\left(q-2-\pmatrix{\frac{-1}q}\right)/(q-1)$, that is, we have to multiply by a correcting factor of

$\prod_q\frac{q\left(q-2-\pmatrix{\frac{-1}q}\right)}{(q-1)^2}\;,$

where the product is over all odd primes. This evaluates to about $1.106$. We can check this result by calculating the expected number of primes $p$ up to some value of $k$ and comparing with the actual number; for $k\lt5800$ there are $107$ primes $p$, and the "probabilities" for $p$ to be prime, corrected by the factor and summed over all odd primes $k\lt5800$, yield an expected number of about $106$.

Combining the two results, we'd expect about

$\sum_{n=1}^\infty\frac4{(2n+1)\log (2n+1)\log(4(2n+1)^2+1)}\prod_q\frac{q\left(q-2-\pmatrix{\frac{-1}q}\right)}{(q-1)^2}\approx1.011$

examples. Thus, given that there is necessarily an integral number of examples, your empirical finding of one example is exactly what might have been expected and requires no further explanation. Note also that while the individual "probability" for $k=193$ is quite small ($\approx0.04\%$), the sum of the terms beyond $k=150$ is roughly one fifth of the total sum, so the occurrence of the example at such a high value of $k$ is also not statistically significant.

  • 0
    That fact will not prevent me from asking questions on this site in the future :-) Thanks for all your previous answers . I wish you good luck.....2012-02-19