程序员数学从零开始

第1章重新认识整数（整数分解） 整数的概念来源于计数，它带有很多朴素、自然的性质。本章从整数分解的角度重新看待整数，详解了整数的素因子分解及其应用，并通过欧几里得算式介绍了辗转相除法、更相减损术和Karastuba算法的原理。 整数的概念来源于计数，它带有很多朴素、自然的性质。结绳记事（图11）大概是整数*早的应用，它发生在语言产生以后、文字出现之前的漫长岁月里。《周易·系辞》云：“上古结绳而治”；《春秋左传集解》云：“古者无文字，其有约誓之事，事大大其绳，事小小其绳，结之多少，随扬众寡，各执以相考，亦足以相治也。” 再看汉字中的“数”，从娄从攴（图12）。攴是以手持杖，娄是打了很多绳结的木棍，合起来就是拿着手杖去数绳子上有多少个绳结。数者，结绳而记之也。 图11结绳记事图12古汉字中的“数” 可以毫不夸张地说，整数奠定了数学的基石。19世纪的数学家克罗内克（Kronecker）曾经说过：“上帝创造了整数，其余都是人做的工作。”整数的定义如此简单自然，以至于总是让人忘记它背后的复杂。本章将从分解的视角重新认识整数。 1.1学生的代码和老师的代码 编程总是充满趣味，在学习了判断和循环后就可以编写一些有趣的代码。记得我初学编程时，老师曾出过一个题目：找出两个数的*大公约数。当时我在黑板上写下了自己的实现方式。 代码11学生的代码01def gcd_stu(a, b):02if a < b:03a, b = b, a04result = \[i for i in range(1, b + 1) if b %i == 0 and a %i == 0\]05return result.pop()运行结果是正确的。回到座位上，我为此高兴了2分钟。 后来老师写出了另一个实现。 代码12老师的代码01def gcd_teacher(a, b):02if a < b:03a, b = b, a04return a if b == 0 else gcd_teacher(b, a %b)我的**反应是：“嗯？” 遗憾的是，我当时并没有深究这段代码，只是简单地记住了这种方法，反正都是交给计算机计算，何必在乎快慢呢？ 后来学了数据结构，知道了用大O评估算法效率，我这才开始重新审视那段寻找*大公约数的代码——它实际上使用了传说中的“辗转相除”，要真正弄清楚其来龙去脉，还要从整数说起…… 1.2整除和余数 我们都曾经用笨拙的声音从1数到10，这大概是人生中**次接触数学，稍大一点后懂得了零的概念，再后来知道了还有负数……这些美好的记忆都有整数相伴左右。随着年龄的增长和知识的扩充，我们知道了更多关于整数的知识，其中就包括整除和余数。 1.2.1欧几里得算式 数学中是以数轴分段的方式定义整除的，如果n是一个正整数，那么可以用n的倍数将数轴分成很多段，如图13所示。 图13用n的倍数将数轴分成很多段 如果将另一个整数m放在数轴上，那么m将正好位于qn和（q+1）n之间，其中q也是一个整数，如图14所示。 图14m位于qn和（q+1）n之间 如果m正好是n的整数倍，那么m=qn；否则可以写成m=qn+r的形式，其中qn是位于m左侧*近的n的整数倍，r是qn到m的整数距离。如果把两种情况合并，那么对于任意整数m和n，且n≠0，总是可以写成下面的形式： m=qn+r,0≤r对于特定的n来说，m的表达是唯一的，这种表达式叫作欧几里得算式，也叫作除法算式。 看上去很复杂，其实欧几里得算式有更常见的描述：如果m和n都是整数，且n≠0，那么总是存在整数q和r，0≤rm÷n=q……r 其中q是商，r是余数，如果r=0，则称m能够被n整除，或称n能整除m，记作n|m，其中“|”是整除符号。可见，欧几里得算式只不过是从代数上解释了整除和余数。 乘法和除法互为逆运算，把欧几里得算式写成乘法就变成了m的唯一的表达式： m=qn+r 示例11找出q和r（1）m=10,n=3； （2）m=3,n=10； （3）m=-11,n=5。 前两个比较简单。 （1）10=3×3+1,q=3,r=1。 （2）3=10×0+3,q=0,r=3。 图15在计算机 上计算-11%5第三个可能会出点差错。 （3）-11=5×（-2）-1,q=-2,r=-1。 在计算机上计算-11%5，结果如图15所示。 看来计算机认为是另一种答案：-11=5×（-3）+4,q=-3,r=4。 整除的定义终于显现出作用了，余数的取值范围是0≤r1.2.2整除的性质 如果a、b、c都是整数，则有以下3个被人们熟知的关于整除的性质。 性质1.1 如果a|b且a|c，则a|（b+c）。 性质1.2 如果a|b，则a|cb。 性质1.3如果a|b且b|c，则a|c。 注：由于0不能作为除数，所以a|b包含的默认条件是a≠0。 此外，还有一个推论：如果a、b、c都是整数，当a|b且a|c时，对于任意整数m和n，都有a|（mb+nc）。 除法和乘法互为逆运算，这些性质和推论其实都是根据乘法的分配律和结合律推导而来的，以性质1.1为例： ab and acb=pa,c=qa b+c=pa+qa=（p+q）a p+q是一个整数，根据欧几里得算式对整除的定义，得出a|（b+c）。