Quadratic Residue/Examples/61

Example of Quadratic Residues

The set of quadratic residues modulo $61$ is:

$\set {1, 3, 4, 5, 9, 12, 13, 14, 15, 16, 19, 20, 22, 25, 27, 34, 36, 39, 41, 42, 45, 46, 47, 48, 49, 53, 56, 57, 58, 60}$

This sequence is A010422 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).

Proof

From Square Modulo n Congruent to Square of Inverse Modulo n, to list the quadratic residues of $61$ it is sufficient to work out the squares $1^2, 2^2, \dotsc, \paren {\dfrac {60} 2}^2$ modulo $61$.

So:

\(\ds 1^2\)

\(\equiv\)

\(\ds 1\)

\(\ds \pmod {61}\)

\(\ds 2^2\)

\(\equiv\)

\(\ds 4\)

\(\ds \pmod {61}\)

\(\ds 3^2\)

\(\equiv\)

\(\ds 9\)

\(\ds \pmod {61}\)

\(\ds 4^2\)

\(\equiv\)

\(\ds 16\)

\(\ds \pmod {61}\)

\(\ds 5^2\)

\(\equiv\)

\(\ds 25\)

\(\ds \pmod {61}\)

\(\ds 6^2\)

\(\equiv\)

\(\ds 36\)

\(\ds \pmod {61}\)

\(\ds 7^2\)

\(\equiv\)

\(\ds 49\)

\(\ds \pmod {61}\)

\(\ds 8^2\)

\(\equiv\)

\(\ds 3\)

\(\ds \pmod {61}\)

\(\ds 9^2\)

\(\equiv\)

\(\ds 20\)

\(\ds \pmod {61}\)

\(\ds 10^2\)

\(\equiv\)

\(\ds 39\)

\(\ds \pmod {61}\)

\(\ds 11^2\)

\(\equiv\)

\(\ds 60\)

\(\ds \pmod {61}\)

\(\ds 12^2\)

\(\equiv\)

\(\ds 22\)

\(\ds \pmod {61}\)

\(\ds 13^2\)

\(\equiv\)

\(\ds 47\)

\(\ds \pmod {61}\)

\(\ds 14^2\)

\(\equiv\)

\(\ds 13\)

\(\ds \pmod {61}\)

\(\ds 15^2\)

\(\equiv\)

\(\ds 42\)

\(\ds \pmod {61}\)

\(\ds 16^2\)

\(\equiv\)

\(\ds 12\)

\(\ds \pmod {61}\)

\(\ds 17^2\)

\(\equiv\)

\(\ds 45\)

\(\ds \pmod {61}\)

\(\ds 18^2\)

\(\equiv\)

\(\ds 19\)

\(\ds \pmod {61}\)

\(\ds 19^2\)

\(\equiv\)

\(\ds 56\)

\(\ds \pmod {61}\)

\(\ds 20^2\)

\(\equiv\)

\(\ds 34\)

\(\ds \pmod {61}\)

\(\ds 21^2\)

\(\equiv\)

\(\ds 14\)

\(\ds \pmod {61}\)

\(\ds 22^2\)

\(\equiv\)

\(\ds 57\)

\(\ds \pmod {61}\)

\(\ds 23^2\)

\(\equiv\)

\(\ds 41\)

\(\ds \pmod {61}\)

\(\ds 24^2\)

\(\equiv\)

\(\ds 27\)

\(\ds \pmod {61}\)

\(\ds 25^2\)

\(\equiv\)

\(\ds 15\)

\(\ds \pmod {61}\)

\(\ds 26^2\)

\(\equiv\)

\(\ds 5\)

\(\ds \pmod {61}\)

\(\ds 27^2\)

\(\equiv\)

\(\ds 58\)

\(\ds \pmod {61}\)

\(\ds 28^2\)

\(\equiv\)

\(\ds 52\)

\(\ds \pmod {61}\)

\(\ds 29^2\)

\(\equiv\)

\(\ds 48\)

\(\ds \pmod {61}\)

\(\ds 30^2\)

\(\equiv\)

\(\ds 46\)

\(\ds \pmod {61}\)

So the set of quadratic residues modulo $61$ is:

$\set {1, 3, 4, 5, 9, 12, 13, 14, 15, 16, 19, 20, 22, 25, 27, 34, 36, 39, 41, 42, 45, 46, 47, 48, 49, 53, 56, 57, 58, 60}$

The set of quadratic non-residues of $61$ therefore consists of all the other non-zero least positive residues:

$\set {2, 6, 7, 8, 10, 11, 17, 18, 21, 23, 24, 26, 28, 29, 30, 31, 32, 33, 35, 37, 38, 40, 43, 44, 50, 51, 52, 54, 55, 59}$

This sequence is A028774 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).

$\blacksquare$

Sources

• 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {3-5}$ The Use of Computers in Number Theory: Exercise $6$