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~$ ?

  • $\begingroup$ There are some typos in the text : "For the first $~291422~$ primes of this form only in case when $~p=4 \cdot 193^2+1~$ $2~$ isn't primitive root modulo $~p$" should be "For the first $~291422~$ primes of this form except when $~p=4 \cdot 193^2+1~$ $2~$ is a primitive root modulo $~p$" . $\endgroup$ – Ewan Delanoy Feb 18 '12 at 15:48
  • $\begingroup$ @EwanDelanoy,Thanks,English isn't my native language so.... $\endgroup$ – Peđa Terzić Feb 18 '12 at 16:01
  • $\begingroup$ Note that you can get proper formatting for things like $\operatorname{ord}$ by using \operatorname{ord}. If you just write ord, $\TeX$ interprets this as juxtaposed variable names and italicizes them. $\endgroup$ – joriki Feb 19 '12 at 8:58
  • $\begingroup$ @joriki,thanks...fixed $\endgroup$ – Peđa Terzić Feb 19 '12 at 9:13
  • $\begingroup$ 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. $\endgroup$ – joriki Feb 20 '12 at 11:56

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


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.

  • $\begingroup$ ,Splendid...In your opinion what would be probability that composite number of the form : $p=4n^2+1~$ , where $n$ is an odd prime satisfies the congruence : $~2^{p-1} \equiv 1 \pmod p$ ? $\endgroup$ – Peđa Terzić Feb 19 '12 at 11:43
  • $\begingroup$ @pedja: I don't know. You're asking about the probability that $p$ is a Poulet number. Since apparently little is known in general about their distribution, it seems unlikely that one could say much more about their distribution among numbers of that specific form. Of the numbers listed in OEIS sequence A001567, none are of that form. $\endgroup$ – joriki Feb 19 '12 at 12:12
  • $\begingroup$ ,In my opinion since 2 is primitive root for almost all primes p it is unlikely that p could be pseudoprime to base 2 or Carmichael number . $\endgroup$ – Peđa Terzić Feb 19 '12 at 12:39
  • $\begingroup$ @pedja: How do you draw a connection between those two? $\endgroup$ – joriki Feb 19 '12 at 13:00
  • $\begingroup$ ,If $~2~$ is a primitive root modulo $~p~$ and $~p~$ is of the form $~4n^2+1~$ then $~p~$ has to be prime number since it cannot be power of some odd prime . Am I correct ? $\endgroup$ – Peđa Terzić Feb 19 '12 at 13:25

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.