王子龍老師教會同學們如何使用歐幾裡德算法，即輾轉相除法，快速求出兩數的最大公因數。並且，留下證明題讓同學們思考。
這個算法在數學界和計算機界都太重要，以至於很容易可以度到正確證明方法，和計算機實現。但是好多家長度完以後表示不理解。我來嘗試用「普通話」描述一下。
假設兩個正整數A和B(A>B），則兩者關係可表達為A=kB+r（其中r是A除以B的餘數），記作r=A mod B
再假設q是A和B的最大公約數gcd（greatest common divisor），記作gcd(A，B)=q
那麼由A=kB+r => r=A-kB，即可知q也可以被r整除
所以gcd(B, r)=q，即gcd(B, A mod B)=q，得證。
#定義函數gdc，返回值為最大公約數
def gdc(A,B):
if B==0:
return A
else:
return gdc(B,A%B)
#調用函數列印返回值，傳入A=12480，B=1024
print "gdc(12480,1024)=",gdc(12480,1024)
運行結果：
gdc(12480,1024)= 64
註：直接copy&paste代碼到在線編譯器玩的話，請注意調整縮進
求出最大公因數有什麼用呢？
1.貝祖定理
由歐幾裡德算法進一步推出，兩數的最大公約數可用兩數的整數倍相加來表示，這就是貝祖定理 -- 任何整數A、B和它們的最大公約數q，關於未知數x和y的線性方程（裴蜀等式）Ax + By = r有解，若且唯若r是q的倍數。
換種說法，最大公約數q就是最小的可以寫成Ax+By形式的正整數。例如，12和42的最大公約數是6，那麼我們可知方程12x + 42y = 6有解。
裴蜀等式有解時必然有無窮多個整數解，每組解x、y都稱為裴蜀數。特別情況是，兩個整數a、b 是互質的，等價於方程 ax+by=1有整數解。
2.計算機密碼學
計算機密碼最常用的有
（1）移位
（2）邏輯運算
（3）歐幾裡德算法求兩個整數的最大公約數
（4）素數的判定和尋找
歐幾裡德算法是計算機編程實現加解密的基本運算之一。例如RSA算法是基於人們無法快速分解出公約數的假設。
寫在最後
當代使用量子計算Quantumn的疊加態，同時並行運算多種情況，可快速分解出公約數，加速RSA破解。想了解更多量子計算原理，請看歷史貼把看《擺渡人》的時間省下，來學學量子計算
Reference
Python在線編譯器 https://c.runoob.com/compile/6
【歷史課程回顧】
『編程學數學』Lesson 5 神奇的數字37（六年級第一單元）
『編程學數學』Lesson 4 整除快速記憶法（六年級第一單元）
『編程學數學』Lesson 3 多邊形的內外角
『編程學數學』Lesson 2 有用且無用的素數
『編程學數學』Learning Math by Coding Lesson 1