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.

$p$ is an odd prime and $k$ is a positive integer. Let $n=k \cdot p^2+1$. If $2^k \not\equiv 1 \pmod n$ and $2^{n-1} \equiv 1 \pmod n$, is $n$ prime? If it is, why?

share|improve this question
8  
What do you think? –  Did May 28 '12 at 17:41
1  
Also posted to MathOverflow, mathoverflow.net/questions/98222/prime-of-the-form-nkp21, without any mention of the post here. –  Gerry Myerson May 29 '12 at 1:05
    
I don't see any reason why this should always be true. Are there infinitely many base-2 pseudoprimes of the form $p^2+1$, or $2p^2+1$? - these would be counterexamples. I suspect the reason it's hard to find a counterexample is just because base-2 pseudoprimes are somewhat rare. –  Greg Martin May 29 '12 at 9:11
add comment

2 Answers 2

Not necessarily. Let $p = 3$ and $k = 154$. Then $n = 3^2 * 154 + 1 = 1387$, $2^{154} \equiv 1024 \not\equiv 1 \pmod{1387}$, and $2^{1386} \equiv 1 \pmod{1387}$. But $n = 1387 = 19 * 73$ is not prime.

share|improve this answer
1  
The version at MO had the additional constraint, $k\lt p$. If there's a counterexample to that version, it will have to be bigger than 1387. –  Gerry Myerson May 29 '12 at 2:46
2  
I checked $n \lt 10^{14}$ and the best is $n = 1101673501$ with $\frac{k}{p} \approx 1.75$. So maybe there isn't one. –  Dan Brumleve May 29 '12 at 3:24
add comment

I'm able to find a proof of the $k=2$ case, which is the first non-trivial case.

Result: Let $p$ be an odd prime and $n=2p^2+1$ such that $2^{n-1} \equiv 1 \pmod n$. Then $n$ is prime.

This proof splits into four steps:

  • We will prove that if $p$ divides $\varphi(n)$, then $n$ is prime.
  • We will prove that if $2^{2p} \equiv 1 \pmod n$, then $p$ divides $\varphi(n)$.
  • We will prove that if $2^{p^2} \equiv 1 \pmod n$, then $p$ divides $\varphi(n)$.
  • The Lucas primality test implies that if $2^{2p} \not\equiv 1 \pmod n$ and $2^{p^2} \not\equiv 1 \pmod n$, then $n$ is prime.

Lemma: Let $p$ be a prime and $n=2p^2+1$. If $p$ divides $\varphi(n)$, then $n$ is prime.

Proof: Since $\varphi(n)$ is multiplicative and $p$ is prime, $p$ divides $\varphi(q^t)$ for some prime power divisor $q^t$ of $n$. Since $\varphi(q^t)=q^{t-1}(q-1)$, and $q$ divides $n$ while $p$ does not divide $n$, we must have that $p$ divides $q-1$.

Since $q$ divides $n$, we know $n=bq$ for some $b \geq 1$. Since $p$ divides $q-1$, we know $q=cp+1$ for some $c \geq 1$.

Hence $$n=b(cp+1)=bcp+b$$ and from before $$n=2p^2+1.$$ By taking these equations modulo $p$, we must have that $b \equiv 1 \pmod p$.

Case I: $b \geq 2p+1$. Then $n=bcp+b>2p^2+1$, giving a contradiction.

Case II: $b=p+1$. Then $n=cp(p+1)+p+1=cp^2+2cp+1$. Since $n$ is odd, we must have that $c$ is even, and thus $n>2p^2+1$, giving a contradiction.

Thus $b=1$, and hence $c=2p$, and hence $q=2p^2+1=n$. Hence $n$ is prime (since $q$ is a prime divisor of $n$). End proof.

  • Now assume $2^{2p} \equiv 1 \pmod n$. Then $4^p \equiv 1 \pmod n$. Since $\gcd(4,n)=1$, we know $4$ is a member of the group $(\mathbb{Z}_n)^{\times}$. Hence the order of $4$, which we will denote $o_4$, divides $|(\mathbb{Z}_n)^{\times}|=\varphi(n)$. However, since $4^p \equiv 1 \pmod n$, we know that $o_4$ divides $p$. But since $n \geq 19$, we know that $o_4>1$, so $o_4=p$. Hence $p$ divides $\varphi(n)$.

  • Now assume $2^{p^2} \equiv 1 \pmod n$. Since $\gcd(2,n)=1$, we know $2 \in (\mathbb{Z}_n)^{\times}$. Hence the order $o_2$ of $2$ divides $|(\mathbb{Z}_n)^{\times}|=\varphi(n)$. However, since $2^{p^2} \equiv 1 \pmod n$, we know that $o_2$ divides $p^2$. But since $n \geq 19$, we know that $o_2>1$, so $p$ divides $o_2$ (more specifically, we know $o_2 \in \{p,p^2\}$). Hence $p$ divides $\varphi(n)$.

share|improve this answer
    
With the previously-hinted constraint that $k<p$, the first step should generalize to larger values of $k$, since $(ap+1)(cp+1) \ne kp^2+1$ unless one of $a,c$ vanishes (the LHS is $1 + (a+c)p$ mod $p^2$, and $ac<k<p$). –  Erick Wong Jun 13 '12 at 17:44
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.