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 \in I$$ (96)

usually denoted by

$$a \ \equiv \ b \mod{\, I}$$ (97)

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

$$\overline{a} + \overline{b} \ = \ \overline{a+b} \ \ \ \ {\rm and} \ \ \ \ \overline{a} \overline{b} \ = \ \overline{ab}$$ (98)

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 \ \mid \ a - b \ \ \iff \ \ p \ \mid \ (q_a - q_b) p + r_a - r_b \ \ \iff \ \ p \ \mid \ r_a - r_b$$ (99)

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

$$a \ \equiv \ b \mod{\, p} \ \ \iff \ \ r_a \ = \ r_b$$ (100)

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)$$ (101)

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

$$a \ \equiv \ b \mod{\, p} \ \ \iff \ \ a(u) \ = \ b(u)$$ (102)

Proposition 8   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$$ (103)

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

$$a \, b \equiv 1 \mod{\, m}$$ (104)

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 7   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 9   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^2)$ arithmetic operations in ${\bf k}$ .

Explain why!

Remark 8   Let $m$ be a positive integer. The set

$$({\mbox{${\mathbb{Z}}$}}/m)^{\ast} \ = \ \{ a \mod{\, m} \ \mid \ {\gcd}(a,m) = 1 \}$$ (105)

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)^{\ast}$ . 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

$${\phi}(m) \ = \ (p-1) p^{e-1}$$ (106)

Explain why!

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

$$a^p \ \equiv \ a \mod{\, p}$$ (107)

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 \cdots 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 \equiv (a-1)^p + 1^p \equiv (a-1) + 1 = a \mod{\, p}$$ (108)

$\qedsymbol$

Remark 9   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 6 that the inverse of $a \mod{\, p}$ can be computed by

$$a^{-1} \ \equiv \ a^{p-2} \mod{\, p}$$ (109)

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