# any nonzero integer is quadratic residue

Theorem.  For every nonzero integer $a$ there exists an odd prime number $p$ such that $a$ is a quadratic residue modulo $p$.

Proof.$1^{\circ}.$$a=2$.  We see that  $3^{2}\equiv 2\pmod{7}$  and $7\nmid 2$,  whence 2 is a quadratic residue modulo $7$.
$2^{\circ}.$$2\mid a$  but  $a\neq 2$.  The number  $1^{2}-a=1-a$  (which is odd and $\neq\pm 1$) has an odd prime factor $p$ which does not divide $a$.  Thus $a$ is a quadratic residue modulo $p$.
$3^{\circ}.$$a=3$.  We state that  $4^{2}-3=13\equiv 0\pmod{13}$  and  $13\nmid 3$.  Therefore 3 is a quadratic residue modulo 13.
$4^{\circ}.$$a=5$.  We see that  $4^{2}-5=11\equiv 0\pmod{11}$  and  $11\nmid 5$, i.e. 5 is a quadratic residue modulo 11.
$5^{\circ}.$$2\nmid a$  but  $a\neq 3$,  $a\neq 5$.  Now the number  $2^{2}-a=4-a$  (which is odd and $\neq\pm 1$) has an odd prime factor $p$.  Moreover, $p\nmid a$  since  $p\nmid 4$.  Accordingly, $a$ is a quadratic residue modulo $p$.

Title any nonzero integer is quadratic residue AnyNonzeroIntegerIsQuadraticResidue 2013-03-22 18:01:03 2013-03-22 18:01:03 pahio (2872) pahio (2872) 6 pahio (2872) Theorem msc 11A15 FundamentalTheoremOfArithmetic