Elements of Residue Class Rings

Contents

Creation

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

These generic functions create 1, 1, 0, and 0 respectively, in any Z/mZ.

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 Fp in the case R = Z/pZ, or an element of S = Z/nZ for a multiple or divisor n of m (with R = Z/mZ).
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 Z/mZ

Solution(a, b) : RngIntResElt, RngIntResElt -> RngIntResElt
Given elements a and b of Z/mZ, return a solution x to the linear congruence a.x=b ∈Z/mZ. An error is signalled if no solution exists.
IsSquare(n) : RngIntResElt -> BoolElt, RngIntResElt
    Factorization: [<RngIntElt, RngIntElt>] Default: [ ]
Given an element n∈Z/mZ this function returns true if there exists a∈Z/mZ such that a2=n∈Z/mZ, 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 Z/mZ, this function returns an element b of Z/mZ such that b2=a∈Z/mZ, 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 Z/mZ. 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 RngIntRes_element-ops (H20E4)

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 ]

So 1404 has 12 square roots!

V2.28, 13 July 2023