Is $n = k \cdot p^2 + 1$ necessarily prime if $2^k \not\equiv 1 \pmod{n}$ and $2^{n-1} \equiv 1 \pmod{n}$?

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

-
What do you think? – Did May 28 '12 at 17:41
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

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.

-
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
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

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)$.

-
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