今天又一次被一道数学问题震撼到了。很多感想，特别关于中英基础教育的差别，甚至是大学教育怎样做启发式，创新型教育，而不是填鸭式。我们讨论了很久，停留在嘴上，实际教育又是如何呢？
0. 引言
朋友发来孩子的家庭作业，是一道数学题，题目是这样的。
我简单的翻译一下。 如下图所示是一个简单的数学计算流程。给出初始值A=1084， B=328。 现在请你按照流程图并使用A和B的初始值得出结果。并记录你所得的中间值。说明最终结果和A,B初始值的关系。并说明这种关系是否具有一般性。
题目很简单。给了一个流程图和两个起始数字，要求孩子根据流程图和所给数字给出结果，就是跑流程。关键在后面，题目要求孩子给出最终结果和初始数据的关系。并证明这种关系是否具有一般性？要知道这是一个英国九年级学生（相当于中国的初二）的问题！
作为一名大学老师，自以为很简单，于是着手解决问题。
当然，现在知道了结果，回头看并没有那么困难。试想，仅仅具有一般数学、计算机、或者数论基础的人。估计，第一眼也会发懵。 这就是我当初的感受。
不信的朋友可以试试。直接跳过的后一章。
除过给出的两个数据， 我还随意找了另外一些数据。打开Excel，列出表格，很快试验了两组数据。
结果有了。结果和初始数据的关系是什么呢？
1. 寻找关系
很显然，两个数据不等时，都做了替换动作。而这个替换很典型，就是把两个数据中大的一个替换成它们的差。而且是重复的动作直至，大小关系改变。作为一名专业计算机软件工程师，第一直觉就是，减法实现的除法。这是计算机工程中的常见动作。其实，计算机只会加法，减法是通过加补数来完成；乘法通过移位加来完成；除法通过连续减来实现。所以，过去我们常把计算机的CPU称为加法器。
减法实现除法时一个重要的概念就是余数。余数在计算机里十分重要。很多时候比商还重要。计算机常常把商扔掉。仅仅考虑余数。这就是重要的模数运算。Mod. 提到模数， 不得不说钟表的指针位置。13点和1点时针位置相同。也就是说13和1 的模数相等，都是1。这是因为他们都是模12 的余数。
之所以提到模数运算是因为连续减，直到结果小于减数时，就是计算了模数。连续减的次数就是商。结果就是余数。如第一个例子。1804，连续减了5次328后得到164。就是1804 除以328 商5余164。问题在于，用余数和减数比是什么意思？
如果，这里减法代表除法， 那么，减数除以余数，.....,
直至， 能够整除。减法的结果等于零，说明相等，也就是整除。商1。
这里涉及到模数、整除、余数。 回过头看了，自然是找最大公约数了。可是， 有谁能够从这算式中直接得出？
2。 最大公约数（GCF， GCD）
最大公约数也叫最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数，a，b的最小公倍数记为[a，b]。
其实， 这个作业里列出的算法就是辗转相除法， 也叫欧几里得算法，计算公式gcd(a,b) = gcd(b,a mod b)。它是由古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法。
证法一
a可以表示成a = kb + r（a，b，k，r皆为正整数，且r<b），则r = a mod b
假设d是a,b的一个公约数，记作d|a,d|b，即a和b都可以被d整除。
而r = a - kb，两边同时除以d，r/d=a/d-kb/d=m，由等式右边可知m为整数，因此d|r
因此d也是b,a mod b的公约数
假设d是b,a mod b的公约数, 则d|b,d|(a-k*b),k是一个整数。
进而d|a.因此d也是a,b的公约数
因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证。
证法二
假设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的公约数;
假设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).
这里是我想起我们的祖先也有类似的算法。 叫更相减损术是出自《九章算术》的一种求最大公约数的算法，原文是：
可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。
白话文译文：
（如果需要对分数进行约分，那么）可以折半的话，就折半（也就是用2来约分）。如果不可以折半的话，那么就比较分母和分子的大小，用大数减去小数，互相减来减去，一直到减数与差相等为止，用这个相等的数字来约分。
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是公约数。求“等数”的办法是“更相减损”法。
3. 欧几里得最大公约数算法与目前我们使用的网络加密的RSA算法
质数及互质
质数(Prime number)又称素数,指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数。大于1的自然数若不是素数，则称之为合数。
如果两个或两个以上的整数的最大公约数是 1，则称它们为互质(也叫互素)。两个整数 a 与 b 互质，记为 a ⊥ b。
互质的两个数，有如下性质
整数a和b互质当且仅当存在整数x,y使得xa+yb=1。
也就是说，如果a、b互质，那么xa+yb=1必然有解。如果xa+yb=1有解，则a、b必然互质；如果xa+yb=1无解，则a、b必然不是互质。
这个性质涉及扩展欧几里德算法，我们后面会提到。
互质的判别方法主要有：
两个不同的质数一定互质。例如，2与7、13与19。
较大的数是质数，则两数互质。如33与51
一个素数，另一个不为它的倍数，这两个数互质。例如，3与10、5与 26。
相邻两个自然数互质。即，如果p是大于1整数，则p与p-1、p+1互质。如15与16、14互质
相邻两个奇数互质。如19与21、17互质。
RSA公开密钥密码体制
是一种使用不同的加密密钥与解密密钥，“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制 [2] 。
在公开密钥密码体制中，加密密钥（即公开密钥）PK是公开信息，而解密密钥（即秘密密钥）SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然解密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK [2] 。
正是基于这种理论，1978年出现了著名的RSA算法，它通常是先生成一对RSA密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。这就使加密的计算量很大。为减少计算量，在传送信息时，常采用传统加密方法与公开密钥加密方法相结合的方式，即信息采用改进的DES或IDEA对话密钥加密，然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后，用不同的密钥解密并可核对信息摘要
思考：
一个简单的作业让学生有深入的思考。
