今天又一次被一道數(shù)學(xué)問題震撼到了。很多感想，特別關(guān)于中英基礎(chǔ)教育的差別，甚至是大學(xué)教育怎樣做啟發(fā)式，創(chuàng)新型教育，而不是填鴨式。我們討論了很久，停留在嘴上，實際教育又是如何呢？

0. 引言

朋友發(fā)來孩子的家庭作業(yè)，是一道數(shù)學(xué)題，題目是這樣的。

我簡單的翻譯一下。 如下圖所示是一個簡單的數(shù)學(xué)計算流程。給出初始值A(chǔ)=1084， B=328。 現(xiàn)在請你按照流程圖并使用A和B的初始值得出結(jié)果。并記錄你所得的中間值。說明最終結(jié)果和A,B初始值的關(guān)系。并說明這種關(guān)系是否具有一般性。

題目很簡單。給了一個流程圖和兩個起始數(shù)字，要求孩子根據(jù)流程圖和所給數(shù)字給出結(jié)果，就是跑流程。關(guān)鍵在后面，題目要求孩子給出最終結(jié)果和初始數(shù)據(jù)的關(guān)系。并證明這種關(guān)系是否具有一般性？要知道這是一個英國九年級學(xué)生（相當(dāng)于中國的初二）的問題！

作為一名大學(xué)老師，自以為很簡單，于是著手解決問題。

當(dāng)然，現(xiàn)在知道了結(jié)果，回頭看并沒有那么困難。試想，僅僅具有一般數(shù)學(xué)、計算機(jī)、或者數(shù)論基礎(chǔ)的人。估計，第一眼也會發(fā)懵。 這就是我當(dāng)初的感受。

不信的朋友可以試試。直接跳過的后一章。

除過給出的兩個數(shù)據(jù)， 我還隨意找了另外一些數(shù)據(jù)。打開Excel，列出表格，很快試驗了兩組數(shù)據(jù)。

結(jié)果有了。結(jié)果和初始數(shù)據(jù)的關(guān)系是什么呢？

1. 尋找關(guān)系

很顯然，兩個數(shù)據(jù)不等時，都做了替換動作。而這個替換很典型，就是把兩個數(shù)據(jù)中大的一個替換成它們的差。而且是重復(fù)的動作直至，大小關(guān)系改變。作為一名專業(yè)計算機(jī)軟件工程師，第一直覺就是，減法實現(xiàn)的除法。這是計算機(jī)工程中的常見動作。其實，計算機(jī)只會加法，減法是通過加補數(shù)來完成；乘法通過移位加來完成；除法通過連續(xù)減來實現(xiàn)。所以，過去我們常把計算機(jī)的CPU稱為加法器。

減法實現(xiàn)除法時一個重要的概念就是余數(shù)。余數(shù)在計算機(jī)里十分重要。很多時候比商還重要。計算機(jī)常常把商扔掉。僅僅考慮余數(shù)。這就是重要的模數(shù)運算。Mod. 提到模數(shù)， 不得不說鐘表的指針位置。13點和1點時針位置相同。也就是說13和1 的模數(shù)相等，都是1。這是因為他們都是模12 的余數(shù)。

之所以提到模數(shù)運算是因為連續(xù)減，直到結(jié)果小于減數(shù)時，就是計算了模數(shù)。連續(xù)減的次數(shù)就是商。結(jié)果就是余數(shù)。如第一個例子。1804，連續(xù)減了5次328后得到164。就是1804 除以328 商5余164。問題在于，用余數(shù)和減數(shù)比是什么意思？

如果，這里減法代表除法， 那么，減數(shù)除以余數(shù)，.....,?

直至， 能夠整除。減法的結(jié)果等于零，說明相等，也就是整除。商1。?

這里涉及到模數(shù)、整除、余數(shù)。 回過頭看了，自然是找最大公約數(shù)了。可是， 有誰能夠從這算式中直接得出？

2。 最大公約數(shù)（GCF， GCD）

最大公約數(shù)也叫最大公因子，指兩個或多個整數(shù)共有約數(shù)中最大的一個。a，b的最大公約數(shù)記為（a，b），同樣的，a，b，c的最大公約數(shù)記為（a，b，c），多個整數(shù)的最大公約數(shù)也有同樣的記號。求最大公約數(shù)有多種方法，常見的有質(zhì)因數(shù)分解法、短除法、輾轉(zhuǎn)相除法、更相減損法。與最大公約數(shù)相對應(yīng)的概念是最小公倍數(shù)，a，b的最小公倍數(shù)記為[a，b]。

其實， 這個作業(yè)里列出的算法就是輾轉(zhuǎn)相除法， 也叫歐幾里得算法，計算公式gcd(a,b) = gcd(b,a mod b)。它是由古希臘數(shù)學(xué)家歐幾里得在其著作《The Elements》中最早描述了這種算法。

證法一

a可以表示成a = kb + r（a，b，k，r皆為正整數(shù)，且r<b），則r = a mod b

假設(shè)d是a,b的一個公約數(shù)，記作d|a,d|b，即a和b都可以被d整除。

而r = a - kb，兩邊同時除以d，r/d=a/d-kb/d=m，由等式右邊可知m為整數(shù)，因此d|r

因此d也是b,a mod b的公約數(shù)

假設(shè)d是b,a mod b的公約數(shù), 則d|b,d|(a-k*b),k是一個整數(shù)。

