第1章重新認識整數（整數分解）
整數的概念來源於計數，它帶有很多樸素、自然的性質。本章從整數分解的角度重新看待整數，詳解了整數的素因子分解及其應用，並通過歐幾裡得算式介紹了輾轉相除法、更相減損術和Karastuba算法的原理。
整數的概念來源於計數，它帶有很多樸素、自然的性質。結繩記事（圖11）大概是整數最早的應用，它發生在語言產生以後、文字出現之前的漫長歲月裡。《周易·繫辭》雲：“上古結繩而治”；《春秋左傳集解》雲：“古者無文字，其有約誓之事，事大大其繩，事小小其繩，結之多少，隨揚眾寡，各執以相考，亦足以相治也。”
再看漢字中的“數”，從婁從攴（圖12）。攴是以手持杖，婁是打了很多繩結的木棍，合起來就是拿著手杖去數繩子上有多少個繩結。數者，結繩而記之也。
圖11結繩記事圖12古漢字中的“數”
可以毫不誇張地說，整數奠定了數學的基石。19世紀的數學家克羅內克（Kronecker）曾經說過：“上帝創造了整數，其餘都是人做的工作。”整數的定義如此簡單自然，以至於總是讓人忘記它背後的復雜。本章將從分解的視角重新認識整數。
1.1學生的代碼和老師的代碼
編程總是充滿趣味，在學習了判斷和循環後就可以編寫一些有趣的代碼。記得我初學編程時，老師曾出過一個題目：找出兩個數的最大公約數。當時我在黑板上寫下了自己的實現方式。
代碼11學生的代碼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分鐘。
後來老師寫出了另一個實現。
代碼12老師的代碼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的倍數將數軸分成很多段，如圖13所示。
圖13用n的倍數將數軸分成很多段
如果將另一個整數m放在數軸上，那麼m將正好位於qn和（q+1）n之間，其中q也是一個整數，如圖14所示。
圖14m位於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
示例11找出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。
圖15在計算機
上計算-11%5第三個可能會出點差錯。
（3）-11=5×（-2）-1,q=-2,r=-1。
在計算機上計算-11%5，結果如圖15所示。
看來計算機認為是另一種答案：-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 acb=pa,c=qa
b+c=pa+qa=（p+q）a
p+q是一個整數，根據歐幾裡得算式對整除的定義，得出a|（b+c）。
