2
$\begingroup$

So I'm completely stuck on how to prove Euclid's GCD Algorithm, given that we know the theorem $\texttt{gcd}(a, b) = \texttt{gcd}(b, a -b)$ as well as $\texttt{gcd}(a, b) = (b, a \bmod b)$

How would we go about proving the correctness of the algorithm, essentially that the GCD returned call it $d$, by $\texttt{gcd}(a, b)$ is correct for all pairs of $(a, b)$?

My instinct is to use induction, but I don't quite understand what we would be using induction on.. I find the two theorems straightforward, but I don't quite understand how to apply them in a manner to begin an induction proof (I'm thinking strong induction) to show that the algorithm correctly computes the GCD for all pairs $(a, b)$ such that $a \in \mathbb{N}$, $b \in \mathbb{N}$ and $a > b$ since if $b > a$ the algorithm will simply switch the two.

I've referred to the CLRS book where they provide proofs of the theorems (but I understand the theorems and don't have to prove these) but am still completely stuck on how to move forward. I imagined starting with some base case such as $$gcd(1,0)$$ or $$gcd(2, 0)$$ or $$gcd(2, 1)$$ but from there I'm not sure what we're using induction on, or what the inductive step really would be. I understand we basically have to show that the algorithm gets down to our base case, that is $a \bmod b $ is $0$, the last remainder stored by the function is returned and that is our gcd.

I also went through some examples with numbers, like $gcd(55, 34)$ and continuously applied the theorem that $gcd(a, b) = gcd(b, a - b)$ to see that the recursive call finally ends in $gcd(1, 1)$ and $1 \bmod 1$ = $0$, so $1$ is returned.

Could someone please shed some light on how to move forward? Have spent significant time trying to attempt this proof.

$\endgroup$
4
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Euclidean_algorithm#Proof_of_validity $\endgroup$ – Maximilian Janisch Jan 23 '20 at 23:59
  • $\begingroup$ Thanks, I'm a bit confused of how we manage to get down to that final non-zero remainder, $r_{n - 1}$ though. How would I go about proving that? I don't think I could come close to giving a two-step argument since it seems I'm lacking the understanding of how to prove it.. $\endgroup$ – fibonnaci_0_1_1 Jan 24 '20 at 0:06
  • 1
    $\begingroup$ My (informal) idea is that you recursively construct remainders $r_i$ which satisfy $r_{i}>r_{i+1}$. Since all the $r_i$ are positive integers, it follows that for some $N$ we have $r_N=0$ and there will be no more remainders. (Indeed it is not too hard to prove formally that there is no infinite sequence of integers $r_1>r_2>\dots>0$.) $\endgroup$ – Maximilian Janisch Jan 24 '20 at 0:31
  • $\begingroup$ Okay, I tried that with an example and definitely see how that works and eventually we get down to a finite number of remainders, like you said, $N$ number of remainders.. I don't understand how to prove this for a general case of all pairs $(a, b)$ though.. Any thoughts? $\endgroup$ – fibonnaci_0_1_1 Jan 24 '20 at 2:31
2
$\begingroup$

The key here, quoting from the section Infinite descent in the wikipedia article on mathematical induction, is

$\quad$ ... there are no infinite decreasing sequences of natural numbers

Here we provide constructions/hints and leave the organization/exposition of the theory to the interested reader.

Recall that we have the first projection mapping $\pi_1$ on $\Bbb Z^{+} \times \Bbb Z^{+}$ defined by:

$\quad \forall \, (m,m) \in \Bbb Z^{+} \times \Bbb Z^{+} : \pi_1(m,n)=m$

Define $P = \{ (m,n) \in \Bbb Z^{+} \times \Bbb Z^{+} \mid m \ge n \} $. Recall that the set $P$ contains the diagonal set

$\quad \quad \quad \Delta_{\mathbb Z^{+}} = \{(d,d) \mid d \in \mathbb Z^{+}\}$.

We define the function $F: P \to P$ as follows

