一、整除的概念，歐幾里得除法

1、整除的概念

定義1.1：

設a，b是任意兩個整數，其中b ≠ 0.如果存在一個整數q使得等式 a = q · b 成立，就稱 b 整除 a 或者 a 被 b 整除，記作 b | a，并把b叫做a的因數，把a叫做b的倍數，人們常把q寫成 a / b，否則，就稱b不能整除a，或者a不能被b整除，

此外，再不會混淆的情況下，乘法a·b簡記為ab，

注：

（1）當b遍歷整數a的所有因數時，-b也遍歷整數a的所有因數，

（2）當b遍歷整數a的所有因數時，a/b也遍歷整數a的所有因數，

根據定義有：

0是任何非零整數的倍數，
1是任何整數的倍數，
任何非零整數a是其本身的倍數，也是其自身的因數，

定理1.1：

設a，b ≠ 0，c ≠ 0是三個整數，若 b | a，c | b，則c | a，

定理1.2：

設a，b，c ≠ 0是三個整數，若c | a，c | b，則c | a ± b，

定理1.3：

設a，b，c ≠ 0是三個整數，若c | a，c | b，則對任意整數s，t，有c |（s·a+t·b），

定理1.4：

設整數c ≠ 0，若整數a_{1，···，}a_n都是整數c的倍數，則對任意n個整數s₁，···，s_n，整數s₁a₁+ ··· + s_na_n是c的倍數，

定理1.5：

設a，b都是非零整數，若a | b，b | a，則a = ±b，

定義1.2：

設整數n ≠ 0，±1.如果除了顯然因數±1和±n外，n沒有其他因數，那么n就叫做素數（或質數或不可約數），否則，n叫做合數，

定理1.6：

設n是一個正合數，p是n的一個大于1的最小正因數，則p一定是素數，且p≤n^1/2，

2、Eratoshenes篩法

定理1.7：

設n是正整數，若果對所有的素數p ≤ n^1/2，都有p不被n整除，則n一定是素數，

應用該定理，可得到一個尋找素數的確定性方法，通常叫做平凡除法或厄拉托塞師篩法，

3、歐幾里得除法 —— 最小非負余數

定理1.9（歐幾里得除法）：

設a，b是兩個整數，其中b>0，則存在唯一的整數q，r使得a = q·b + r ，0 ≤ r ≤ b ，

定義1.3：

a = q·b + r ，0 ≤ r ≤ b中，q叫做a被b除所得的不完全商，r叫做a被b除所得的余數，

定義1.4：

設x是實數，稱x的整數部分為小于或等于x的最大整數，記成[x]，

這時，有[x] ≤ x＜ [x]+1，

4、素數的平凡判別

素數的平凡判別：對于給定正整數N，設不大于N^1/2的所有素數為p₁，p_2,，···，p_s，

如果N被所有p_i除的余數都不為零，則N是素數，

5、歐幾里得除法 —— 一般余數

定理1.10（歐幾里得除法）：

設a，b是兩個整數，其中b＞0.則對任意的整數c，存在唯一的整數q，r使得

a = q·b+r，c ≤ r＜b+c

二、整數的表示

1、b進制

定理2.1：

設b是大于1的正整數，則每個正整數n可唯一地表示成

n = a_k-1b^k-1 + a_k-2b^k-2 + ··· + a₁b + a₀，

其中a_i是整數，0 ≤ a_i ≤ b-1，i = 1，···，k-1，且首項系數a_k-1 ≠ 0.

2、計算復雜性

大O符合和小o符號

大O符號：

設f(n)和g(n)都是正整數n的正值函式，如果存在一個正常數C，使得對任意的正整數n都有f(n) ≤ Cg(n)，

就稱g(n)是f(n)的界，記作f(n) = O(g(n))，簡記為f = O(g)，

小o符號：

設f(n)和g(n)都是正整數n的正值函式，如果對任意小的正數€，存在一個正整數N₀，使得對任意的正整數n ＞ N₀都有f(n) ＜ €g(n)，

就稱g(n)是比f(n)高階的無窮量，記作f(n) = o(g(n))，簡記為f = o(g)，

三、最大公因數與廣義歐幾里得除法

1、最大公因數

定義3.1：

