next up previous
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 $ \in$ R the relation

a - b $\displaystyle \in$ I (12)

usually denoted by

a  $\displaystyle \equiv$  b mod I (13)

defines an equivalence relation. If we denote by $ \overline{{a}}^{{I}}_{{}}$ (or $ \overline{{a}}$ 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

$\displaystyle \overline{{a}}$ + $\displaystyle \overline{{b}}$  =  $\displaystyle \overline{{a+b}}$    and    $\displaystyle \overline{{a}}$$\displaystyle \overline{{b}}$  =  $\displaystyle \overline{{ab}}$ (14)

Example 2   Let R be an Euclidean domain and let p $ \in$ R with p $ \neq$ 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 $ \in$ R in R/p by a mod p. For a, b $ \in$ R the relation a - b $ \in$ 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  $\displaystyle \iff$  p  |  (qa - qb)p + ra - rb  $\displaystyle \iff$  p  |  ra - rb (15)

For R = $ \mbox{${\mathbb Z}$}$ with positive remainder or for R = $ \bf k$[x] we have in fact

a  $\displaystyle \equiv$  b mod p  $\displaystyle \iff$  ra  =  rb (16)

Explain why!

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

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

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

a  $\displaystyle \equiv$  b mod p  $\displaystyle \iff$  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 $ \in$ R such that

a b $\displaystyle \equiv$ 1 mod m (20)

That is there exists c $ \in$ 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. $ \qedsymbol$

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;
} == R add {
        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 $ \bf k$ be a field and f $ \in$ $ \bf k$[x] with degree n $ \in$ $ \mbox{${\mathbb N}$}$. One arithmetic operation in the residue class ring $ \bf k$[x]/f, that is, addition, multiplication or division by an invertible element can be done using $ \cal {O}$(n2) arithmetic operations in $ \bf k$.

Explain why!

Remark 5   Let m be a positive integer. The set

($\displaystyle \mbox{${\mathbb Z}$}$/m) *   =  {a mod m  |  gcd(a, m) = 1} (21)

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

$\displaystyle \phi$(m)  =  (p - 1)pe-1 (22)

Explain why!

Theorem 1 (Fermat's little theorem)   If p $ \in$ $ \mbox{${\mathbb N}$}$ is a prime and a $ \in$ $ \mbox{${\mathbb Z}$}$ then we have

ap  $\displaystyle \equiv$  a mod p (23)

Moreover if p does not divide a then we have ap-1  $ \equiv$  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 $\displaystyle \equiv$ (a - 1)p + 1p $\displaystyle \equiv$ (a - 1) + 1 = a mod p (24)

$ \qedsymbol$

Remark 6   For a prime p $ \in$ $ \mbox{${\mathbb N}$}$ and a $ \in$ $ \mbox{${\mathbb Z}$}$ such that a $ \neq$ 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  $\displaystyle \equiv$  ap-2mod p (25)

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


next up previous
Next: Modular Algorithms and interpolation Up: The Euclidean Algorithm Previous: The Extended Euclidean Algorithm
Marc Moreno Maza
2003-06-06