Next: Modular Algorithms and interpolation Up: The Euclidean Algorithm Previous: The Extended Euclidean Algorithm

## Modular Arithmetic

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

 a - b I (12)

usually denoted by

 a   b mod I (13)

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

 +   =      and      = (14)

Example 2   Let R be an Euclidean domain and let p R with p 0. We consider the ideal I generated by p. The residue class ring R/I is often denoted by R/p and the class of a R in R/p by a mod p. For a, b R the relation a - b I means that a - b is a multiple of p. Let (qa, ra) and (qb, rb) be the quotient-remainder pairs of a and b w.r.t. p respectively. We have

 p  |  a - b    p  |  (qa - qb)p + ra - rb    p  |  ra - rb (15)

For R = with positive remainder or for R = [x] we have in fact

 a   b mod p    ra  =  rb (16)

Explain why!

Example 3   Let R = [x] for a field . Let u and let I be the ideal generated by the polynomial x - u. For every a R there exists q R such that

 a  =  q(x - u) + a(u) (17)

So in that case for every a, b R we have

 a   b mod p    a(u)  =  b(u) (18)

Proposition 3   Let R be an Euclidean domain and let a, m be in R. Then a mod m is a unit of R/m iff gcd(a, m) = 1. In this case the Extended Euclidean Algorithm can be used to compute the inverse of a mod m.

Proof. Indeed, let g be the gcd of a and m and let s, t be the corresponding Bézout coefficients. Hence we have

 s a + t m = g (19)

If g = 1 then s mod m is the inverse of a mod m. Conversly if a mod m is invertible there exists b R such that

 a b 1 mod m (20)

That is there exists c R such that a b - 1 = c m. If a and m could be divided by an element d which is not a unit then we would be led to a contradiction ( d (a' b + c m') = 1). Hence gcd(a, m) = 1.

Remark 4   The above remarks and proposition lead us to the following ALDOR implementation of the residue class ring of an Euclidean domain R 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 4   Let be a field and f [x] with degree n . One arithmetic operation in the residue class ring [x]/f, that is, addition, multiplication or division by an invertible element can be done using (n2) arithmetic operations in .

Explain why!

Remark 5   Let m be a positive integer. The set

 (/m) *   =  {a mod m  |  gcd(a, m) = 1} (21)

is the group of units of the ring /m. The Euler's totient function m (m) counts the number of elements of (/m) * . By convention (1) = 1. Then if p is a prime we have (p) = p - 1. If m is a power pe of the prime p then we have

 (m)  =  (p - 1)pe-1 (22)

Explain why!

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

 ap   a mod p (23)

Moreover if p does not divide a then we have ap-1   1 mod p.

Proof. It is sufficient to prove the claim for a = 0 ... p - 1 which we do by induction on a. The cases a = 0 and a = 1 are trivial. For a > 1 we have

 ap = ((a - 1) + 1)p (a - 1)p + 1p (a - 1) + 1 = a mod p (24)

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

 a-1   ap-2mod p (25)

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

Next: Modular Algorithms and interpolation Up: The Euclidean Algorithm Previous: The Extended Euclidean Algorithm
Marc Moreno Maza
2004-04-27