My Math Forum Euclid Algorithm Mathematical Induction

 Computer Science Computer Science Forum

September 6th, 2019, 03:58 AM   #1
Newbie

Joined: Sep 2019
From: Earth

Posts: 2
Thanks: 0

Math Focus: Computer Science
Euclid Algorithm Mathematical Induction

Hello,

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:

Code:
    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?

Proof.

$\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$
Then
$\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
 proof.txt (1.2 KB, 0 views)

 Tags algorithm, euclid, induction, mathematical

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post zaidahmed Algebra 1 April 29th, 2014 03:42 AM shaharhada Algebra 2 October 4th, 2013 10:45 AM GgiPunjab Number Theory 2 November 16th, 2012 02:43 AM tinynerdi Number Theory 0 August 29th, 2010 11:58 PM julien Applied Math 1 May 27th, 2007 09:44 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top