Primality Test for Safe Primes Is this proof acceptable ?
Theorem
Let $N$ be of the form $N=2p +1$ with $p$ prime , then 
$N$ is  prime iff $N \mid 2^{2p}-1$  
Proof
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 . 
 A: First, I might change what you wrote from 
It follows : $(2p+1)+1 > q^2 > p^2$
to
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$.
