Modular arithmetic and Euclid

The following statement is important for modular arithmetic:

Theorem 13 (Division theorem)

$(\forall a)(\forall b \geq 1)(\exists! q, r: 0 \leq r \leq b-1)(a = b\cdot q+ r)$.¹

The number $q$ is called integer quotient and $r$ the remainder. This just says something very intuitive: Dividing $a$ by $b$ gives us the quotient $q$ and remainder $r$.

We say that $f$ is a common divisor of $a$ and $b$ if $f \mid a$² and $f \mid b$. Integer $d$ is a greatest common divisor of $a$ and $b$ if $d$ is a common divisor of $a$ and $b$, and every common divisor of $a$ and $b$ divides $d$. We remark that the existence of a greatest common divisor is not obvious (everyone has learned them since grade school and took it for granted that they exist). But really, how can we know that there is one common divisor where everyone else divides it?

Notice that $d$ is a greatest common divisor of $a$ and $b$ iff $-d$ is also one (and these are the only two!). Denote by ${\sf gcd}(a,b)$ the unique non-negative greatest common divisor of $a$ and $b$.

Theorem 14

For all $a,b$, there exists a greatest common divisor of $a$ and $b$.

We will again show two proofs. The first proof is purely mathematical and does not directly imply an algorithm that computes a greatest common divisor. The second proof is algorithmic and the existence of a greatest common divisor in fact follows from the fact that the algorithm will be proved to return it.

First proof via algebra

For $a \in {\mathbb Z}$ denote by $a {\mathbb Z}$ the set of all multiples of $a$, e.g., $3 {\mathbb Z} = \{0, \pm 3, \pm 6, \ldots\}$. Fix integers $a, b$. We will explicitly define a greatest common divisor of $a$ and $b$. First, we claim that every set that is closed under subtraction (i.e. a subtraction of two elements in the set also belongs to the set) must be of a certain form.

Lemma 8

If $A \subseteq {\mathbb Z}$ is nonempty and closed under subtraction, then there exists $d$ such that $A = d {\mathbb Z}$.

Proof:

If $A$ is closed under subtraction, notice that

• $0 \in A$: Since $a - a \in A$ (here we use that $A$ is nonempty, do you see why?)
• $(\forall a \in A) -a \in A$ (do you see why?)
• $(\forall a,b \in A) a+b \in A$ (why?)
• $a \in A \implies a {\mathbb Z} \subseteq A$ (this can be proven by induction!)

Now, we define $d$ to be the smallest positive integer in $A$. From the last property above, we have that $d {\mathbb Z} \subseteq A$. We claim that in fact $A = d {\mathbb Z}$. Consider any number $a \in A$. Apply the division theorem (to divide $a$ by $d$) to write $a = q \cdot d + r$ where $0\leq r \leq d-1$. Notice that, since $a, q \cdot d \in A$, we know that $r \in A$. If $r >0$, this would be impossible since $r$ is positive and smaller than $d$, so we must have $r = 0$, which means that $d \mid a$, and thus $a \in d {\mathbb Z}$.

For subsets $A, B \subseteq {\mathbb Z}$, we define $A + B = \{a+b: a \in A, b \in B\}$. For instance $a {\mathbb Z} + b {\mathbb Z}$ would be exactly the set that contains all numbers of the form $\{a x + b y: x,y \in {\mathbb Z}\}$. The following property is simple to verify.

Exercise 30

The set $a {\mathbb Z} + b{\mathbb Z}$ is closed under subtraction.

The lemma implies that $d {\mathbb Z} = a {\mathbb Z} + b {\mathbb Z}$ for some $d$. We claim that $d$ is a greatest common divisor of $a$ and $b$. First, notice that $d \mid a$ because $a \in a {\mathbb Z} + b {\mathbb Z} = d {\mathbb Z}$; by the same reasoning $d \mid b$. So, $d$ is a common divisor. Now consider any common divisor $f$ of $a$ and $b$. Since $d \in a{\mathbb Z} + b {\mathbb Z}$, we know that $d = ax + by$ for some integers $x, y$. Since $f \mid a$ and $f \mid b$, we have that $f \mid d$ as well. This concludes the proof.

Notice that this proof implies the following fundamental result in elementary number theory.

