欧几里得98、小学生能学会的大学数学：辗转相除算法计算原理的两种证明

a÷b=k……r（a、b、k、r是整数），则（a，b）=（b，r）。

…两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。

…a÷b=k……r：被除数（a）÷除数（b）=商（k）……余数（r）…

证法一

a可以表示成a = kb + r（a，b，k，r都是正整数，且r＜b），则r = a mod b

… a÷b=k……c

∴a/b=k……c

∴  a=kb+c

…

…mod：见《欧几里得97》…

 

a = kb + r

∴ r = a - kb

假设d是a，b的一个公因数（即a和b都可以被d整除）。

r = a - kb两边同时除以d，得：r/d=a/d-kb/d

a和b都可以被d整除

∴ a/d是整数；kb/d是整数

整数-整数=整数

∴ “a/d-kb/d”是整数

r/d=a/d-kb/d

∴ r/d是整数。即r可以被d整除。

∴ d是b，r的公因数

 

假设d是b，r的公因数, 则b和r都可以被d整除。

a = kb + r 两边同时除以d，得：a/d=kb/d-r/d

b和r都可以被d整除

∴ b/d是整数；r/d是整数

k是整数

∴ kb/d是整数；“kb/d-r/d”是“整数-整数”——结果还是整数

“kb/d-r/d”是整数；a/d=kb/d-r/d

∴ a/d是整数。即d能整除a。

∴ d也是a，b的公因数。

由证明过程知，（a，b）和（b，a mod b）的公因数是一样的。

∴ 其最大公因数也必然相等。

原命题得证。

 

证法二

令c=（a，b），设a=mc，b=nc

…（a，b）：在数论中，记法（a，b）表示整数a与整数b的最大公约数（greatest common divisor，也译作最大公因数），即所有能同时整除 a 与 b 的正整数中最大的那一个…

…c=（a，b）：c是整数a与整数b的最大公因数…

r=a-kb；a=mc，b=nc   

∴ r=a-kb=mc-knc=（m-kn）c

∴ c也是r的因数

可以判定m-kn与n为互质数。

（…互质数：公因数只有1的两个非零自然数，叫做互质数…）

…假设m-kn与n不是互质数

设m-kn=xd，n=yd，（d是整数；d＞1）

m-kn=xd

∴ m=kn+xd

n=yd

∴ m=kn+xd=kyd+xd=（ky+x）d

m=（ky+x）d；a=mc，b=nc

∴ a=mc=（ky+x）dc，b=nc=ycd

即a=（ky+x）dc，b=ycd

观察“a=（ky+x）dc，b=ycd”知：a与b最大公因数要么是cd，要么比cd大。

这与前面“c是整数a与整数b的最大公因数”矛盾。

“m-kn与n不是互质数”违反了矛盾律。

…矛盾律：对两个矛盾的判断不能同时承认它们都是真的…它们中至少有一个是假的…见《欧几里得82》…

∴ “m-kn与n不是互质数”是假命题。

根据排中律，“m-kn与n不是互质数”是假命题，那么“m-kn与n不是互质数”的反命题——m-kn与n是互质数，就是真命题。

…排中律：对同一问题做的两个互相矛盾的判断中，必有一个是真的，非此即彼…见《欧几里得80》…

“m-kn与n是互质数”得证。

…

r=（m-kn）c，b=nc，m-kn与n是互质数

∴ （b，r）=c

c=（a，b）

∴ （a，b）=（b，r）=c

原命题得证。

 

“第一次数学危机的根结就在于，古希腊人理所当然地相信不断地截取线段，总有一个时候会截到两个线段一样长。后来，Hippasus（通常译为希帕索斯）画了这么一张图，告诉大家了一个反例：有可能这个操作会无穷尽地进行下去…

请看下集《欧几里得99、辗转相除的正方形图示》”

若不知晓历史，便看不清未来

欢迎关注博客"人性的游戏"或微博"人性的游戏"