Algebra Solutions: 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$ .

Algebra Solutions

Compute inverses in ZZ/(n)

No comments:

Post a Comment