I want to proof the following: Let $\left(\frac{a}{n}\right)$ denote the Jacobisymbol of $a$ and $n$. Then I want to show that $n$ is a square $\Leftrightarrow \left(\frac{a}{n}\right) \neq -1 \forall a.$
$\Rightarrow$: If $n = m^2$ for some $m$ then $\left(\frac{a}{n}\right) = \left(\frac{a}{m^2}\right) = \left(\frac{a}{m}\right)^2 \in\left\{0,1\right\}$.
$\Leftarrow$: Let $n$ be not a square. Then we find an odd prime $p$ and an odd integer $u$, such that $n = p^u\cdot r$ with $p\nmid r$. Furhtermore we know that there is a $b$ which is a quadratic nonresidue mod $p$. Since $p$ is prime and no divisor of $r$, we have $gcd(p, r) = 1$. So we can solve the congruence $ b + kp\equiv 1\pmod r $ uniquely. Then we set $a:=b+kp \pmod r$ and get $$ \left(\frac{a}{p}\right) = -1 \text{ and } \left(\frac{a}{r}\right) = 1. $$
Finally we have $$ \left(\frac{a}{n}\right) = \left(\frac{a}{p}\right)^u\cdot \left(\frac{a}{r}\right) = (-1)^u\cdot 1 = -1. $$
Now my question regards the notation. Is it correct that I write "The congruence $b+kp\equiv 1 \pmod r$"? I mean, I then get $ k\equiv (1-b)\cdot p^{-1}\pmod r$, but this is a whole residue class. Can I build the variable $a$ as I did it with that residues class?=