Suppose an integer x is a square modulo every prime, show that x is a square integer

Question

I was looking at Is every non-square integer a primitive root modulo some odd prime? (the answer by Hagen von Eitzen) but its a bit too concise so im having a hard time understanding it.

Could someone expand/rewrite his answer or offer another one. In particular

• im not sure why $(\frac{a}{b}) =1$ for almost all primes
• why its determind by $q$ mod $8b$
• confused on the CRT portion

Answer 1

Okay, I will rewrite (and elaborate) on the mentioned solution as below

1. Let $n$ be a non-square. Write $n=a^2b$ with $b\ne 1$ square-free. Write $b=p_1\cdot\ldots\cdot p_m$ as product of disctinct primes with $m\ge 1$.

2. For primes $q> n$ the factor $a^2$ can be ignored, as $\left( \frac{a^2b}{q} \right)= \left( \frac{a^2}q \right)\left( \frac bq \right) =1 \times \left( \frac bq \right) =\left( \frac bq \right)$.

The reason $a^2$ can be ignored for almost all q is that we are only considering $q>n$, otherwise $q$ may be divided by $a$, so $\left( \frac{a^2}q \right) = 0$ instead of $1$

3. According to quadratic reciprocity law, $ \left(\frac{b}{q}\right)$ is determined by $q\bmod 8b$.

This is true because $\left( \frac bq \right) = \Pi_{i=1}^n \left( \frac{p_i}{q} \right)$. But the quadratic reciprocity law states that:

\begin{equation} \left( \frac{p_i}q \right) \left( \frac q{p_i} \right) =(-1)^{\frac{(p_i-1)(q-1)}4}\end{equation}

And the following result can be easily verified the way you prove the Gauss lemma: \begin{equation} \left( \frac q{p_i} \right) = (-1)^{\frac{{p_i}^2-1}8 (q-1)+\sum_{k=1}^{p_i'} \lfloor \frac{ka}{p_i} \rfloor}\end{equation}

wherein $p_i'=\frac{p_i-1}2$

Therefore, it is easy to see that $\left( \frac q{p_i} \right)$ is determined by $q \bmod 8p_i$, and since $p_i$ does not repeat itself in the expansion of $b$, $\left( \frac bq \right)$ is determined by $ q \bmod 8b $

4. Also, there is at least one residue $d\bmod 8b$ for which $q\equiv d\pmod{8b}$ implies $ \left(\frac{b}{q}\right)=-1$ (e.g. ensure $\left(\frac d{p_1}\right)=-1$ and $\left(\frac d{p_i}\right)=+1$ for all other $i$ and use the chinese remainder theorem).

In the bracket, the solver tried to point out the existence of $d$. So we find $\left( \frac{d_1}{p_1} \right) =1$ and $\left( \frac{d_i}{p_i} \right) =(-1), \forall i \neq 1$, then apply CRT to find $d\equiv d_i, \forall i$ that $\left( \frac{d}{b} \right) = \pi_{i=1}^n \left( \frac{d_i}{p_i} \right) = (-1) $

5. Especially, $d$ is relatively prime to $8b$ so that by Dirichlet there exist infinitely many primes $q$ with $q\equiv d\pmod{8b}$. For such a $q$ with $q>n$ we conclude that $n$ is not a square modulo $q$.