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
    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$" .2012-02-18
  • 0
    @EwanDelanoy,Thanks,English isn't my native language so....2012-02-18
  • 0
    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.2012-02-19
  • 0
    @joriki,thanks...fixed2012-02-19
  • 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
    ,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$ ?2012-02-19
  • 0
    @pedja: I don't know. You're asking about the probability that $p$ is a [Poulet number](http://mathworld.wolfram.com/PouletNumber.html). 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](http://oeis.org/A001567), none are of that form.2012-02-19
  • 0
    ,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 .2012-02-19
  • 0
    @pedja: How do you draw a connection between those two?2012-02-19
  • 0
    ,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 ?2012-02-19
  • 0
    @pedja: I don't understand that argument -- can you flesh it out? Why can it not be the power of some odd prime, and if so, why does that imply it has to be prime? By the way, why do you start your comments with commas, and why do you create extra space around math using tildes?2012-02-19
  • 0
    There is a theorem that states : "modulus $n$ has a primitive roots iff $n$ is : $1,2,4,p,2p,p^k ~\text{or}~2p^k$ , where $p$ is a prime number"...[Theorem](http://math453spring2009.wikidot.com/lecture-25)2012-02-19
  • 0
    Consider equation : $4n^2=p^k-1=(p-1)(p^{k-1}+p^{k-2}+...+1)$2012-02-19
  • 0
    @pedja: What about that equation? I find your style of interaction rather irritating. You make some statement and say "Am I correct?"; then it turns out you had a whole argument to back that up -- why didn't you say so right away? Now you say "consider equation", and presumably you again have some argument why that equation shows that $p$ can't be a power of an odd prime -- do you want me to guess it, or what's the point?2012-02-19
  • 0
    No I have no argument why $p$ can't be power of an odd prime...I only know that from the equation above it follows that : $p=3 ~\text{or}~ p=5~$ therefore : $4n^2+1=3^k$ , or $4n^2+1=5^k$ . It seems that these diophantine equations have no solutions in integers for $k>1$ , but I am not sure of it...That's why I am asking you....2012-02-19
  • 0
    @pedja: Sorry, I find this too annoying. I won't be answering anymore. If you don't want to write out your arguments for others, you'll just have to think about them by yourself.2012-02-19
  • 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