Existence of a specific prime

Question

Reading some background on the Brocard-Ramanujan equation I found a proof which says the following. For a fixed natural number $A$ which is not a square it is always possible to find a prime $p$ such that

1. $p>A$;
2. $x^2\equiv A \pmod{p}$ has no solution (that is, $A$ is a quadratic non-residue modulo $p$).

However, the proof does not say anything about how it is possible. I do not find it so evident. Maybe I am missing some very basic fact.

Answer 1

If $A$ is a non-square, let $B=q_1\dots q_l\,$ its non-square part, i.e. write $A=BC$, where $C$ is a square and $B$ has no repeated prime factor. It is enough to find a prime $p>A$ such that $B$ is a non-square modulo $p$. Actually, we'll find one such that $p\equiv 1\bmod 4$.

• If $B$ is odd, using the Legendre symbol, we have by the law of quadratic reciprocity law: $$\biggl(\frac Bp\biggr)=\prod_{i=1}^l\Bigl(\frac{q_i}p\Bigr)=\prod_{i=1}^l\Bigl(\frac p{q_i}\Bigr)\bigl(-1\bigr)^{\tfrac{(p-1)(q_i-1)}4}=\prod_{i=1}^l\Bigl(\frac p{q_i}\Bigr)$$ By the Chinese remainder theorem, we can find an $x$ which is not a square modulo $p_1$, is modulo $p_i\ (i>1)$, and such that $x\equiv 1\bmod4$.

  Now by Dirichlet's theorem on arithmetic progressions, among the elements $x+4kB=x+ 4kq_1\dots q_l$, which are squares modulo each $q_i$, there are primes $p>A$. For such a $p$, we have $p\equiv 1\mod4$, so that $\biggl(\dfrac Bp\biggr)=-1$.

• If $B$ is even, write $B=2B'$. We slightly modify the previous argument: first choose an $x$ that additionally is congruent to $1\bmod 8$. Then consider a prime $p>A$ in the arithmetic progression: $$x+4kB=x+8kB'$$ By the previous case, $B'$ is not a square modulo $p$, and since $\,p\equiv1\bmod8$, by the Second supplementary law: $$\biggl(\frac Bp\biggr)= \biggl(\frac 2p\biggr)\biggl(\frac{B'}p\biggr)=\bigl(-1\bigr)^{\tfrac{p^2-1}8}\cdot(-1)=-1 $$

Therefore in either case, $B$ is not a square modulo $p$.

Answer 2

I do not have enough reputation to comment. Just a hint to make Bernard's idea work. Show that among the elements of forms $1+kB$ or $1+2kB$ there are infinitely many primes which are congruent to $3$ mod $4$, otherwise you reach some contradiction with existence of primes of some form. Just an idea, I have not made it through.