進(jìn)而d|a.因此d也是a,b的公約數(shù)

因此(a,b)和(b,a mod b)的公約數(shù)是一樣的，其最大公約數(shù)也必然相等，得證。

證法二

假設(shè)c = gcd(a,b),則存在m,n，使a = mc, b = nc;

令r = a mod b，即存在k，使r = a-kb = mc - knc = (m-kn)c;

故gcd(b,a mod b) = gcd(b,r) = gcd(nc,(m-kn)c) = gcd(n,m-kn)c;

則c為b與a mod b的公約數(shù);

假設(shè)d = gcd(n,m-kn), 則存在x,y, 使n = xd, m-kn = yd; 故m = yd+kn = yd+kxd = (y+kx)d;

故有a = mc = (y+kx)dc, b = nc = xdc; 可得 gcd(a,b) = gcd((y+kx)dc,xdc) = dc;

由于gcd(a,b) = c, 故d = 1;

即gcd(n,m-kn) = 1, 故可得gcd(b,a mod b) = c;

故得證gcd(a,b) = gcd(b,a mod b).

這里是我想起我們的祖先也有類似的算法。 叫更相減損術(shù)是出自《九章算術(shù)》的一種求最大公約數(shù)的算法，原文是：

可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也。以等數(shù)約之。

白話文譯文：

（如果需要對分?jǐn)?shù)進(jìn)行約分，那么）可以折半的話，就折半（也就是用2來約分）。如果不可以折半的話，那么就比較分母和分子的大小，用大數(shù)減去小數(shù)，互相減來減去，一直到減數(shù)與差相等為止，用這個相等的數(shù)字來約分。

第一步：任意給定兩個正整數(shù)；判斷它們是否都是偶數(shù)。若是，則用2約簡；若不是則執(zhí)行第二步。

第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的減數(shù)和差相等為止。

則第一步中約掉的若干個2的積與第二步中等數(shù)的乘積就是所求的最大公約數(shù)。

其中所說的“等數(shù)”，就是公約數(shù)。求“等數(shù)”的辦法是“更相減損”法。

3. 歐幾里得最大公約數(shù)算法與目前我們使用的網(wǎng)絡(luò)加密的RSA算法

質(zhì)數(shù)及互質(zhì)

質(zhì)數(shù)(Prime number)又稱素數(shù),指在大于1的自然數(shù)中，除了1和該數(shù)自身外，無法被其他自然數(shù)整除的數(shù)。大于1的自然數(shù)若不是素數(shù)，則稱之為合數(shù)。

如果兩個或兩個以上的整數(shù)的最大公約數(shù)是 1，則稱它們?yōu)榛ベ|(zhì)(也叫互素)。兩個整數(shù) a 與 b 互質(zhì)，記為 a ⊥ b。

互質(zhì)的兩個數(shù)，有如下性質(zhì)

整數(shù)a和b互質(zhì)當(dāng)且僅當(dāng)存在整數(shù)x,y使得xa+yb=1。

也就是說，如果a、b互質(zhì)，那么xa+yb=1必然有解。如果xa+yb=1有解，則a、b必然互質(zhì)；如果xa+yb=1無解，則a、b必然不是互質(zhì)。

這個性質(zhì)涉及擴(kuò)展歐幾里德算法，我們后面會提到。

互質(zhì)的判別方法主要有：

兩個不同的質(zhì)數(shù)一定互質(zhì)。例如，2與7、13與19。

較大的數(shù)是質(zhì)數(shù)，則兩數(shù)互質(zhì)。如33與51

一個素數(shù)，另一個不為它的倍數(shù)，這兩個數(shù)互質(zhì)。例如，3與10、5與 26。

相鄰兩個自然數(shù)互質(zhì)。即，如果p是大于1整數(shù)，則p與p-1、p+1互質(zhì)。如15與16、14互質(zhì)

相鄰兩個奇數(shù)互質(zhì)。如19與21、17互質(zhì)。

RSA公開密鑰密碼體制

是一種使用不同的加密密鑰與解密密鑰，“由已知加密密鑰推導(dǎo)出解密密鑰在計算上是不可行的”密碼體制?[2]?。

在公開密鑰密碼體制中，加密密鑰（即公開密鑰）PK是公開信息，而解密密鑰（即秘密密鑰）SK是需要保密的。加密算法E和解密算法D也都是公開的。雖然解密密鑰SK是由公開密鑰PK決定的，但卻不能根據(jù)PK計算出SK?[2]?。

正是基于這種理論，1978年出現(xiàn)了著名的RSA算法，它通常是先生成一對RSA密鑰，其中之一是保密密鑰，由用戶保存；另一個為公開密鑰，可對外公開，甚至可在網(wǎng)絡(luò)服務(wù)器中注冊。為提高保密強度，RSA密鑰至少為500位長，一般推薦使用1024位。這就使加密的計算量很大。為減少計算量，在傳送信息時，常采用傳統(tǒng)加密方法與公開密鑰加密方法相結(jié)合的方式，即信息采用改進(jìn)的DES或IDEA對話密鑰加密，然后使用RSA密鑰加密對話密鑰和信息摘要。對方收到信息后，用不同的密鑰解密并可核對信息摘要

思考：

一個簡單的作業(yè)讓學(xué)生有深入的思考。