 NumberTheory - Maple Programming Help

Home : Support : Online Help : Mathematics : Number Theory : NumberTheory/ModularSquareRoot

NumberTheory

 ModularSquareRoot
 modular square root

 Calling Sequence ModularSquareRoot(x, n)

Parameters

 x - integer n - positive integer

Description

 • The ModularSquareRoot function computes a non-negative integer $y$ such that ${y}^{2}=x\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}n$ if possible. If not possible, an error message is displayed.
 • When x has more than one square root, any one of them may be returned.

Examples

 > with(NumberTheory):

The follow numbers have square roots modulo $37$.

 > residues := {seq(i^2 mod 37, i = 0..36)};
 ${\mathrm{residues}}{≔}\left\{{0}{,}{1}{,}{3}{,}{4}{,}{7}{,}{9}{,}{10}{,}{11}{,}{12}{,}{16}{,}{21}{,}{25}{,}{26}{,}{27}{,}{28}{,}{30}{,}{33}{,}{34}{,}{36}\right\}$ (1)

$30$ has a square root modulo $37$.

 > evalb(30 in residues);
 ${\mathrm{true}}$ (2)
 > ModularSquareRoot(30, 37);
 ${17}$ (3)
 > 17^2 mod 37;
 ${30}$ (4)

$24$ does not have a square root modulo $37$ and so an error message is displayed.

 > evalb(24 in residues);
 ${\mathrm{false}}$ (5)
 > ModularSquareRoot(24, 37);

Compatibility

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