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.
Max Alekseyev
- 34.3k
- 5
- 74
- 152