Old abababab

Math Problem Solver: GCD (求最大公约数)

2013/5/07

To find the Greatest Common Divider (gcd) of positive integers a and b,using the Euclidean and the Chinese algorithms.

Algorithm for finding gcd(m,n), based on the Euclidean division method

Assuming positive integers (m,n), m>n,

The trick: Observe the triple (a,b,c) where a=m, b=n, and c=r from m%n

Property: a>b>c. Obvious.

Property: gcd(a,b) = gcd(b,c) 　　

Let d = gcd(a,b) then

　　a=dx b=dy, a=bq+c

--> dx=dyq+c --> c=d(x-yq)

--> d|c

--> d is a common divisor shared by b and c.

Suppose d’ is another common divisor of b and c, then it’s easy to see that d’|a.

If d’ > d, then d is not gcd(a,b). So d’ < d.

--> d = gcd(b,c) 　　

==> a = bq + c

--> dx = dyq + dz 　　

==> Euclidean algorithm (300 BC): Solving gcd(a,b) is equivalent to solving gcd(b,c). This can be carried out recursively, as at each recursion, b<a, c<b , and eventually c=0 by well ordering principle of non-negative integers. And gcd(b,c) = b when c=0; 　　

This suggests an algorithm to get gcd(m,n). 　　

1- Let a=m, b=n, get c=m%n 　　

2- Termination condition: Return b as gcd if c==0; 　　

3- Recurs otherwise: Update a=b, b=c. 　　

==> Chinese algorithm: Solving gcd(a,b) is equivalent to solving gcd(b, a-b). 　　

dx = dyq + dz

--> a-b = d(x-yq) = dz.

Note that a-b < a but may be > b , <b or ==b. a=b=gcd(a,b) when a==b.

This suggests a recursive algorithm for gcd(m,n) m>n

1-Let a=m, b=n, Termination condition: Return a as gcd if a==b 　　

2-Recurs otherwise: Update ordered pair (a,b) a>b, with b and a-b.

Chinese algorithm (更相减损术) (100 AD. 东汉末期)

约分(按：约分者，物之数量，不可悉全，必以分言之；分之为数，繁则难用。设有四分之二者，繁而言之，亦可为八分之四；约而言之，则二分之一也，虽则异辞， 至于为数，亦同归尔。法实相推，动有参差，故为术者先治诸分。)术曰：可半者半之；不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。-- 《九章算术-卷一》刘徽李淳风评注

Note: The Chinese algorithm was derived from the practice of reducing (simplying) fractions.

评：现存中国古代数学文献大多只说解法，不说原理，但是众多的解法都不像只是经验得来，必有原理思路。而原理思路才是解题的金钥匙。古代数学有多大程度是秘传的呢？（原理都是秘方？易失传？）。

GCD(a,b): Linear combination in terms of a and b.

Proof idea:

Among all the positive integers in the form ax+by there must be a smallest d0. (Set S: dϵS: d=ax+by).

Test d0 to see if it divides a and b.

m=dq+r=(ax+by)q+r,

r=m-axq-byq=m(1-xq)-byq, rϵS, 0<=r r=0.

To find integers x and y, notice that x[k] = x[k-2] + x[k-1]*q[k], where k=0,1,.. as recursive index; x[0]=1,x[1]=0; q[k] quotient in the kth recursion. y = (gcd - a*x)/b. This recursive formula works but needs proof.

Give it a shot ...