Is $17$ a quadratic residue for a prime $p$?

Question

wondering if $17$ is a quadratic residue for a prime $p$? We know that $p \equiv \pm 3 \mod{8}$ but nothing else.

Thanks!

Answer 1

Well, pretty trivially we have that

$$\left(\frac{17}2\right)=1\;\;\ldots$$

But also

$$\left(\frac{17}{19}\right)=\left(\frac2{17}\right)=1$$

and some more...the QRT, as commented, is your friend.

Answer 2

For any fixed number, (in our case $17$), we can use Reciprocity to characterize all the primes $p$ such that $(17\mid p)=1$.

Note that $2$ is a QR of $17$. For odd primes $p$, we have $(17\mid p)=(p\mid 17)$. So the answer depends only on the congruence class of $p$ modulo $17$. Now we go through all $16$ possibilities.

We can use machinery, but it is sufficient to find the squares of $1,2,3,\dots,8$ modulo $17$.

Answer 3

Claim. Every prime is a quadratic residue / a non-quadratic residue for some other primes.

Lemma. If $p$ is an odd prime and $\eta_p$ denotes the least quadratic non-residue $\!\!\pmod{p}$, then $\eta_p$ is a prime.

Proof. If we assume that $\eta_p$ is a composite number, from the multiplicativity of the Legendre symbol and $\left(\frac{\eta_p}{p}\right)=-1$ we get that at least one prime divisor of $\eta_p$ has to be a non-quadratic residue $\!\!\pmod{p}$. That contradicts the minimality of $\eta_p$.

Lemma. By denoting as $\mathcal{P}$ the set of prime number, the map $\mathfrak{m}:\mathcal{P}\to\mathcal{P}$ defined by $\mathfrak{m}(p)=\eta_p$ is surjective.

Proof. Assuming that some prime $q$ does not belong to the range of $\mathfrak{m}$ we have that $q$ is a fake square. But fake squares do not exist, due to quadratic reciprocity and the weak version of Dirichlet's theorem, stating that for every prime $p$ there is some prime $q\equiv 1\pmod{p}$. The weak version of Dirichlet's theorem can be proved in a elementary way through cyclotomic polynomials.

This settles the second part of the initial claim: every prime is a quadratic non-residue (the least quadratic non-residue) for some other prime. Let us settle the first part of the claim, too.

Given a prime $p$, there is some prime $q$ fulfilling $q\equiv 1\pmod{4p}$.
By quadratic reciprocity and the periodicity of Legendre symbol, $$ \left(\frac{p}{q}\right) = \left(\frac{q}{p}\right)=\left(\frac{1}{p}\right)=1 $$ hence $p$ is a quadratic residue $\!\!\pmod{q}$. $\square$

---

$17$ is a quadratic residue for the following primes:

$$2,\quad 13,\quad 19,\quad 43,\quad 47,\quad 53,\quad 59,\quad 67,\quad 83,\quad 89,\quad 101,\quad103,\quad\ldots $$ and by Chebotarev's theorem the relative density in $\mathcal{P}$ of the set of primes such that $\left(\frac{17}{p}\right)=1$ is $\frac{1}{2}$. Additionally, for any prime $q$ the least prime $q$ such that $\left(\frac{p}{q}\right)=1$ is rarely much larger than $\log p$. Assuming the Generalized Riemann Hypothesis, by Marek Wolf's improvement of Ankeny's bound (see Bober, Goldmakher) we have that for any prime $p$ large enough $$ \min\left\{q\in\mathcal{P}:\left(\frac{p}{q}\right)=1\right\}\leq 2\log^2 p.$$