設a₁，···，a_n是n（n≥2）個整數，若整數d是它們中每一個數的因數，則d就叫做a₁，···，a_n的一個公因數，

d是a₁，···，a_n的一個公因數的數學運算式為：d | a₁，···，d | a_n，

如果整數a₁，···，a_n不全為零，那么a₁，···，a_n的所有公因數中最大的一個公因數叫做最大公因數，記作（a₁，···，a_n），

特別地，當（a₁，···，a_n） = 1 時，稱a₁，···，a_n互質或互素，

注①：d ＞ 0是a₁，···，a_n的最大公因數的數學運算式可表述為

d | a₁，···，d | a_n
若 e | a₁，···，e | a_n，則e | d，

注②：a，b的最大公因數 d = （a，b）是集合

　　{ s · a + t · b | s， t ∈ Z}

注③：a₁，···，a_n的最大公因數 d 是集合

　　{ s₁ · a₁ + ··· + s_n · a_n | s₁，···，s_n ∈ Z}

定理3.1：

設a₁，···，a_n是n個不全為零的整數，則

a₁，···，a_n 與 |a₁|，···，|a_n|的公因數相同
（a₁，···，a_n）=（|a₁|，···，|a_n|），

定理3.2：

設b是任一正整數，則（0，b）= b，

定理3.3：

設a，b，c是三個不全為零的證書，如果a = q · b + c，其中q是整數，則（a，b）= （b，c）

性質3.1：

定理3.4：

定理3.5：

2、最大公因數的進一步性質

定理3.9：

設a，b是任意兩個不全為零的整數，d是正整數，則d是整數a，b的最大公因數的充要條件是：

d | a，b | b；
若 e | a，e | b，則e | d，

假設1,2成立，那么

說明d是整數a，b的公因數；
說明d是整數a，b的公因數中的最大數，因為e | d 時，有 | e | ≤ d，

因此，d是整數a，b的最大公因數，

定理3.10：

定理3.11：

定理3.12：

定理3.13：

3、多個整數的最大公因數及運算

定理3.14：

定理3.15：

4、形為2^α-1的整數及其最大公因數

四、整除的進一步性質及最小公倍數

1、整數的進一步性質

定理4.1：

設a，b，c是三個整數，且c ≠ 0，如果c | ab，（a，c）= 1，則c | b，

定理4.2：

設p是素數，若p | ab，則p | a 或 p | b，

定理4.3：

設a₁，···，a_n是n個整數，p是素數，若p | a₁，···，a_n，則p一定整除某一a_k，1 ≤ k ≤ n，

第1章 整數的可除性 -《資訊安全數學基礎》

一、整除的概念，歐幾里得除法

1、整除的概念

定義1.1：

定理1.1：

定理1.2：

定理1.3：

定理1.4：

定理1.5：

定義1.2：

定理1.6：

2、Eratoshenes篩法

定理1.7：

3、歐幾里得除法 —— 最小非負余數

定理1.9（歐幾里得除法）：

定義1.3：

定義1.4：

4、素數的平凡判別

5、歐幾里得除法 —— 一般余數

定理1.10（歐幾里得除法）：

二、整數的表示

1、b進制

定理2.1：

2、計算復雜性

大O符合和小o符號

三、最大公因數與廣義歐幾里得除法

1、最大公因數

定義3.1：

定理3.1：

定理3.2：

定理3.3：

性質3.1：

定理3.4：

定理3.5：

2、最大公因數的進一步性質

定理3.9：

定理3.10：

定理3.11：

定理3.12：

定理3.13：

3、多個整數的最大公因數及運算

定理3.14：

定理3.15：

4、形為2α-1的整數及其最大公因數

四、整除的進一步性質及最小公倍數

1、整數的進一步性質

定理4.1：

定理4.2：

定理4.3：

2、最小公倍數

定義4.1：

定理4.4：

3、最小公倍數與最大公因數

定理4.5：

4、多個整數的最小公二倍數

定理4.6：

定理4.7：

五、整數分解

定理5.1：

六、素數的算數基本定理

1、算數的基本定理

定理6.1：

定理6.2：

2、算數基本定理的應用

定理6.3：

定理6.4：

定理6.5：

定理6.6：

七、素數定理

定理7.1：

第1章整數的可除性 -《資訊安全數學基礎》

4、形為2^α-1的整數及其最大公因數