# 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\phantom{\rule{veryverythickmathspace}{0ex}}(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\phantom{\rule{veryverythickmathspace}{0ex}}(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\phantom{\rule{veryverythickmathspace}{0ex}}(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 |