
Computer Science Computer Science Forum 
 LinkBack  Thread Tools  Display Modes 
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 nonnegative 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); } 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 mp$ and $\displaystyle mq$ 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 mp$, then $\displaystyle p = m * i$ As $\displaystyle mq$, 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 my$ As $\displaystyle my$ and $\displaystyle mq$, then $\displaystyle m <= gcd(q, y)$ And as $\displaystyle gcd(q, y) = n$, then $\displaystyle m <= n$ As nq and ny 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) 

Tags 
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 