Theorem 15 (Bézout's lemma)

For all $a,b$ there exist $u,v$ such that ${\sf gcd}(a,b)= a u + bv$.

Exercise 31

Let $a_1, \ldots, a_n \in {\mathbb Z}$. Prove that $a_1 {\mathbb Z} + a_2 {\mathbb Z} + \ldots + a_n {\mathbb Z} = k {\mathbb Z}$ for some $k \in {\mathbb Z}$. Determine the value of $k$ (in terms of other $a_i$'s).

Second Proof via Euclid's algorithm

Interestingly, the second proof is much older than the first one. The following efficient algorithm is due to Euclid (from around 350 B.C.)

$\mathrm{Euclidean}(a,b)$

1. $A\leftarrow a$ and $B \leftarrow b$
2. while $B\geq 1$ do
   1. $R \leftarrow A \pmod{B}$
   2. $A \leftarrow B, B \leftarrow R$
3. return $A$

Exercise 32

Given $a,b$, the algorithm always terminates in finitely many steps.

Theorem 16

The above algorithm correctly returns ${\sf gcd}(a,b)$.

We would need to develop some preliminary notation and facts to facilitate the analysis of this algorithm. For integer $a \in {\mathbb Z}$, denote by ${\sf div}(a)$ the set of all integers that divide $a$, i.e., ${\sf div}(6) = \{\pm 1, \pm 2, \pm 3, \pm 6\}$.

Lemma 9

$d$ is a greatest common divisor of $a$ and $b$ if and only if ${\sf div}(d) = {\sf div}(a) \cap {\sf div}(b)$.

Proof:

It is straightforward to show that ${\sf div}(f) \subseteq {\sf div}(a) \cap {\sf div}(b)$ for every common divisor $f$ of $a$ and $b$. The implication $\implies$ follows from this. To see the converse, suppose ${\sf div}(d) = {\sf div}(a) \cap {\sf div}(b)$. Consider any common divisor $f$ of $a$ and $b$, so we must have that $f \in {\sf div}(a) \cap {\sf div}(b)$. Therefore, $f \in {\sf div}(d)$, which means that every common divisor divides $d$. Moreover, since $d \in {\sf div}(d) = {\sf div}(a) \cap {\sf div}(b)$, $d$ is a common divisor of $a$ and $b$, so $d$ is a greatest common divisor.

For simplicity of notation, denote by ${\sf div}(a,b) = {\sf div}(a) \cap {\sf div}(b)$.

Exercise 33

Let $a, b \in {\mathbb Z}$. For all integer $q$, ${\sf div}(a,b) = {\sf div}(a-q \cdot b, b)$.

Proof (of Theorem 16:

We argue that the following is loop invariant: ${\sf div}(a,b) = {\sf div}(A,B)$ Notice that the algorithm updates $A$ to $B$ and $B$ to $R$ in the while-loop, so it suffices to argue that ${\sf div}(A,B)= {\sf div}(B,R)$. But since $R = A \pmod{B}$, we have that $R = A - q \cdot B$ for some integer $q$. From Exercise 33, we have that ${\sf div}(A,B) = {\sf div}(A- q B, B)$, so the statement is indeed a loop invariant. Using the loop invariant, when the algorithm leaves the while loop, we have that $B =0$ (recall the reminder is always nonnegative). Therefore, ${\sf div}(a,b) = {\sf div}(A,B) = {\sf div}(A, 0) = {\sf div}(A)$. Lemma 9 implies that $A$ is a greatest common divisor of $a$ and $b$.

Exercise 34

Let $B_i$ be the value of $B$ after the $i$-th iteration of the while loop in Euclid's algorithm, starting with $B_0= b$. Prove that $B_{i+2} \leq B_i/2$.

Exercise 35

Use the previous exercise, deduce that the Euclid's algorithm terminates in at most $2m$ iterations where $m$ is the number of binary digits of $b$.

Exercise 36

Given integers $A,B$, the operation $A \pmod{B}$ can be computed in time $O(n^2)$ where $n$ is the number of digits of $A$ and $B$.

These exercises imply that Euclid's algorithm is very efficient, implementable to run in time $O(n^3)$ where $n$ is the number of digits of the input. The Euclidean algorithm is a great showcase of an intimate connection between algorithms and mathematics from more than 2000 years ago (Euclid seemed to think like a computer scientist when coming up with the gcd algorithm ☺️).

Exercise 37 (Euclid's gcd lemma)

Prove that ${\sf gcd}(a,b) = {\sf gcd}(a-b,b)$.

Exercise 38

The Fibonacci number is given by $F_n = F_{n-1} + F_{n-2}$ where $F_0= 0$ and $F_1 =1$. Prove that ${\sf gcd}(F_n, F_{n-1}) = 1$ for all $n \geq 1$.

Exercise 39

We say that a sequence $a_1,a_2, \ldots$ is eventually periodic with period $k$ if there exists $n_0$ such that for all $i\ge n_0$, we have $a_i = a_{i+k}$. In other words, the sequence can be seen as infinite copies of a finite sequence. Prove: For every $m$, the Fibonacci sequence modulo $m$ is eventually periodic. The period is at most $m^2-1$.

Exercise 40

Define the sequence $g_n = 3g_{n-1} + 2g_{n-2}+ g_{n-3}$ and $g_0 = 0, g_1 = g_2= 1$. Prove that, for every integer $m$, the sequence $g_n$ modulo $m$ is eventually periodic.

Exercise 41

Let $d(n)$ be the number of positive divisors of $n$, e.g., $d(1)=1, d(2) = d(3)=d(5) = 2, d(4)=3$. Prove your answers on the following questions:

• For what values of $n$ do we have $d(n) =2$?
• For what values of $n$ do we have $d(n) =3$?

Footnotes

1. All these numbers are integers, and in this chapter numbers are integers unless stated otherwise. ↩

2. Recall that this denotes "$f$ divides $a$". ↩