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

Question

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

Answer 1

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.

Answer 2

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