$$ F(m,n) = \left\{\begin{array}{lr} (m,n) & \text{if } m = n\\ (m-n,n) & \text{if } m-n \ge n\\ (n,m-n) & \text{if } m-n \lt n\\ \end{array}\right\} $$

If $(m,n) \in P$ we can apply the $\text{gcd}$ function. Note that for elements $(d,d)$ in the diagonal $\Delta_{\mathbb Z^{+}}$,

$\tag 1 \text{gcd}(d,d) = d$

Now it is well known that

$\tag 2 \text{gcd}(m,n) = \text{gcd}\big(F(m,n)\big)$

For fixed $(s,t)$ in the domain of $F$ we define a sequence

$\tag 3 a_k = \pi_1 \circ F^k(s,t)$

By using the absurdity of an infinite descent, the sequence $(a_k)$ eventually 'stops decreasing and remains constant. That happens precisely when the algorithm $F$ 'hits the diagonal.

So the algorithm $F$ 'gets us' to the diagonal in a finite number of steps, and from there we can just 'read off' greatest common divisor.


Example: Let $m = 28$ and $n = 10$ so that $(m,n)$ belongs to the domain of $F$.

$\quad F(28,10) = (18, 10)$
$\quad F(18,10) = (10, 8)$
$\quad F(10,8) = (8, 2)$
$\quad F(8,2) = (6, 2)$
$\quad F(6,2) = (4, 2)$
$\quad F(4,2) = (2, 2)$ STOP

Of course if you don't want to stop you can continue to apply $F$. But the points on the diagonal are exactly the fixed points of $F$, so you will quickly lose interest.

The point $(2,2) \in \Delta_{\mathbb Z^{+}}$ and so $\text{gcd}(28,10) = 2$.

$\endgroup$
3
  • $\begingroup$ Thank you for the help, but unfortunately, I literally cannot follow anything after the first line where you define the cartesian product of $Z^+ \times Z^+$. It seems I lack the requisite knowledge of "projection mapping" and diagonal sets. $\endgroup$ – fibonnaci_0_1_1 Jan 24 '20 at 4:32
  • $\begingroup$ I suggest you keep applying the function $F$ to the ordered pair $(55, 34)$ - should look familiar! $\endgroup$ – CopyPasteIt Jan 24 '20 at 12:55
  • $\begingroup$ Thanks, I did that and see what it evaluates to (it stops at $gcd(1,1)$) but I still have difficulties in how to translate this into an induction proof. $\endgroup$ – fibonnaci_0_1_1 Jan 24 '20 at 20:11
1
$\begingroup$

Hint Use (strong) induction on $a+b$. Note that $(a-qb)+b<a+b$ as long as $q \neq 0$, which is always the case when you divide the largest number by the smallest, i.e. $a \geq b$.

$\endgroup$
14
  • $\begingroup$ Thank you! I agree that $(a - qb) + b < a + b$ whenever $q \neq 0$ and we always have $q > 0$ since it must be at least $1$, so $q \geq 1$. Could you possibly give me a hint as to the base cases? I feel like we're basically showing that the last remainder the $n^{th}$ one is $0$, and the last nonzero remainder is the gcd... $\endgroup$ – fibonnaci_0_1_1 Jan 24 '20 at 4:48
  • $\begingroup$ Base case is $(a,b)=(1,0)$. Induction hypothesis: $a\geq b, a+b\leq k, k\geq 1$. Then do the case $a\geq b,a+b=k+1$ by considering two subcases: $b=0$ or $b>0$, where the first subcase is true because $\gcd(a,0)=a$, and the second subcase is reduced to the induction hypothesis, as in the hint. $\endgroup$ – Pythagoras Jan 24 '20 at 13:27
  • $\begingroup$ @fibonnaci_0_1_1 The base case is $a+b=1$ which means $a=1,b=0$, there is nothing to prove here. And as Pythagoras already pointed in the comment, in the inductive step you can assume that $a \geq b$ and discuss the two cases $b=0, b>0$ separately. $\endgroup$ – N. S. Jan 24 '20 at 14:56
  • $\begingroup$ @Pythagoras Thanks! So base case of $(a, b) = (1, 0)$ essentially shows that $gcd(1, 0)$ returns a; i.e., returns 1. Then for IH, we are assuming $a \geq b$, $a + b \leq k$, $k \geq 1$ and for the first case, when b = 0, we already know that we will return $a$.. If $b > 0$ we will end up with $gcd(a, b) = gcd(b, a - b)$? I don't understand how the second subcase is reduced to the IH... I feel like that's the missing link here maybe? I believe that I'm close but not quite sure. $\endgroup$ – fibonnaci_0_1_1 Jan 24 '20 at 17:19
  • $\begingroup$ @N.S. how is the second subcase $b > 0$ properly addressed? Is it just showing how the problem keeps reducing, and hit's the base case eventually? I don't know what I'm screwing up here.. $\endgroup$ – fibonnaci_0_1_1 Jan 24 '20 at 17:24
