web analytics

睡前一小时数学系列之gcd的求法

gcd:共产党。共产党泛指以马克思主义为指导以建立共产主义社会为目标的工人党。在中国,他是中国共产党的简称。
哦。。不。其实不是这样的。
gcd:最大公因数。一般gcd(a,b)表示a,b两数的最大公因数,
而一般求gcd的方法,就是人们常知的 欧几里德算法---辗转相除法。
辗转相除的思想其实就是  gcd(a,b)=gcd(b,a%b)
而求gcd 其实就是一直做刚才的式子,直到a%b为0的时候 b就是gcd (a,b).
最迷的就是为什么它是这样的呢?。接下来给出一种很普通证明。。。

gcd( a,b ) == gcd(b,a%b);

证明:

令 gcd(a,b)=d

设 t1,t2

使 a=t1*d , b=t2*d

设 k=a/b r=a%b

则 

so : a= kb +r

because : r= kb-a

so : r = k*t2*d – t1*d

because : d|(t2*d) && d|(t1*d)

so : d| (k*t2*d - t1*d)

so : d | r

假设: (k*t2 – t1) 与 t2 不互质

设 k*t2 -t1 = x*q

t2 = y*q

because: t1 = k*t2 – t1

t1 = k*y*q - x*q

t1 = ( k*y – x) *q

so : a = (k*y-x)*q*d

b = y*q*d

so : gcd(a,b)= q*d

但是 gcd(a,b) = d 矛盾

so : (k*t2 – t1) 与 t2  互质。

So : gcd ( b , r ) = d

so : gcd(a,b)== gcd( b , a%b)

这种证明。我觉得这是最清楚的方法。
恩。就是这样。
每次都觉的数学很有趣。。
可能接下来会写一篇扩展欧几里德算法。 。。慢慢学吧~

接下来放出程序:

 

Post a Comment

You must be logged in to post a comment.