My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum

LinkBack Thread Tools Display Modes
September 6th, 2019, 03:58 AM   #1
Joined: Sep 2019
From: Earth

Posts: 2
Thanks: 0

Math Focus: Computer Science
Euclid Algorithm Mathematical Induction


This is my second post on this form, so please let me know if I should move it to a more suitable section or use better formatting.

I have this exercise in the book Algorithms by R. Sedgewick and K. Wayne:

Use mathematical induction to prove that Euclid’s algorithm computes the greatest common divisor of any pair of non-negative integers p and q.

The algorithm is as follows:

    int euclid(int p, int q) {
        if (q == 0) {
          return p;
        return euclid(q, p mod q);
Is my induction (it follows) correct?
How would you improve it both in style and logic?


$\displaystyle gcd(p, q) = euclid(p, q)$ holds for $\displaystyle q = 0$ and/or $\displaystyle p = 0$, as:

for $\displaystyle p = 0, q = 0$, $\displaystyle gcd(0, 0) = euclid(0, 0) = 0$
for $\displaystyle q = 0, p > 0$, $\displaystyle gcd(p, 0) = euclid(p, 0) = p$
for $\displaystyle p = 0, q > 0$, gcd(0, q) = euclid(0, q) = euclid(q, 0 mod q) = euclid(q, 0) = q

According to the algorithm, $\displaystyle gcd(p, q) = euclid(p, q)$ holds for $\displaystyle q > 0$ and $\displaystyle p > 0$, if gcd(p, q) = euclid(q, p mod q).
So, let's prove it.

Let's assume that m is GCD of p and q: $\displaystyle m = gcd(p, q)$
Then $\displaystyle m|p$ and $\displaystyle m|q$
Let's use integer y, such as y = p mod q
Let's assume that n is GCD of q and y: n = gcd(q, y) = euclid(q, p mod q)
Proving that m = n, we are going to prove that gcd(p, q) = euclid(q, p mod q)

Let's use integers i and j.
As $\displaystyle m|p$, then $\displaystyle p = m * i$
As $\displaystyle m|q$, then $\displaystyle q = m * j$

Let's use integer k, so that p > k.
$\displaystyle p = q * k + y$
$\displaystyle y = p - q * k$
$\displaystyle y = m * i - m * j * k$
$\displaystyle y = m (i - j * k)$
Which means, that $\displaystyle m|y$

As $\displaystyle m|y$ and $\displaystyle m|q$, then $\displaystyle m <= gcd(q, y)$
And as $\displaystyle gcd(q, y) = n$, then $\displaystyle m <= n$

As n|q and n|y
Then, using integers i and j
$\displaystyle q = n * i$
$\displaystyle y = n * j$

As $\displaystyle p = q * k + y$
$\displaystyle p = n * i * k + n * j$
$\displaystyle p = n(i * k + j)$
Which means n divides p as well.

Thus, $\displaystyle n <= gcd(p, q)$
So, $\displaystyle n <= m$

As $\displaystyle m <= n$ and $\displaystyle n <= m$, then $\displaystyle m = n$.
Thus, gcd(p, q) = gcd(q, y) = euclid(q, p mod q)
Attached Files
File Type: txt proof.txt (1.2 KB, 0 views)
yuga is offline  

  My Math Forum > Science Forums > Computer Science

algorithm, euclid, induction, mathematical

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
Euclid's division of algorithm zaidahmed Algebra 1 April 29th, 2014 03:42 AM
Euclid's algorithm shaharhada Algebra 2 October 4th, 2013 10:45 AM
Euclid’s Algorithm?? GgiPunjab Number Theory 2 November 16th, 2012 02:43 AM
? >= log b/ log ? ( euclid's algorithm) tinynerdi Number Theory 0 August 29th, 2010 11:58 PM
Euclid's algorithm julien Applied Math 1 May 27th, 2007 09:44 AM

Copyright © 2019 My Math Forum. All rights reserved.