Quadratic nonresidue - Revision history

Vipul: Created page with '==Definition== Suppose $n$ is a natural number. A '''quadratic nonresidue''' modulo $n$ is a number $a$ (or a residue class of a number
2010-05-29T21:58:02Z

Created page with '==Definition== Suppose <math>n</math> is a natural number. A '''quadratic nonresidue''' modulo <math>n</math> is a number <math>a</math> (or a residue class of a number <mat…'

New page
==Definition==

Suppose <math>n</math> is a [[natural number]]. A '''quadratic nonresidue''' modulo <math>n</math> is a number <math>a</math> (or a residue class of a number <math>a</math>) relatively prime to <math>n</math> such that the equation:

<math>x^2 \equiv a \pmod n</math>

has no solution. Since <math>a</math> is relatively prime to <math>n</math>, it suffices to check that there is no solution with <math>x</math> relatively prime to <math>n</math>. Further, it suffices to check that there is no solution for <math>x</math> relatively prime to <math>n</math> and <math>0 \le x \le n</math>.

Note that the term ''quadratic nonresidue'' is used both for actual numbers and for residue classes. The term is ''not'' used in cases where <math>a</math> is not relatively prime to <math>n</math>.

The opposite of quadratic nonresidue is [[quadratic residue]].