Return to Answer

The claim does not hold. A counterexample is given by $n=14$, $p=134123250258009499$ and correspondingly $$N = 2197475332227227631617 = 193 \cdot 12289 \cdot 926510094425921.$$ It can be easily verified that $$3^{(N-1)/2} \equiv 1 \pmod{N},$$ but $N$ is not prime.

A couple more values of $N$ giving counterexamples: $$300334937065845770469377,\ 80203520301265852381167617.$$

ADDED. Here is a list of 659 of counterexamples that I found.

The claim does not hold. A counterexample is given by $n=14$, $p=134123250258009499$ and correspondingly $$N = 2197475332227227631617 = 193 \cdot 12289 \cdot 926510094425921.$$ It can be easily verified that $$3^{(N-1)/2} \equiv 1 \pmod{N},$$ but $N$ is not prime.

A couple more values of $N$ giving counterexamples: $$300334937065845770469377,\ 80203520301265852381167617.$$

ADDED. Here is a list of 659 counterexamples that I composed from the known prime factors of generalized Fermat numbers GFN(3).

The claim does not hold. A counterexample is given by $n=14$, $p=134123250258009499$ and correspondingly $$N = 2197475332227227631617 = 193 \cdot 12289 \cdot 926510094425921.$$ It can be easily verified that $$3^{(N-1)/2} \equiv 1 \pmod{N},$$ but $N$ is not prime.

A couple more counterexamples: $$N\in\{\ 300334937065845770469377,\ 80203520301265852381167617\ \}.$$

The claim does not hold. A counterexample is given by $n=14$, $p=134123250258009499$ and correspondingly $$N = 2197475332227227631617 = 193 \cdot 12289 \cdot 926510094425921.$$ It can be easily verified that $$3^{(N-1)/2} \equiv 1 \pmod{N},$$ but $N$ is not prime.

A couple more values of $N$ giving counterexamples: $$300334937065845770469377,\ 80203520301265852381167617.$$

ADDED. Here is a list of 659 of counterexamples that I found.

The claim does not hold. A counterexample is given by $n=14$, $p=134123250258009499$ and correspondingly $$N = 2197475332227227631617 = 193 \cdot 12289 \cdot 926510094425921.$$ It can be easily verified that $$3^{(N-1)/2} \equiv 1 \pmod{N},$$ but $N$ is not prime.

The claim does not hold. A counterexample is given by $n=14$, $p=134123250258009499$ and correspondingly $$N = 2197475332227227631617 = 193 \cdot 12289 \cdot 926510094425921.$$ It can be easily verified that $$3^{(N-1)/2} \equiv 1 \pmod{N},$$ but $N$ is not prime.

A couple more counterexamples: $$N\in\{\ 300334937065845770469377,\ 80203520301265852381167617\ \}.$$