$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?
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}$?
-
0I 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. – 2012-05-29
2 Answers
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.
-
2I checked $n \lt 10^{14}$ and the best is $n = 1101673501$ with $\frac{k}{p} \approx 1.75$. So maybe there isn't one. – 2012-05-29
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)$.
-
0With the previously-hinted constraint that k
, 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
). – 2012-06-13