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(mod7)$  and $7\nmid 2$,  whence 2 is a quadratic residue modulo $7$.
$2^{\circ }.$  $2\mid a$  but  $a\ne 2$.  The number  $1^2-a=1-a$  (which is odd and $\ne \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(mod13)$  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(mod11)$  and  $11\nmid 5$, i.e. 5 is a quadratic residue modulo 11.
$5^{\circ }.$  $2\nmid a$  but  $a\ne 3$,  $a\ne 5$.  Now the number  $2^2-a=4-a$  (which is odd and $\ne \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
Canonical name	AnyNonzeroIntegerIsQuadraticResidue
Date of creation	2013-03-22 18:01:03
Last modified on	2013-03-22 18:01:03
Owner	pahio (2872)
Last modified by	pahio (2872)
Numerical id	6
Author	pahio (2872)
Entry type	Theorem
Classification	msc 11A15
Related topic	FundamentalTheoremOfArithmetic