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

0. 引言

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

我簡(jiǎn)單的翻譯一下。 如下圖所示是一個(gè)簡(jiǎn)單的數(shù)學(xué)計(jì)算流程耘擂。給出初始值A(chǔ)=1084胆剧， B=328。 現(xiàn)在請(qǐng)你按照流程圖并使用A和B的初始值得出結(jié)果梳星。并記錄你所得的中間值赞赖。說(shuō)明最終結(jié)果和A,B初始值的關(guān)系。并說(shuō)明這種關(guān)系是否具有一般性冤灾。

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

作為一名大學(xué)老師糠悼，自以為很簡(jiǎn)單届榄，于是著手解決問(wèn)題。

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

不信的朋友可以試試莹妒。直接跳過(guò)的后一章名船。

除過(guò)給出的兩個(gè)數(shù)據(jù)， 我還隨意找了另外一些數(shù)據(jù)动羽。打開(kāi)Excel包帚，列出表格，很快試驗(yàn)了兩組數(shù)據(jù)运吓。

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

1. 尋找關(guān)系

很顯然拘哨，兩個(gè)數(shù)據(jù)不等時(shí)谋梭，都做了替換動(dòng)作。而這個(gè)替換很典型倦青，就是把兩個(gè)數(shù)據(jù)中大的一個(gè)替換成它們的差瓮床。而且是重復(fù)的動(dòng)作直至，大小關(guān)系改變产镐。作為一名專業(yè)計(jì)算機(jī)軟件工程師隘庄，第一直覺(jué)就是，減法實(shí)現(xiàn)的除法癣亚。這是計(jì)算機(jī)工程中的常見(jiàn)動(dòng)作丑掺。其實(shí)，計(jì)算機(jī)只會(huì)加法述雾，減法是通過(guò)加補(bǔ)數(shù)來(lái)完成街州；乘法通過(guò)移位加來(lái)完成；除法通過(guò)連續(xù)減來(lái)實(shí)現(xiàn)玻孟。所以唆缴，過(guò)去我們常把計(jì)算機(jī)的CPU稱為加法器。

減法實(shí)現(xiàn)除法時(shí)一個(gè)重要的概念就是余數(shù)黍翎。余數(shù)在計(jì)算機(jī)里十分重要面徽。很多時(shí)候比商還重要。計(jì)算機(jī)常常把商扔掉匣掸。僅僅考慮余數(shù)斗忌。這就是重要的模數(shù)運(yùn)算质礼。Mod. 提到模數(shù)， 不得不說(shuō)鐘表的指針位置织阳。13點(diǎn)和1點(diǎn)時(shí)針位置相同。也就是說(shuō)13和1 的模數(shù)相等砰粹，都是1唧躲。這是因?yàn)樗麄兌际悄?2 的余數(shù)。

之所以提到模數(shù)運(yùn)算是因?yàn)檫B續(xù)減碱璃，直到結(jié)果小于減數(shù)時(shí)弄痹，就是計(jì)算了模數(shù)。連續(xù)減的次數(shù)就是商嵌器。結(jié)果就是余數(shù)肛真。如第一個(gè)例子。1804爽航，連續(xù)減了5次328后得到164蚓让。就是1804 除以328 商5余164。問(wèn)題在于讥珍，用余數(shù)和減數(shù)比是什么意思历极？

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

直至氏义， 能夠整除锄列。減法的結(jié)果等于零，說(shuō)明相等惯悠，也就是整除邻邮。商1。?

這里涉及到模數(shù)吮螺、整除饶囚、余數(shù)。 回過(guò)頭看了鸠补，自然是找最大公約數(shù)了萝风。可是紫岩， 有誰(shuí)能夠從這算式中直接得出规惰？

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

