整除及其性質

定義5.1.1 ：設a和b是任意整數，若存在整數c，使得a=bc，則稱a是b的倍數，b是a的因數。或者稱a被b整除，而b整除a。記為b|a。

注意：

（1）任意整數整除0 ，特別0|0； 0=b·0；(c=0) 0=0·c(c可以是任意整數)，但0不能整除任意非零整數。a=0·c(a≠0)

（2）1和（-1）整除任意整數。 a=1·a；a=(-1)·(-a)

推論：b|a，(b\(\ne\) 0) 當且僅當a被b除（或者a除以b,或者b除a）的余數為0。

整除的基本性質

性質1 若a|b，b|c，則a|c （傳遞性）

性質2 若a|b，則a|bc （b|bc用傳遞性證明)

性質3 若a|b，a|c，則a|b\(\pm\)c。

性質4 若a整除b1,…,bn, 則a| \(\mathrm{\lambda}_1\mathrm{b}_1\)+…+ \(\mathrm{\lambda}_n\mathrm{b}_n\)，其中\(\mathrm{\lambda}_{\mathrm{i}}\)為任意整數。

性質5 若在一等式中，除某項外，其余各項都是a的倍數，則此項也是a的倍數

性質6 若a|b，b|a，則b=\(\pm\)a

性質7 設a=qb+c，則a，b的公因數與b，c的公因數是完全相同的

定義5.1.2

若d是a的因數也是b的因數，則稱d為a，b的公因數。
若d是a，b的公因數，而a，b的任意公因數整除d，則稱d為a，b的最高公因數。a，b的最高公因數通常記為d=(a,b)。

