Is this proof acceptable ?


Let $N$ be of the form $N=2p +1$ with $p$ prime , then

$N$ is prime iff $N \mid 2^{2p}-1$


In one direction , if $2p+1$ is a prime then by Fermat Little Theorem we have :

$2^{2p} \equiv 1 \pmod N$ , hence $N \mid 2^{2p}-1$ .

Conversely , let $N$ be a factor of $4^p-1$ .

If $p=2$ then :

$N \mid 4^2-1$ and $N=5$ , so $N$ is prime .

If $p >2$ , then :

Suppose that $2p+1$ is composite and let $q$ be it's least prime factor .

Then , $4^p \equiv 1 \pmod q$ , and so :

$\operatorname{ord_q(4)} \mid p$ and $\operatorname{ord_q(4)} \mid q-1$ , hence

$p \mid q-1$ , and therefore $q> p$ .

It follows : $(2p+1)+1 > q^2 > p^2$ ,

which is contradiction since $p>2$ , hence $N$ must be prime .


First, I might change what you wrote from

It follows : $(2p+1)+1 > q^2 > p^2$


If $N$ is composite, it follows : $(2p+1)+1 > q^2 > p^2$

The claim might be true, but I think there is a problem with this argument. What if $q$ (the smallest prime factor of $N=2p+1$) is $3$? Then in the second part of the argument where we assume $N$ is a factor of $4^p-1$, it is still true that $4^p\equiv1\mod q$, and this does imply that $\operatorname{ord}_{q}(4)\mid p$. But your argument then proceeds as if $\operatorname{ord}_q(4)=p$. With $q=3$, actually $\operatorname{ord}_q(4)= 1$. There is no implication then that $q>p$.

If $N$ is additionally not divisible by $3$, then maybe your argument works. (That is, if $N=6p\pm1$.)

If $3$ is the smallest prime divisor of $N$, then either $N=3^k$, or you can modify your argument to let $q$ be the second smallest prime divisor of $N$. In the latter case, you still get that this $q$ is greater than $p$. If $N$ is not prime, then your next-to-last line becomes $(2p+1)+1>3q>3p$, which is still a contradiction.

This leaves the case $N=3^k$, where we are still assuming $N$ is a factor of $4^p-1$. We know in this case that $N$ is not prime. So your claim (in its full totality) hinges on $p=\frac{3^k-1}{2}$ not being prime when $3^k$ divides $4^p-1$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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