_Posted on April 13, 2024_ ##### Introduction We may want to find the greatest common divisor between two integers $a$ and $b$. There are many applications to performing this computation quickly. One immediate application is for simplifying fractions. For example, you may have $r = \frac{2,394}{12,313}$ and want to simplify it. After finding that $\text{GCD}(2394,12313) = 7$, multiply $r$ by $\frac{1/7}{1/7} = 1$ to get $r = \frac{342}{1,759}$. RSA !! Based on the current definition of the greatest common divisor for two integers $a$ and $b$, however, you might have to list out all divisors of both $a$ and $b$, then search for the greatest divisor that they share. ##### The Algorithm To compute the $\text{GCD}(a,b)$ efficiently, we use an alternative inductive definition for $\text{GCD}(a,b)$, which states that $\text{GCD}(a,b) = \text{GCD}(b,a \mod b)$, and as the base case, $\text{GCD}(0,a) = a$. The operation $a \mod b$ is the modulo operation, which simply returns the remainder $r$ after applying an [[Integer Division Algorithms|integer division algorithm]] on $a$ and $b$. Based on this definition, we may imagine the following algorithm: ```scheme (define (gcd a b) (if (= b 0) a (gcd b (remainder a b)))) ``` ^268c5e ##### Theoretical Foundation In my post on [[Bézout's Lemma]], I defined the greatest common divisor $d$ of integers $a$ and $b$ so that $\text{GCD}(a,b) = d$ if and only if 1. $d \mid a$ and $d \mid b$ 2. If $c \mid a$ and $c \mid b$, then $c \mid d$. To establish that the above algorithm will actually work, we prove the equivalence of the inductive definition and the definition previously established using the following theorem: Let $a,b,q,r$ be integers, with $b \neq 0$. Assume that $a = bq + r$ for $0 \leq r < b$, then $\text{GCD}(a,b) = \text{GCD}(b,r)$. Proof: Let $\text{GCD}(a,b) = d$. We want to show that $d \mid b$ and $d \mid r$ and if $c \mid b$ and $c \mid r$ then $c \mid d$. Note that $d \mid b$ and $d \mid a$ are given. Thus, we have $dk = de + r$ for $k,e \in \mathbb{Z}$. This implies that $r = dk - de = d(k - e)$. Thus $d \mid r$.Now, suppose that we have $c \in \mathbb{Z}$ such that $c \mid b$ and $c \mid r$. By definition, $ck = b$ and $cl = r$ for $k,l \in \mathbb{Z}$. Thus, (since $d \mid a$) we have $de = c(kq) +cl = c(kq + l)$ for some $e$. Thus, $d \mid c$ Additionally, we must show that $\text{GCD}(0,a) = a$. Indeed, this is trivial, since $\forall a \in \mathbb{Z} \text{, }a \mid 0$, and $a(1) = a$. Additionally, suppose that $c \mid 0$ and $c \mid a$. We have our result. $\blacksquare$