# 13.1: Modular Arithmetic and Number Theory

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

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 ≡143. 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 ∈ ℤnthere must be a y ∈ ℤn so that xyn 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 + bnn ax + 0

(since bnn 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−1n 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−1kn = 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−1144 −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 Zpq 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,2p,3p,. . . , (q − 1)p. There are q elements in this list.
• The multiples of q share a common divisor with pq. These include 0,q,2q,3q,. . . , (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 xppxfor all x, when p is prime.2

2You have to handle the case of xp 0 separately, since 0 ∉ ℤp so Euler’s theorem doesn’t apply to it.

13.1: Modular Arithmetic and Number Theory is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek.