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

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

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$$

1. 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:

$$$$\left( \frac{p_i}q \right) \left( \frac q{p_i} \right) =(-1)^{\frac{(p_i-1)(q-1)}4}$$$$

And the following result can be easily verified the way you prove the Gauss lemma: $$$$\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}$$$$

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$$

1. 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)$$

1. 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$$.