Proof concerning specific class of Proth numbers

141 Views Asked by At

Is this proof acceptable ?

Theorem

Let $N = k\cdot 2^n+1$ with $n>1$ , $k<2^n$ , $k$ odd and $3 \nmid k $ , thus

$N$ is prime iff $3^{\frac{N-1}{2}} \equiv -1 \pmod N$

Proof

Necessity : If $N$ is prime then $3^{\frac{N-1}{2}} \equiv -1 \pmod N$.

Let $N$ be a prime , then according to Euler criterion :

$3^{\frac{N-1}{2}} \equiv \left(\frac{3}{N}\right) \pmod N$

If $N$ is prime then $N \equiv 2 \pmod 3 $ and therefore : $\left(\frac{N}{3}\right)=-1$ .

Since $N \equiv 1 \pmod 4 $ according to the law of quadratic reciprocity it follows that : $\left(\frac{3}{N}\right)=-1$ .

Hence , $3^{\frac{N-1}{2}} \equiv -1 \pmod N $ .

Sufficiency : If $3^{\frac{N-1}{2}} \equiv -1 \pmod N$ then $N$ is prime.

If $3^{\frac{N-1}{2}} \equiv -1 \pmod N$ then according to Proth's theorem $N$ is prime .

1

There are 1 best solutions below

0
On BEST ANSWER

Is this proof acceptable ?

I think it is acceptable.

For necessity : I found nothing wrong in your proof. I think that it might be better to add an explanation about how to get $N\equiv 2\pmod 3$, but your proof is acceptable.

For sufficiency : You can apply Proth's theorem here, so your proof is acceptable.