# If $p$ is prime, prove that $\exists k\in\lbrace 5,-7,9,-11,..\rbrace$ in $(\mathbb{Z}/p\mathbb{Z})^*$ so that the Legendre symbol $(\frac{k}{p})=-1$

The BSPW primality test, when given $p$ as input, iterates over $k \in \lbrace 5,-7,9,-11,...\rbrace$ as long as the Legendre symbol $(\frac{k}{p})=1$. If $(\frac{k}{p})=0$, it returns "composite". So to show that the algorithm works properly, one has to prove (amongst other things) that if $p$ prime, there always exists a $k$ prior to $|k|=p$ with $(\frac{k}{p})=-1$. How do I do that?

This is what I tried:

Looking at the set $K$ of all $k$ we get: $$|K|=|\{5,-7,9,-11,...\}|=|\{5,p-7,9,p-11,...\}|=\left \lfloor{\frac{p}{2}}\right\rfloor-2=\frac{p-1}{2}-2$$

Let Q be the set of quadratic residues mod p. $(\mathbb{Z}/p\mathbb{Z})^*$ has $p-1$ elements. Every square element $x^2 \in (\mathbb{Z}/p\mathbb{Z})^*$ has exactly two roots: $x$ and $-x$. In other words the elements of $(\mathbb{Z}/p\mathbb{Z})^*$ generate $\frac{p-1}{2}$ quadratic residues mod p. Thus $|Q|=\frac{p-1}{2}$. But unfortunately $|K| < |Q|$, so I cannot use this to show $K \not \subseteq Q$.

Another observation is that because$(\mathbb{Z}/p\mathbb{Z})^*$ is cyclic, there exists a generating element $e$, thus: $$Q=\{x^2\}=\{(e^k)^2, k \in 1..p-1\}=\{e^{2k}, k \in 1..p-1\}=\{(e^2)^k, k \in 1..p-1\}=<e^2>$$ But I don't know if that's of any use.

The paper that introduced the algorithm does (as far as I can tell, I have not read it entirely) not mention this issue. The relevant sections are on pages 11 and 22, but they only discuss upper bounds for $f(p):=inf\{x: (\frac{x}{p})\not=1\}$, and don't mention why $f(p) \in K$. Since they seem to only be concerned with the case of input $p$ not prime, I am thinking that my question probably has a fairly trivial answer.

There is no merit to that claim that there always exist an $k$ such that $(\frac{k}{p})=-1$. Trivial counterexample are $p=2,5,11$. Hence the claim cannot possibly be proven in that form.

However, as usual, the algorithm is only required to work for large prime. In this case, the claim can be proved if we assume $p\geq 17$. The claim is true in the case of $p=3,7,13$ which can be checked individually by noticing that $(\frac{5}{p})=-1$ in those cases.

So now we assume $p\geq 17$. Then both the positive sequence $5,9,13,\ldots$ and the negative sequence $-7,-11,-15,\ldots$ each contains $3$ terms each. Why $3$ is important? Here is why. We already know that the set of $k$ to be checked contains $\frac{p-1}{2}-2$ elements (I'm assuming your result here without checking, but even in case you're wrong, we simply need to increase the lower bound of $p$ to make the proof work). We will proceed by contradiction, and assuming that for all those $k$ then $(\frac{k}{p})=1$. We will simply have to exhibit $3$ more value that are distinct from those $k$, and still are quadratic residue, making a total of $\frac{p-1}{2}+1$ quadratic residues, which would be a contradiction (as there can only be $\frac{p-1}{2}$ of quadratic residues).

So now we assume that all those $k$ we checked are quadratic residues. The $3$ extra values are as follow:

Case $p\equiv 1(\mod 4)$: then since $(\frac{-1}{p})=1$ if we assume $(\frac{k}{p})=1$ for all $k\in K$ then $(\frac{-k}{p})=1$, hence, since $-K\bigcap K=\emptyset$ there are $2|K|$ quadratic residues, a contradiction.

Case $p\equiv 3(\mod 4)$: then the last 3 term of the negative sequence is equivalence to $12,8,4$. Since $(\frac{4}{p})=1$ this means $(\frac{3}{p})=(\frac{2}{p})=(\frac{1}{p})=1$ which is once again $3$ extra terms distinct from those $k$ we checked.

Thus the proof is done by contradiction.

• In case $p\equiv 1(\mod 4)$ why does it follow that $(\frac{-5}{p})=(\frac{-9}{p})=(\frac{-13}{p})=1$? WolframAlpha says $(\frac{-13}{1009})=-1$. – Max Jul 26 '14 at 17:30
• @Max: remember that we are assuming (since we prove by contradiction) that $(\frac{5}{p})=(\frac{9}{p})=(\frac{13}{p})=1$. So $(\frac{-5}{p})=(\frac{5}{p})(\frac{-1}{p})=1\times 1=1$. In your case, $(\frac{-13}{1009})=-1$ showed that $(\frac{13}{1009})=-1$ so you would have found the $k$ you need. – Gina Jul 26 '14 at 17:35
• Oh, now I understand what you mean. The argument in the answer was not clear to me the way you wrote it. Imo it should be "Case $p \equiv 1~(mod~4):$ If $(\frac{k}{p})=1$ for every k, then also $(\frac{-k}{p})=1$, so we get atleast $2 \cdot |K|$ elements in Q, which is more than |Q|". – Max Jul 26 '14 at 17:42
• @Max: that should be "case $p\equiv 1(\mod 4)$ but I do find your argument clearer, I will edit it in. – Gina Jul 26 '14 at 17:45
• Alright, the other case also checks out. Thank you so very much :) – Max Jul 26 '14 at 17:54