# 13.1: “Dividing” Mod n

- Page ID
- 7397

In general, public-key cryptography relies on computational problems from abstract algebra. Of the techniques currently known for public-key crypto, RSA uses some of the simplest mathematical ideas, so it’s an ideal place to start. We will be working with modular arithmetic, so please review the section on modular arithmetic from the first lecture! We need to understand the behavior of the four basic arithmetic operations in the set ℤ* _{n}* = {0,. . . ,

*n*− 1}.

Every element *x* ∈ ℤ* _{n}* has an inverse with respect to addition mod

*n*: namely −

*x % n*. For example, the additive inverse of 11 mod 14 is −11 ≡

_{14}3. However, multiplicative inverses are not so straight-forward.

### Greatest Common Divisors

If *d | x* and *d | y*, then *d* is a **common divisor** of *x* and *y*. The largest possible such *d* is called the **greatest common divisor (GCD)**, denoted gcd(*x,y*). If gcd(*x,y*) = 1, then we say that *x* and *y* are **relatively prime**. The oldest “algorithm” ever documented is the one Euclid described for computing GCDs (ca. 300 BCE):

### Multiplicative Inverses

We let ℤ^{∗}_{n} denote the set {*x* ∈ ℤ* _{n}* | gcd(

*x,n*) = 1}, the

**multiplicative group modulo**

*n*. This group is

*closed under multiplication mod n*, which just means that if

*x,y*∈ ℤ

^{∗}

_{n}then

*xy*∈ ℤ

^{∗}

_{n}, where

*xy*denotes multiplication mod

*n*. Indeed, if gcd(

*x,n*) = gcd(

*y,n*) = 1, then gcd(

*xy,n*) = 1 and thus gcd(

*xy % n,n*) = 1 by Euclid’s algorithm.

In abstract algebra, a *group* is a set that is closed under its operation (in this case multiplication mod *n*), and is also closed under inverses. So if ℤ^{∗}_{n} is really a group under multiplication mod *n*, then for every *x* ∈ ℤ^{∗}_{n}there must be a *y* ∈ ℤ^{∗}_{n} so that *xy* ≡_{n} 1. In other words, *y* is the **multiplicative inverse** of *x* (and we would give it the name x^{−1}.

The fact that we can always find a multiplicative inverse for elements of ℤ^{∗}_{n} is due to the following theorem:

Theorem 13.1: Bezout’s Theorem

*For all integers x and y, there exist integers a and b such that ax* + *by* = gcd(*x,y*). *In fact,* gcd(*x,y*) *is the smallest positive integer that can be written as an integral linear combination of x and y.*

What does this have to do with multiplicative inverses? Take any *x* ∈ ℤ^{∗}_{n}; we will show how to find its multiplicative inverse. Since *x* ∈ ℤ^{∗}_{n}, we have gcd(*x,n*) = 1. From Bezout’s theorem, there exist integers *a,**b *satisfying *ax* + *bn* = 1. By reducing both sides of this equation modulo *n*, we have

1 ≡_{n}*ax* + *bn* ≡_{n}*ax* + 0

(since *bn* ≡* _{n}* 0). Thus the integer

*a*guaranteed by Bezout’s theorem is the multiplicative inverse of

*x*modulo

*n*.

We have shown that every *x* ∈ ℤ^{∗}_{n} has a multiplicative inverse mod *n*. That is, if gcd(*x,n*) = 1, then *x* has a multiplicative inverse. But might it be possible for x to have a multiplicative inverse mod *n* even if gcd(*x,n*) ≠ 1?

Suppose that we have an element *x* with a multiplicative inverse; that is, *xx*^{−1} ≡* _{n}* 1. Then

*n*divides

*xx*

^{−1}− 1, so we can write

*xx*

^{−1}− 1 =

*kn*(as an expression over the integers) for some integer

*k*. Rearranging, we have that

*xx*

^{−1}−

*kn*= 1. That is to say, we have a way to write 1 as an integral linear combination of

*x*and

*n*. From Bezout’s theorem, this must mean that gcd(

*x,n*) = 1. Hence,

*x*∈ ℤ

^{∗}

_{n}. We conclude that:

The elements of ℤ^{∗}_{n} are exactly those elements with a multiplicative inverse mod *n*.

Furthermore, multiplicative inverses can be computed efficiently using an extended version of Euclid’s GCD algorithm. While we are computing the GCD, we can also keep track of integers *a* and *b* from Bezout’s theorem at every step of the recursion; see below:

Example \(\PageIndex{1}\)

*Below is a table showing the computation of EXTGCD*(35,144). *Note that the columns x, y are computed from the top down (as recursive calls to EXTCD are made), while the columns d, a, and b are computed from bottom up (as recursive calls return). Also note that in each row, we indeed have d* = *ax* + *by.*

The final result demonstrates that 35^{−1} ≡_{144} −37 ≡_{144} 107.

### The Totient Function

Euler’s **totient** function is defined as *ϕ*(*n*) ≝ |ℤ^{∗}_{n}|, in other words, the number of elements of ℤ* _{n}* which are relatively prime to

*n*. As an example, if

*p*is a prime, then ℤ

^{∗}

_{n}= ℤ

_{n}\ {0} because every integer in ℤ

_{n}apart from zero is relatively prime to

*p*. Therefore,

\[ϕ(p) = p − 1.\]

We will frequently work modulo *n* where *n* is the product of two distinct primes *n* = *pq*. In that case, *ϕ*(*n*) = (*p* − 1)(*q* − 1). To see why, let’s count how many elements in **Z*** _{pq}* share a common divisor with

*pq*(i.e., are not in ℤ

^{∗}

_{pq}).

- The multiples of
*p*share a common divisor with*pq*. These include 0,*p*,2*p*,3*p*,. . . , (*q*− 1)*p*. There are*q*elements in this list. - The multiples of
*q*share a common divisor with*pq*. These include 0,*q*,2*q*,3*q*,. . . , (*p*− 1)*q*. There are*p*elements in this list.

We have clearly double-counted element 0 in these lists. But no other element is double counted. Any item that occurs in both lists would be a common multiple of both *p* and *q*, but the least common multiple of *p* and *q* is *pq* since *p* and *q* are relatively prime. But *pq* is larger than any item in these lists.

We count *p* + *q* − 1 elements in ℤ_{pq} which share a common divisor with *pq*. That leaves the rest to reside in ℤ^{∗}_{pq}, and there are *pq* − (*p* + *q* − 1) = (*p* − 1)(*q* − 1) of them. Hence

\[ϕ(pq) = (p − 1)(q − 1).\]

General formulas for *ϕ*(*n*) exist, but they typically rely on knowing the prime factorization of *n*. We will see more connections between the difficulty of computing *ϕ*(*n*) and the difficulty of factoring *n* later in this part of the course.

Here’s an important theorem from abstract algebra:

Theorem 13.2: Euler’s Theorem

*If x* ∈ ℤ^{∗}_{n} *then x*^{ϕ(n)} ≡* _{n}* 1.

As a final corollary, we can deduce Fermat’s “little theorem,” that *x ^{p}* ≡

_{p}*x*for all

*x*, when

*p*is prime.

^{2}

^{2}You have to handle the case of *x* ≡* _{p}* 0 separately, since 0 ∉ ℤ

^{∗}

_{p}so Euler’s theorem doesn’t apply to it.