## Modular Arithmetic

Let be a (commutative) ring (with unity) and be an ideal of . For the relation

 (96)

usually denoted by

 (97)

defines an equivalence relation. If we denote by (or if not ambiguous) the class of the element , then the residue classes of this relation forms a (commutative) ring (with unity) denoted by where addition and multiplication are defined by

 (98)

Example 2   Let be an Euclidean domain and let with . We consider the ideal generated by . The residue class ring is often denoted by and the class of in by . For the relation means that is a multiple of . Let and be the quotient-remainder pairs of and w.r.t. respectively. We have

 (99)

For with positive remainder or for we have in fact

 (100)

Explain why!

Example 3   Let for a field . Let and let be the ideal generated by the polynomial . For every there exists such that

 (101)

So in that case for every we have

 (102)

Proposition 8   Let be an Euclidean domain and let be in . Then is a unit of iff . In this case the Extended Euclidean Algorithm can be used to compute the inverse of .

Proof. Indeed, let be the gcd of and and let be the corresponding Bézout coefficients. Hence we have

 (103)

If then is the inverse of . Conversely if is invertible there exists such that

 (104)

That is there exists such that . If and could be divided by an element which is not a unit then we would be led to a contradiction ( ). Hence .

Remark 7   The above remarks and proposition lead us to the following ALDOR implementation of the residue class ring of an Euclidean domain by one of its element.
ResidueClassRing(R:EuclideanDomain, p:R): Ring with {
class: R -> %;
sample: % -> R;
Rep == R;
import from R;

1: % == per(1);
0: % == per(0);
zero?(x:%): Boolean == zero?(rep(x));
(x:%) = (y:%) : Boolean == zero?(x-y);
one?(x:%): Boolean == x = 1;
class(a:R):% == {
(q,r) := divide(a,p);
per(r);
}
sample(x:%): R == rep(x);
(x:%) + (y:%) : % == class(rep(x) + rep(y));
-(x:%) : % == class(-rep(x));
(x:%) * (y:%) : % == class(rep(x) * rep(y));
(n:Integer) * (x:%): % == class(n * rep(x));
(x:%) ^ (n:NonNegativeInteger) : % == class(rep(x) ^ n);
recip(x:%): Partial(%) == {
import from Partial(%);
(u,v,g) := extendedEuclidean(rep(x),p);
h?: Partial(R) := recip(g);
failed? h? => failed();
h: R := retract(h?);
[class(h * u)];
}
}


Proposition 9   Let be a field and with degree . One arithmetic operation in the residue class ring , that is, addition, multiplication or division by an invertible element can be done using arithmetic operations in .

Explain why!

Remark 8   Let be a positive integer. The set

 (105)

is the group of units of the ring . The Euler's totient function counts the number of elements of . By convention . Then if is a prime we have . If is a power of the prime then we have

 (106)

Explain why!

Theorem 6 (Fermat's little theorem)   If is a prime and then we have

 (107)

Moreover if does not divide then we have .

Proof. It is sufficient to prove the claim for which we do by induction on . The cases and are trivial. For we have

 (108)

Remark 9   For a prime and such that and such that does not divide . It follows from Theorem 6 that the inverse of can be computed by

 (109)

Explain why this leads to an algorithm requiring word operations. Is this better than the modular inversion via Euclide's algorithm?

Marc Moreno Maza
2008-01-07