I am trying to understand Theorem (2.1) in this Paper. Here it is:
Let $n = h\cdot 2^k+1$ with $0<h<2^k$ and $h$ odd. If $\left(\frac{D}{n}\right) = -1$, then:
$n$ is prime $\Leftrightarrow D^{\frac{n-1}{2}}\equiv -1 \pmod n$
But I don't see the proof, yet. Here is what I have.
It's assumed that for an element $D$ the Jacobi-Symbol $\left(\frac{D}{n}\right) = -1$.
Let $n$ be a prime. Then the Jacobisymbol is the same as the Legendresymbol. So, by Euler's criterion I can calculate it via $\left(\frac{D}{n}\right) = D^{\frac{n-1}{2}}$ and we have the right side hence $D^{\frac{n-1}{2}} \equiv -1 \pmod n$.
But how do I show the $\Leftarrow$ direction? So I assumed, $n$ is not prime. Then let $n = p_1\cdot \dots\cdot p_k$ be the primce decomposition. I can then write $\left(\frac{D}{n}\right) =-1 = \left(\frac{D}{p_1}\right)\cdot\dots\cdot\left(\frac{D}{p_k}\right)$. But I can't conclude that $D^{\frac{n-1}{2}}\not\equiv -1\pmod n$.
What am I missing?
Thanks for reading my first post, hope I wrote everything that was needed :)
Assume that $D^{(n-1)/2} \equiv -1 \pmod{n}$. Then in particular $D$ and $n$ are coprime.
It turns out that in this case, the Legendre symbol is a “red herring” of sorts – what’s important is the inequality on $h$.
Let $q$ be a prime dividing $n$ (so $q$ is odd), then we know that $D^{h2^{k-1}}\equiv -1 \pmod{q}$. I claim that this implies that $2^k|q-1$.
Indeed, the gcd $\omega$ of $q-1$ and $h2^k$ is such that $D^{\omega}\equiv 1\pmod{q}$. Therefore $\omega$ cannot divide $h2^{k-1}$, hence $2^k|q-1$.
Assume that $n$ isn’t prime. Then there are two prime numbers (not necessarily distinct) $p$ and $q$ such that $pq|n$. By the above, $p\geq 2^k+1$, $q \geq 2^k+1$, hence $$2^{2k}+1> h2^k+1=n \geq pq \geq (2^k+1)^2,$$ a contradiction.