最大公約數(shù)也叫最大公因子歇万，指兩個(gè)或多個(gè)整數(shù)共有約數(shù)中最大的一個(gè)揩晴。a，b的最大公約數(shù)記為（a贪磺，b）硫兰，同樣的，a寒锚，b劫映，c的最大公約數(shù)記為（a，b刹前，c）泳赋，多個(gè)整數(shù)的最大公約數(shù)也有同樣的記號(hào)。求最大公約數(shù)有多種方法喇喉，常見(jiàn)的有質(zhì)因數(shù)分解法祖今、短除法、輾轉(zhuǎn)相除法拣技、更相減損法千诬。與最大公約數(shù)相對(duì)應(yīng)的概念是最小公倍數(shù)，a过咬，b的最小公倍數(shù)記為[a大渤，b]。

其實(shí)掸绞， 這個(gè)作業(yè)里列出的算法就是輾轉(zhuǎn)相除法泵三， 也叫歐幾里得算法，計(jì)算公式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的一個(gè)公約數(shù)捷犹，記作d|a,d|b，即a和b都可以被d整除冕末。

而r = a - kb萍歉，兩邊同時(shí)除以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是一個(gè)整數(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ù)約之逛尚。

白話文譯文：

（如果需要對(duì)分?jǐn)?shù)進(jìn)行約分，那么）可以折半的話蕾管，就折半（也就是用2來(lái)約分）。如果不可以折半的話旷坦，那么就比較分母和分子的大小舌胶，用大數(shù)減去小數(shù)幔嫂，互相減來(lái)減去锰茉，一直到減數(shù)與差相等為止，用這個(gè)相等的數(shù)字來(lái)約分。

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

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

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

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

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

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

質(zhì)數(shù)(Prime number)又稱素?cái)?shù),指在大于1的自然數(shù)中谬盐，除了1和該數(shù)自身外，無(wú)法被其他自然數(shù)整除的數(shù)诚些。大于1的自然數(shù)若不是素?cái)?shù)飞傀，則稱之為合數(shù)。

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

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

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

也就是說(shuō)，如果a雪隧、b互質(zhì)西轩，那么xa+yb=1必然有解。如果xa+yb=1有解脑沿，則a藕畔、b必然互質(zhì)；如果xa+yb=1無(wú)解庄拇，則a注服、b必然不是互質(zhì)。

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

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

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

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

一個(gè)素?cái)?shù)，另一個(gè)不為它的倍數(shù)阁谆，這兩個(gè)數(shù)互質(zhì)碳抄。例如，3與10场绿、5與 26剖效。

相鄰兩個(gè)自然數(shù)互質(zhì)。即裳凸，如果p是大于1整數(shù)贱鄙，則p與p-1、p+1互質(zhì)姨谷。如15與16逗宁、14互質(zhì)

相鄰兩個(gè)奇數(shù)互質(zhì)。如19與21梦湘、17互質(zhì)瞎颗。

RSA公開(kāi)密鑰密碼體制

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

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

正是基于這種理論檬姥，1978年出現(xiàn)了著名的RSA算法曾我，它通常是先生成一對(duì)RSA密鑰，其中之一是保密密鑰健民，由用戶保存抒巢；另一個(gè)為公開(kāi)密鑰，可對(duì)外公開(kāi)秉犹，甚至可在網(wǎng)絡(luò)服務(wù)器中注冊(cè)蛉谜。為提高保密強(qiáng)度，RSA密鑰至少為500位長(zhǎng)崇堵，一般推薦使用1024位型诚。這就使加密的計(jì)算量很大。為減少計(jì)算量鸳劳，在傳送信息時(shí)俺驶，常采用傳統(tǒng)加密方法與公開(kāi)密鑰加密方法相結(jié)合的方式，即信息采用改進(jìn)的DES或IDEA對(duì)話密鑰加密棍辕，然后使用RSA密鑰加密對(duì)話密鑰和信息摘要。對(duì)方收到信息后还绘，用不同的密鑰解密并可核對(duì)信息摘要

思考：

一個(gè)簡(jiǎn)單的作業(yè)讓學(xué)生有深入的思考楚昭。