Elements of Residue Class Rings#

Creation#

elt< R | k >: RngIntRes, RngIntElt -> RngIntResElt#

Create the residue class containing the integer \(k\) in residue class ring \(R\).

R ! k: RngIntRes, RngIntElt -> RngIntResElt#

Create the residue class containing \(k\) in the residue class ring \(R\). Here \(k\) is allowed to be either an integer, or an element of the finite field \({\mathbb{F}}_p\) in the case \(R = {\mathbb{Z}}/p{\mathbb{Z}}\), or an element of \(S = {\mathbb{Z}}/n{\mathbb{Z}}\) for a multiple or divisor \(n\) of \(m\) (with \(R = {{\mathbb{Z}}/m{\mathbb{Z}}}\)).

One(R): RngIntRes -> RngIntResElt#
Identity(R): RngIntRes -> RngIntResElt#
Zero(R): RngIntRes -> RngIntResElt#
Representative(R): RngIntRes -> RngIntResElt#

These generic functions (cf. Chapter Introduction to Rings) create \(1\), \(1\), \(0\), and \(0\) respectively, in any \({{\mathbb{Z}}/m{\mathbb{Z}}}\).

Random(R): RngIntRes -> RngIntResElt#

Create a “random” residue class in \(R\).

Arithmetic Operators#

+ n: RngIntResElt -> RngIntResElt#
- n: RngIntResElt -> RngIntResElt#
m + n: RngIntResElt, RngIntResElt -> RngIntResElt#
m - n: RngIntResElt, RngIntResElt -> RngIntResElt#
m * n: RngIntResElt, RngIntResElt -> RngIntResElt#
n ^ k: RngIntResElt, RngIntResElt -> RngIntResElt#
m / n: RngIntResElt, RngIntResElt -> RngIntResElt#
m div n: RngIntResElt, RngIntResElt -> RngIntResElt#
m +:= n: RngIntResElt, RngIntResElt -> RngIntResElt#
m -:= n: RngIntResElt, RngIntResElt -> RngIntResElt#
m *:= n: RngIntResElt, RngIntResElt -> RngIntResElt#
m /:= n: RngIntResElt, RngIntResElt -> RngIntResElt#
m ^:= k: RngIntResElt, RngIntResElt -> RngIntResElt#

Equality and Membership#

m eq n: RngIntResElt, RngIntResElt -> BoolElt#
m ne n: RngIntResElt, RngIntResElt -> BoolElt#
n in R: RngIntResElt, Rng -> BoolElt#
n notin R: RngIntResElt, Rng -> BoolElt#

Parent and Category#

Parent(n): RngIntResElt -> RngIntRes#
Category(n): RngIntResElt -> Cat#

Predicates on Ring Elements#

IsZero(n): RngIntResElt -> BoolElt#
IsOne(n): RngIntResElt -> BoolElt#
IsMinusOne(n): RngIntResElt -> BoolElt#
IsNilpotent(n): RngIntResElt -> BoolElt#
IsIdempotent(n): RngIntResElt -> BoolElt#
IsUnit(n): RngIntResElt -> BoolElt#
IsZeroDivisor(n): RngIntResElt -> BoolElt#
IsRegular(n): RngIntRes -> BoolElt#
IsIrreducible(n): RngIntResElt -> BoolElt#
IsPrime(n): RngIntResElt -> BoolElt#

Solving Equations over \({\mathbb{Z}}/m{\mathbb{Z}}\)#

Solution(a, b): RngIntResElt, RngIntResElt -> RngIntResElt#

Given elements \(a\) and \(b\) of \({\mathbb{Z}}/m{\mathbb{Z}}\), return a solution \(x\) to the linear congruence \(a\cdot x=b \in {{\mathbb{Z}}/m{\mathbb{Z}}}\). An error is signalled if no solution exists.

IsSquare(n): RngIntResElt -> BoolElt, RngIntResElt#
Factorization: [<RngIntElt, RngIntElt>]                    Default: [ ]

Given an element \(n\in{{\mathbb{Z}}/m{\mathbb{Z}}}\) this function returns true if there exists \(a\in{{\mathbb{Z}}/m{\mathbb{Z}}}\) such that \(a^2=n\in{{\mathbb{Z}}/m{\mathbb{Z}}}\), false otherwise. If \(n\) is a square, a square root \(a\) is also returned. If \(m\) is large and its prime factorization is known, the computation may be speeded up by assigning the factorization sequence for \(m\) to the optional argument Factorization.

Sqrt(a): RngIntResElt -> RngIntResElt#
SquareRoot(a): RngIntResElt -> RngIntResElt#
Factorization: [<RngIntElt, RngIntElt>]                    Default: [ ]

Given an element \(a\) of the ring \({\mathbb{Z}}/m{\mathbb{Z}}\), this function returns an element \(b\) of \({\mathbb{Z}}/m{\mathbb{Z}}\) such that \(b^2=a\in{{\mathbb{Z}}/m{\mathbb{Z}}}\), if such an element exists, and an error otherwise. If \(m\) is large and its prime factorization is known, the computation may be speeded up by assigning the factorization sequence for \(m\) to the optional argument Factorization.

AllSquareRoots(a): RngIntResElt -> [ RngIntResElt ]#
AllSqrts(a): RngIntResElt -> [ RngIntResElt ]#
Factorization: [<RngIntElt, RngIntElt>]                    Default: [ ]

Return a sequence containing all square roots of the element \(a\) in a residue class ring \({\mathbb{Z}}/m{\mathbb{Z}}\). If the modulus \(m\) is large and its prime factorization is known, the computation may be speeded up by assigning the factorization sequence for \(m\) to the optional argument Factorization.

Example: Element Ops (ex-c52d75)#

We construct the residue class ring having modulus \(2340\) and find all the square roots of \(1404\).

> R := ResidueClassRing(2340);
Residue class ring of integers modulo 2340
> x := R!1404;
> sqrts := AllSquareRoots(x);
> sqrts;
[ 78, 312, 468, 702, 858, 1092, 1248, 1482, 1638,
  1872, 2028, 2262 ]
> [ y^2 : y in sqrts ];
[ 1404, 1404, 1404, 1404, 1404, 1404, 1404, 1404,
  1404, 1404, 1404, 1404 ]

Run in calculator

So 1404 has 12 square roots!

On this page