User Name Remember Me? Password

 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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded 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      