Modular Arithmetic

Example 2 Let R mathend000# be an Euclidean domain and let p $\in$ R mathend000# with p $\neq$ 0 mathend000#. We consider the ideal I mathend000# generated by p mathend000#. The residue class ring R/I mathend000# is often denoted by R/p mathend000# and the class of a $\in$ R mathend000# in R/p mathend000# by a mod p mathend000#. For a, b $\in$ R mathend000# the relation a - b $\in$ I mathend000# means that a - b mathend000# is a multiple of p mathend000#. Let (q_a, r_a) mathend000# and (q_b, r_b) mathend000# be the quotient-remainder pairs of a mathend000# and b mathend000# w.r.t. p mathend000# 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

(99)

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

a $\displaystyle \equiv$ b mod p $\displaystyle \iff$ r_a = r_b

(100)

Explain why!

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

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

(101)

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

a $\displaystyle \equiv$ b mod p $\displaystyle \iff$ a(u) = b(u)

(102)

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

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

s a + t m = g

(103)

If g = 1 mathend000# then s mod m mathend000# is the inverse of a mod m mathend000#. Conversely if a mod m mathend000# is invertible there exists b $\in$ R mathend000# such that

a b $\displaystyle \equiv$ 1 mod m

(104)

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

Remark 7 The above remarks and proposition lead us to the following ALDOR implementation of the residue class ring of an Euclidean domain R mathend000# 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 9 Let $\bf k$ mathend000# be a field and f $\in$ $\bf k$ [x] mathend000# with degree n $\in$ $\mbox{${\mathbb N}$}$ mathend000#. One arithmetic operation in the residue class ring $\bf k$ [x]/f mathend000#, that is, addition, multiplication or division by an invertible element can be done using $\cal {O}$ (n²) mathend000# arithmetic operations in $\bf k$ mathend000#.

Remark 8 Let m mathend000# be a positive integer. The set

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

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

$\displaystyle \phi$ (m) = (p - 1)p^e-1

(106)

Explain why!

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

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

(107)

Moreover if p mathend000# does not divide a mathend000# then we have a^p-1 $\equiv$ 1 mod p mathend000#.

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

a^p = ((a - 1) + 1)^p $\displaystyle \equiv$ (a - 1)^p +1^p $\displaystyle \equiv$ (a - 1) + 1 = a mod p

(108)

$\qedsymbol$

Remark 9 For a prime p $\in$ $\mbox{${\mathbb N}$}$ mathend000# and a $\in$ $\mbox{${\mathbb Z}$}$ mathend000# such that a $\neq$ 0 mathend000# and such that p mathend000# does not divide a mathend000#. It follows from Theorem 6 that the inverse of a mod p mathend000# can be computed by

a^-1 $\displaystyle \equiv$ a^p-2mod p

(109)

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