NumberTheory - Maple Programming Help

NumberTheory

Parameters

 a - integer n - positive integer

Description

 • The QuadraticResidue(a, n) command returns $1$ if a is a quadratic residue modulo n, and returns $-1$ if a is a quadratic non-residue modulo n.
 • If there exists an integer $b$ such that ${b}^{2}$ is congruent to a modulo n, then a is said to be a quadratic residue modulo n. If there does not exist such a $b$, then a is said to be a quadratic non-residue modulo n.

Examples

 > $\mathrm{with}\left(\mathrm{NumberTheory}\right):$

Numbers congruent to a perfect square are always quadratic residues. The converse is true as well.

 > $\mathrm{QuadraticResidue}\left(11,22\right)$
 ${1}$ (1)
 > $121\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}22$
 ${11}$ (2)
 > $\mathrm{QuadraticResidue}\left(22,11\right)$
 ${1}$ (3)

$12$ is a quadratic residue modulo $24$.

 > $\mathrm{QuadraticResidue}\left(12,24\right)$
 ${1}$ (4)
 > ${6}^{2}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}24$
 ${12}$ (5)

$3$ is not a quadratic residue modulo $7$.

 > $\mathrm{QuadraticResidue}\left(3,7\right)$
 ${-1}$ (6)
 > $\mathrm{seq}\left({a}^{2}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}7,a=0..6\right)$
 ${0}{,}{1}{,}{4}{,}{2}{,}{2}{,}{4}{,}{1}$ (7)

In the following plot, for each row index i and column index j, if the box indexed by i and j is black then j is a quadratic residue modulo i. If the box is white then j is a quadratic non-residue modulo i.

 > $Q≔\mathrm{Matrix}\left(100,100,\left(i,j\right)→\mathrm{if}\left(i
  (8)
 > $\mathrm{Statistics}:-\mathrm{HeatMap}\left(Q,\mathrm{colour}=\left[\mathrm{white},\mathrm{black}\right]\right)$

Compatibility

 • The NumberTheory[QuadraticResidue] command was introduced in Maple 2016.