歐幾里得123、小學生能學會的大學數(shù)學：輾轉(zhuǎn)相除算法計算原理的兩種證明

?

輾轉(zhuǎn)相除法，其計算原理依賴于下面的定理：

…輾、轉(zhuǎn)、輾轉(zhuǎn)、輾轉(zhuǎn)相除法：見《歐幾里得119》…

…原、理、原理：見《歐幾里得41》…

…定、理、定理：見《歐幾里得2》…

?

定理：兩個整數(shù)的最大公約數(shù)等于其中較小的那個數(shù)和兩數(shù)相除余數(shù)的最大公約數(shù)。

…其它表述為：被除數(shù)、除數(shù)、余數(shù)是整數(shù)，被除數(shù)除以除數(shù)，得到余數(shù)，則（被除數(shù)，除數(shù)）=（除數(shù)，余數(shù)）；a、b、c是整數(shù)，a除以b余c，則（a，b）=（b，c）；a、b、c是整數(shù)，a÷b=商……c，則（a，b）=（b，c）…

[…（a，b）：整數(shù)a與整數(shù)b的最大公約數(shù)…]

?

“a、b、c是整數(shù)，a÷b=商……c，則（a，b）=（b，c）”有多種證法：

…a÷b=k……r：被除數(shù)（a）÷除數(shù)（b）=商（k）……余數(shù)（r）…

?

證法一

a可以表示成a = kb + r（a，b，k，r皆為正整數(shù)，且r<b），則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

?

假設(shè)d是a，b的一個公因數(shù)（即a和b都可以被d整除）。

r=a-kb兩邊同時除以d，得：r/d=a/d-kb/d

∵ a和b都可以被d整除

∴ a/d是整數(shù)；kb/d是整數(shù)

∵ 整數(shù)-整數(shù)=整數(shù)

∴ “a/d-kb/d”是整數(shù)

?

∵ r/d=a/d-kb/d

∴ r/d是整數(shù)。即r可以被d整除。

∴ d是b，r的公因數(shù)

?

假設(shè)d是b，r的公因數(shù)，則b和r都可以被d整除。

a=kb+r兩邊同時除以d，得：a/d=kb/d-r/d

∵ b和r都可以被d整除

∴ b/d是整數(shù)；r/d是整數(shù)

?

∵ k是整數(shù)

∴ kb/d是整數(shù)；“kb/d-r/d”是“整數(shù)-整數(shù)”——結(jié)果還是整數(shù)

∵ “kb/d-r/d”是整數(shù)；a/d=kb/d-r/d

∴ a/d是整數(shù)。即d能整除a。

∴ d也是a，b的公因數(shù)。

?

由證明過程知，（a，b）和（b，r）的公因數(shù)是一樣的。

∴ 其最大公因數(shù)也必然相等。

原命題得證。

…命、題、命題：見《歐幾里得70》…

?

證法二

令c=（a，b），設(shè)a=mc，b=nc

…c=（a，b）：c是整數(shù)a與整數(shù)b的最大公因數(shù)…

?

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

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

∴ c也是r的因數(shù)

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

?

?

設(shè)d=（n，m-kn），則存在x、y，使n/d=x，（m-kn）/d=y

…d=（n，m-kn）：d是n，m-kn的最大公約數(shù)…

?

n/d=x，（m-kn）/d=y轉(zhuǎn)化一下得：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是整數(shù)a與整數(shù)b的最大公因數(shù)…

?

∴?（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）

?

注意：兩種方法是有區(qū)別的。

?

“從前有座山，山里有座廟，廟里有個和尚，和尚在講故事，從前有座山，山里有座廟，廟里有個和尚，和尚在講故事，從前有座山…

請看下集《歐幾里得124、證明“存在不能表示為兩個整數(shù)之比的數(shù)”，遞、歸、遞歸》”

若不知曉歷史，便看不清未來

歡迎關(guān)注嗶哩號“中國崛起呀”