0
$\begingroup$

Here we give a complete proofs accepting the following as true,

Proposition 1: For any two distinct integers $a,b \in \Bbb Z^{+}$ with $a \gt b$,

$\tag 1 \text{gcd}(a,b) = \text{gcd}(a-b,b)$

Define $P = \{ (m,n) \in \Bbb Z^{+} \times \Bbb Z^{+} \mid m \ge n \} $. Recall that the set $P$ contains the diagonal set

$\quad \quad \quad \Delta_{\mathbb Z^{+}} = \{(d,d) \mid d \in \mathbb Z^{+}\}$.

To avoid any confusion define the function $G: P \to \mathbb Z^{+}$ as follows

$\tag 2 (a,b) \mapsto \text{gcd}(a,b)$

Note that no calculations are necessary to compute $G(z)$ when $z \in \Delta_{\mathbb Z^{+}}$.

We also define the function $F: P \to P$ as follows

$$\tag 3 F(a,b) = \left\{\begin{array}{lr} (a,b) & \text{if } a = b\\ (a-b,b) & \text{if } a-b \ge b\\ (b,a-b) & \text{if } a-b \lt b\\ \end{array}\right\} $$

Note that a point $z \in P$ is a fixed point of the function $F$ if and only if $z \in \Delta_{\mathbb Z^{+}}$.

Proposition 2: For every $z \in P$ and integer $k \ge 1$ the following holds

$\tag 4 G(z) = G(F^k(z))$ Proof
We prove the proposition using simple induction.
Base Case $k=1$:
If $z \in \Delta_{\mathbb Z^{+}}$ then obviously $G(z) = G(F(z))$.
Otherwise, we simply translate proposition 1 to this setting.
Step Case: Assume $\text{(4)}$ is true.
If $F^k(z) \in \Delta_{\mathbb Z^{+}}$ then $G(F^{k+1}(z)) = G(F^{k}(z)) = G(z)$, so that has been addressed.
Otherwise, we simply translate proposition 1 to this setting while using the transitivity property of the equality relation. $\quad \blacksquare$

Proposition 3: For every $z \in P$ there exist a $k \ge 1$ such that $F^k(z) \in \Delta_{\mathbb Z^{+}}$.
Proof
We shall use Fermat's method of descent.
Assume the statement

$\tag 5 Q(n) : n := a + b \land (a,b) \in P \land [\forall k \ge 1, \, F^k(a,b) \notin \Delta_{\mathbb Z^{+}}]$

is true.
Letting $\pi_1$ and $\pi_2$ denote the first and second projection mappings defined on $\mathbb Z^{+} \times \mathbb Z^{+}$ (see definitions here), we define

$\quad a' = \pi_1(F(a,b)) \text{ and } b' = \pi_2(F(a,b))$

and can then write as true

$\tag 6 Q(m) : m := a' + b' \land (a',b') \in P \land [\forall k \ge 1, \, F^k(a',b') \notin \Delta_{\mathbb Z^{+}}]$

where $m \lt n$.

By reductio ad absurdum, $\text{(5)}$ must rejected. $\quad \blacksquare$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.