例：8，12有公因數：±1, ±2, ±4, 其中， ±1|4, ±2|4, ±4|4，(注意正負）則4是8和12的最高公因數，記為4=(8, 12)。-4也是

問題：0和0的最高公因數是多少？ 【答】：0

5.1.2 輾轉相除

定理5.1.2 ：任意二整數a，b有最高公因數。

定理5.1.3：任意二整數a，b的最高公因數d可以表示為a，b的倍數和，即表為下面的形式：d=sa+tb 其中 s，t都是整數。

輾轉相除法求最高公因式：

使用輾轉相除法求兩個數a，b的最高公因數并表示為它們的倍數和，需要使用的主要公式如下：

互質 質因數分解

整數互質

定義5.2.1 ： 若a，b除±1外無其它公因數，則稱a和b互質。

結論：

1、a和b互質，必要而且只要a、b的最高公因數為1(通常只考慮+1)。

2、±1和任意整數(包括0)互質。

定理5.2.1 ：a和b互質，當且僅當1可表示為a和b的倍數和形式，即存在整數s和t使1=sa+tb。

定理5.2.2：若a和b互質，而a|bc，則a|c。

定理5.2.3：若b和a1，a2，…，an都互質，則b和a1a2…an互質。

定理5.2.4：若m1，m2，…，mk兩兩互質而都整除a，則m1m2…mk|a。

常用結論：\(2^{\mathrm{p}}\)-1和\(2^{\mathrm{q}}\)-1互質的充要條件是p和q互質。

質數與合數 算術基本定理

定義5.2.2：一個正整數，如果不等于1而且除了自己和1沒有其它正因數，則稱其為一個質數(也稱為素數)；否則稱其為合數。
這樣，正整數分為{1, 質數，合數}

結論：

1、質數p和a互質，必要而且只要p \(\nmid\) a

2、任意兩個不同的質數互質

定理5.2.5 ：設p為質數，若p整除a1a2…an，則p整除a1，a2，…，an之一。

定理5.2.6 (算術基本定理)：任意正整數n（n\(\ne\) 1）恰有一法寫成質數的乘積（不計因數乘積的順序）。

推論1： 任意整數(\(\ne\) 0，\(\ne\) ±1)恰好有一法寫成下面的形式：±\(\mathrm{p}_1\)…\(\mathrm{p}_k\)，其中\(\mathrm{p}_1\),…,\(\mathrm{p}_k\)都是質數。

推論2： 任意整數(\(\ne\) 0，\(\ne\) ±1)恰好有一法寫成下面的形式：±\({\mathrm{p}_1}^{\mathrm{r}_1}\)…\({\mathrm{p}_n}^{\mathrm{r}_n}\)，其中\(\mathrm{p}_1\),…,\(\mathrm{p}_n\)是不同的質數，\(\mathrm{r}_1\),…,\(\mathrm{r}_n\)是正整數。

定理5.2.7：質數無窮多。

合同 一次同余式

合同及其性質

定義. 設a,b為二整數，m是任意非0整數。若 m|a-b，則稱a合同于b 模m。記為：a\(\equiv\)b(mod m)

注意：

（1）合同為整除的另一種表示法，故整除的性質在此可用。特別地，若b=0，則a$\equiv$0(mod m)表示的就是m|a。

（2）若m|a，則- m|a。所以，若未指定m而一般地討論模m合同時，總假定m是正整數。

（3）a\(\equiv\)b(mod m) iff 以m除a和b所得的余數相同

合同的基本性質：

性質1： a\(\equiv\)a。
性質2： 若a\(\equiv\)b,則b\(\equiv\)a。
性質3： 若a\(\equiv\)b，b\(\equiv\)c，則a\(\equiv\)c。
故合同是一種等價關系。
每一個等價類稱為模m的一個剩余類。

性質4： 若a\(\equiv\)b(mod m),c\(\equiv\)d(mod m)，則a\(\pm\)c\(\equiv\)b\(\pm\)d(mod m)，ac\(\equiv\)bd(mod m)

性質5： 若a\(\equiv\)b(mod m)，則a\(\pm\)k\(\equiv\)b\(\pm\)k (mod m)。其中k為整數。

性質6： 若a+b\(\equiv\)c(mod m)，則a\(\equiv\)c-b(mod m)。

性質7： 若a\(\equiv\)b(mod m)，則ac\(\equiv\)bc(mod m)。

性質8： 若a\(\equiv\)b(mod m)，則\(\\\mathrm{a}^{\mathrm{n}}\equiv \mathrm{b}^{\mathrm{n}}\)(mod m)， n$\geqslant $0

性質9： 若c\(\ne\) 0而ac\(\equiv\) bc(mod mc)，則a\(\equiv\) b(mod m)。

性質10： 若c和m互質，則由ac\(\equiv\)bc(mod m)可以推出a\(\equiv\)b(mod m)。

性質11： 若ac\(\equiv\)bc(mod m)，且（c, m）=d， 則a\(\equiv\)b(mod m/d)

其實性質9和10是都性質11的特例，因為性質9里(c,m)=d=c，性質10里(c,m)=d=1

結論：若(c,m)=d,則(c/d , m/d)=1

對于質數模p(即模p為質數，如mod 3)，則有與相等完全類似的消去律。

性質12： 若p為質數，c\(\not \equiv\) 0(mod p)，（c,p互質），而ac\(\equiv\) bc(mod p)，則a\(\equiv\) b(mod p)。

性質13： 設p(x)是整系數多項式，x和y是整數變量，則由x\(\equiv\)y(mod m)可得p(x) \(\equiv\)p(y) (mod m)。

剩余類 一次同余式

等價類、剩余類：模m合同既然是一種等價關系，就可以把所有整數按照模 m合同的關系分為等價類，每一個等價類稱為模m的一個剩余類。

例如，整數集合Z，模3，得到：
余數為0: {…, -6, -3, 0, 3, 6, …}
余數為1: {…, -5, -2, 1, 4, 7, …}
余數為2: {…, -4, -1, 2, 5, 8, …}

1、同一個剩余類中的數互相合同，不同的剩余類中的數不互相合同。

2、因為以m去除任意整數，可能得到的余數恰有0，1，…，m-1，這m個數，所以模m共有m個剩余類。

3、從模m每個剩余類中任意取出一個數作為代表，得到m個數，比方r1, r2, …,rm，稱這m個數作成一個完全剩余系。

例1： 0，1，…，m-1便是這樣一個完全剩余系，稱為模m 的非負最小完全剩余系。
任意整數模m恰好合同于此完全剩余系中的一個數。
例2： 模3，三個數0，1，2作成一個完全剩余系，-1，0，1也作成一個完全剩余系。
例3： 模2，兩個數0，1作成一個完全剩余系，0代表所有偶數，1代表所有奇數.

同余式：含有整數變量的合同式，稱為合同方程或同余式 。

ax\(\equiv\)b(mod m)這種形式的合同式稱為一次同余式；類似地，\(\mathrm{a}_2\mathrm{x}^2+\mathrm{a}_1\mathrm{x}\equiv \mathrm{b}\left( \mathrm{mod} \mathrm{m} \right)\)稱為二次同余式。

一次同余式解的個數：

1、若a和m互質，b任意，則模m恰有一個數x使ax\(\equiv\) b(mod m) 。

推論：設p為質數。若a\(\not \equiv\) 0 (mod p)，b任意，則模p恰有一個數x使ax\(\equiv\) b(mod p)。

2、若(a, m)=d>1 ，且d|b，則同余式ax\(\equiv\) b(mod m)有d個解

求解一次合同方程的方法 ：

方法一：先使用輾轉相除方法將互質的a與m的最大公因數1表示為a和m的倍數和的形式：1=as+mt，然后取x=sb，即可。

注意：\(\mathrm{s}=(-1)^k\mathrm{T}_{\mathrm{k}}\)

方法二 ：就是利用合同的性質，使x的系數變成1，即得到解。

定理5.3.2：若(a, m)=d>1，且d\(\nmid\)b，則同余式ax\(\equiv\) b (mod m)無解。

本定理可以作為同余式無解的判定定理.

定理5.3.3：若(a, m)=d>1 ，且d|b，則同余式ax\(\equiv\)b(mod m)有d個解，分別為 \(\mathrm{\alpha}\), \(\mathrm{\alpha}\)+m/d, \(\mathrm{\alpha}\)+2m/d, …, \(\mathrm{\alpha}\)+(d-1)m/d ……
其中\(\mathrm{\alpha}\)是同余式(a/d)x\(\equiv\)b/d (mod m/d)的解。

秦九韶定理 Euler函數

一次同余式組 秦九韶定理

定理5.4.1 設[m1,m2]為m1，m2的最低公倍數。則同余式組
x\(\equiv\)a1 (mod m1)
x\(\equiv\)a2 (mod m2) ……………..(1)
在mod[m1,m2]下有唯一解的充要條件為
(m1,m2)|(a1-a2) ……………………….(2)

Note：當此定理中的(m1,m2)=1這種特殊情況時，則（1）有關于模m1m2唯一解。推廣此特殊情形即得到中國剩余定理，也稱為孫子定理。后經過秦九韶整理和解法的推廣，我們這里稱之為秦九韶定理。

秦九韶定理 ：設m1, m2 , …, mk兩兩互質。a1, a2, …, ak為k個整數，則下列同余式組有解，且在模m1 m2 …mk下解唯一：

習題：

Euler函數

結論：設n是任意正整數， A 為mod n的任意剩余類，a\(\in\)A。若a和n互質，則A中任意數和n互質。

若A中有一個數和n互質，則其中所有的數都和n互質。故A 中的數或者都和n互質，或者都和n不互質。

**例. ** mod 6
2，8，16 ，…,與6都不互質。
5，11，17，…,與6都互質。

定義：設A 為mod n的一個剩余類，若對a\(\in\)A，a與n互質，則稱剩余類A與n互質。

Euler函數 ：

定義： 和n互質的剩余類的個數稱為Euler(歐拉)函數,記為\(\mathrm{\varphi}\)(n)。
定義 ：從和n互質的每一個剩余類中取出一個數，這樣得到的\(\mathrm{\varphi}\)(n)個數稱之為作成mod n的一個簡化剩余系。
顯然，從mod n的一個非負最小完全剩余系中取出與n互質的那些數,就得到mod n的一個簡化剩余系，因而\(\mathrm{\varphi}\)(n)等于\(\leqslant\)n的正數中和n互質的數的個數。

例 n=10，則mod n的一個完全剩余系為0，1，…，9，一個簡化剩余系為1，3，7，9，\(\mathrm{\varphi}\)(10)=4。
例 n=12，則mod n的一個完全剩余系為0，1，…，11，一個簡化剩余系為1，5，7，11，\(\mathrm{\varphi}\)(12)=4。

定理5.4.5 ：設m=m1…mk，而m1, …, mk兩兩互質。則\(\mathrm{\varphi}\)(m)= \(\mathrm{\varphi}\)(m1)\(\mathrm{\varphi}\)(m2) …\(\mathrm{\varphi}\)(mk)

例. \(\mathrm{\varphi}\)(2646)= \(\mathrm{\varphi}\)(2×27×49)
= \(\mathrm{\varphi}\)(2) ×\(\mathrm{\varphi}\)(27)×\(\mathrm{\varphi}\)(49)

定理5.4.6 ：\( \text{設n}={\mathrm{p}_1}^{\mathrm{r}_1}{\mathrm{…p}_{\mathrm{k}}}^{\mathrm{r}_{\mathrm{k}}}\text{是n的質因數分解式，p}_1\mathrm{…p}_{\mathrm{k}}\text{都不相同，于是} \\ \mathrm{\varphi}\left( \mathrm{n} \right) =\mathrm{n}\left( 1-\frac{1}{\mathrm{p}_1} \right) \mathrm{…}\left( 1-\frac{1}{\mathrm{p}_{\mathrm{k}}} \right)\)

\(\text{例} \mathrm{\varphi (}2646)=\mathrm{\varphi (}2×3^3×7^2)=2646×(1-1/2)(1-1/3)(1-1/7)=756\)

定理5.4.7(Fermat-Euler定理,Euler1760年提出) ：若a和n互質，則\(\mathrm{a}^{\mathrm{\varphi}\left( \mathrm{n} \right)}\equiv 1\)(mod n)

\(\text{例}：a=3,n=10,3與10互質,\mathrm{\varphi (}10)=4,則3^4\equiv 1(mod10) \\ a=5,n=12,5與12互質,\mathrm{\varphi (}12)=4,則5^4\equiv 1(mod12)\)

推論1 (Fermat小定理Ⅰ)
若p是質數而p \(\nmid\) a，則\(\mathrm{a}^{\mathrm{p}-1}\equiv 1\)(mod p)。

推論2（Fermat小定理Ⅱ）
若p為質數，則對任意整數a,都有\(\mathrm{a}^{\mathrm{p}}\equiv a\)(mod p)。

例:p=3, a=2, \(2^{3-1}\equiv 1\left( \mathrm{mod} 3 \right)\) \(2^{3}\equiv 2\left( \mathrm{mod} 3 \right)\)

例題：

第九次作業

1、用輾轉相除法求1046和2683的最高公因數并表示為它們的倍數和。

2683/1046=2……591

1046/591=1……455

591/455=1……136

455/136=3……47

136/47=2……42

47/42=1……5

42/5=8……2

5/2=2……1

2/1=2……0

最高公因數：\(1=\left( -1 \right) ^{8-1}\times 423\times 2683+\left( -1 \right) ^8\times 1085\times 1046\) （注意n是最后一個非零余項的n）

公式：

2、判斷題：0和1 是互質的。（對）

【解】±1和任意整數(包括0)互質。

3、判斷題：0和100的最高公因數是±100。（ 對 ）

第十次作業

判定同余式206x\(\equiv\) 114(mod 422)是否有解，如果存在請給出解。

【解】(206,114)=2且2|114故有兩個解

? 法一：

? 先求103\(\equiv\) 57(mod 211)的解

? 211=103*2+5

? 故206x\(\equiv\) 114(mod 211) 又因為211x\(\equiv\) 0(mod 211)

? 5x\(\equiv\) -114(mod 211)

? 5x\(\equiv\) 97(mod 211)

? 因為211=42*5+1

? 故210x\(\equiv\) 12936(mod 211)

? 211x\(\equiv\) 0(mod 211)

? x\(\equiv\) -12936(mod 211)

? x\(\equiv\) 146(mod 211)

? 故x\(\equiv\) 146(mod 422) x\(\equiv\) 357(mod 422)

? 法二：

? 先求103$\equiv$57(mod 211)的解

? 211=103*2+5

? 103=20*5+3

? 5=3*1+2

? 3=2*1+1

? 2=1*2+0

最高公因式：\(1=\left( -1 \right) ^3\times 41\times 211+\left( -1 \right) ^4\times 84\times 103\)

由此知：\(\mathrm{S}=\left( -1 \right) ^4\times 84=84\)

? \(x=Sb=84\times57=4788=211\times 23-65\equiv -65\left( \mathrm{mod } 211 \right) \equiv 146\left( \mathrm{mod } 211 \right)\)

歸正以后得x\(\equiv\) 146(mod 422) x\(\equiv\) 357(mod 422)

往期回顧

離散數學（集合論）
離散數學（古典數理邏輯）
離散數學（圖與網絡）
離散數學（數論基礎）
離散數學（格與布爾代數）
離散數學（群、環、域）