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

 

辗转相除法，其计算原理依赖于下面的定理：

…辗、转、辗转、辗转相除法：见《欧几里得119》…

…原、理、原理：见《欧几里得41》…

…定、理、定理：见《欧几里得2》…

 

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

…其它表述为：被除数、除数、余数是整数，被除数除以除数，得到余数，则（被除数，除数）=（除数，余数）；a、b、c是整数，a除以b余c，则（a，b）=（b，c）；a、b、c是整数，a÷b=商……c，则（a，b）=（b，c）…

[…（a，b）：整数a与整数b的最大公约数…]

 

“a、b、c是整数，a÷b=商……c，则（a，b）=（b，c）”有多种证法：

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

 

证法一

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

… a÷b=k……c

∴a/b=k……c

∴  a=kb+c…

…mod：“Module Operation（取模运算）”的缩写…也就是“Module Operation”的前三个字母…见《欧几里得120》…

 

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，r）的公因数是一样的。

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

原命题得证。

…命、题、命题：见《欧几里得70》…

 

证法二

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

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

 

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

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

∴ c也是r的因数

∴ （b，c）=（b，r）=[nc，（m-kn）c]=（n，m-kn）c

 

 

设d=（n，m-kn），则存在x、y，使n/d=x，（m-kn）/d=y

…d=（n，m-kn）：d是n，m-kn的最大公约数…

 

n/d=x，（m-kn）/d=y转化一下得：n=xd，m-kn=yd

∴ m=yd+kn=yd+kxd=（y+kx）d

∴ a =mc=（y+kx）dc，b=nc=xdc

 

c=（a，b）

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

 

∴ （a，b）=[（y+kx）dc，xdc]=dc=c，d = 1

 

∴ 1=（n，m-kn）

∴ （b，c）=（b，r）=[nc，（m-kn）c]=（n，m-kn）c=c

 

c=（a，b）

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

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

 

注意：两种方法是有区别的。

 

“从前有座山，山里有座庙，庙里有个和尚，和尚在讲故事，从前有座山，山里有座庙，庙里有个和尚，和尚在讲故事，从前有座山…

请看下集《欧几里得124、证明“存在不能表示为两个整数之比的数”，递、归、递归》”

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

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