Algebra Solutions: AADF: Chapter 0

A program to perform modular arithmetic

Write a computer program to add and multiply mod n, for any n given as input. The output of these operations should be the least residues of the sums and products of the two integers. Also include the feature that if $\mathsf{gcd}(a,n) = 1$ , an integer $c$ between 0 and $n-1$ such that $ac = 1$ mod n may be printed on request.

mod :: Integer -> Integer -> Integer

mod a n'

 | a < 0     = mod (a+n) n

 | a > n     = mod (a-n) n

 | otherwise = a

 where n = abs n'

plusMod :: Integer -> Integer -> Integer -> Integer

plusMod n a b = mod (a+b) n

timesMod :: Integer -> Integer -> Integer -> Integer

timesMod n a b = mod (a*b) n

invMod :: Integer -> Integer -> Maybe Integer

invMod a n 

 = if (gcd a n) /= 1 

    then Nothing 

    else Just $ foo $ fst $ bezout a n

   where foo k = if k < 0 then (k+n) else k

Compute inverses in ZZ/(n)

For each of the following pairs of integers $a$ and $n$ , show that $a$ is relatively prime to $n$ and determine the multiplicative inverse of $a$ mod $n$ .

$a = 13, n = 20$
$a = 69, n = 89$
$a = 1891, n = 3797$
$a = 6003722857, n = 77695236973$

First we note the following simple lemma: for all integers $a,b,x,y$ , we have that $\mathsf{gcd}(a,b)|ax+by$ . The proof is simple; if $\mathsf{gcd}(a,b) = d$ , we have $a = dn$ and $b = dm$ so that $ax + by = dnx + dmy = d(nx + my)$ .
This lemma will allow us to use the Bezout program written previously to solve these problems without having a proof of correctness for the code; if we have $ax + by = 1$ , then the $x$ and $y$ serve as a witness to the fact that $\mathsf{gcd}(a,b) = 1$ .

$a = 13, n = 20$
$\mathsf{gcd}(a,n) = 1$ since $(-3)13 + (2)20 = 1$ . Reducing mod 20, we have that $17 \cdot 13 = (-3) \cdot 13 = 1$ .
$a = 69, n = 89$
$\mathsf{gcd}(a,n) = 1$ since $(40)69 + (-31)89 = 1$ . Reducing mod 89, we have that $40 \cdot 69 = 1$ .
$a = 1891, n = 3797$
$\mathsf{gcd}(a,n) = 1$ since $(253)1891 + (-126)3797 = 1$ . Reducing mod 3797, we have that $253 \cdot 1891 = 1$ .
$a = 6003722857, n = 77695236973$
$\mathsf{gcd}(a,n) = 1$ since
$(-220)6003722857 + (17)77695236973 = 1$ . Reducing mod $77695236973$ , we have that
$-220 \cdot 6003722857 = 77695236753 \cdot 6003722857 = 1$ .

Compute the units in ZZ/(n)

Conclude from two previous theorems [here and here] that $(\mathbb{Z}/(n))^\times$ is the set of elements $\overline{a} \in \mathbb{Z}/(n)$ with $\mathsf{gcd}(a,n) = 1$ . Verify this directly in the case $n = 12$ .

By definition,
$(\mathbb{Z}/(n))^\times = \{ \overline{a} \in \mathbb{Z}/(n) \ |\ \overline{a} \cdot \overline{c} = \overline{1} \ \mathrm{for\ some}\ \overline{c} \in \mathbb{Z}/(n) \}$ .
Suppose $\overline{a} \in (\mathbb{Z}/(n))^\times$ . We must have $\mathsf{gcd}(a,n) = 1$ since otherwise we have a contradiction. Moreover, if $\mathsf{gcd}(a,n) = 1$ then there exists $\overline{c} \in \mathbb{Z}/(n)$ such that $\overline{a} \cdot \overline{c} = \overline{1}$ .