Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$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|cite|improve this question
What do you think? – Did May 28 '12 at 17:41
Also posted to MathOverflow,, 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.

share|cite|improve this answer
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)$.

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

Your Answer


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.