Modular Arithmetic

$\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 (q_a, r_a) and (q_b, r_b) be the quotient-remainder pairs of a and b w.r.t. p respectively. We have

p | a - b $\displaystyle \iff$ p | (q_a - q_b)p + r_a - r_b $\displaystyle \iff$ p | r_a - r_b

(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$ r_a = r_b

(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}$ (n²) arithmetic operations in $\bf k$ .

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 p^e of the prime p then we have

$\displaystyle \phi$ (m) = (p - 1)p^e-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

a^p $\displaystyle \equiv$ a mod p

(23)

Moreover if p does not divide a then we have a^p-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

a^p = ((a - 1) + 1)^p $\displaystyle \equiv$ (a - 1)^p + 1^p $\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$ a^p-2mod p

(25)

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