离散数学（数论基础）

整除性辗转相除

互质质因数分解

合同一次同余式

秦九韶定理 Euler函数

第九次作业

第十次作业

整除及其性质

5.1.2 辗转相除

整数互质

质数与合数算术基本定理

合同及其性质

剩余类一次同余式

一次同余式组秦九韶定理

Euler函数

定义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 ：任意二整数a，b有最高公因数。

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

辗转相除法求最高公因式：

使用辗转相除法求两个数a，b的最高公因数并表示为它们的倍数和，需要使用的主要公式如下：

\[\mathrm{S}_0=0,\mathrm{S}_1=1,\mathrm{T}_0=1,\mathrm{T}_1=\mathrm{q}_1
\\
\mathrm{S}_{\mathrm{k}}=\mathrm{q}_{\mathrm{k}}\mathrm{S}_{\mathrm{k}-1}+\mathrm{S}_{\mathrm{k}-2}
\\
\mathrm{T}_{\mathrm{k}}=\mathrm{q}_{\mathrm{k}}\mathrm{T}_{\mathrm{k}-1}+\mathrm{T}_{\mathrm{k}-2}
\\
\mathrm{d}=\left( -1 \right) ^{\mathrm{n}-1}\mathrm{S}_{\mathrm{n}}\mathrm{a}+\left( -1 \right) ^{\mathrm{n}}\mathrm{T}_{\mathrm{n}}\mathrm{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}=\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)的解。

定理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下解唯一：

\[\left. \begin{array}{r}
\mathrm{x}\equiv \mathrm{a}_1\left( \mathrm{mod} \quad\mathrm{m}_1 \right) ,\\
\mathrm{x}\equiv \mathrm{a}_2\left( \mathrm{mod} \quad\mathrm{m}_2 \right) ,\\
\mathrm{……} \mathrm{……} \mathrm{……},\\
\mathrm{x}\equiv \mathrm{a}_{\mathrm{k}}\left( \mathrm{mod} \quad\mathrm{m}_{\mathrm{k}} \right)\\
\end{array} \right\} \left( 1 \right)
\]

习题：

结论：设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

k	0	1	2	3	4	5	6	7	8	9
$\mathrm{r}_{\mathrm{k}}$		591	455	136	47	42	5	2	1	0
$\mathrm{q}_{\mathrm{k}}$		2	1	1	3	2	1	8	2	2
$\mathrm{S}_{\mathrm{k}}$	0	1	1	2	7	16	23	200	423
$\mathrm{T}_{\mathrm{k}}$	1	2	3	5	18	41	59	513	1085

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

公式：

\[\mathrm{S}_0=0,\mathrm{S}_1=1,\mathrm{T}_0=1,\mathrm{T}_1=\mathrm{q}_1\\\mathrm{S}_{\mathrm{k}}=\mathrm{q}_{\mathrm{k}}\mathrm{S}_{\mathrm{k}-1}+\mathrm{S}_{\mathrm{k}-2}\\\mathrm{T}_{\mathrm{k}}=\mathrm{q}_{\mathrm{k}}\mathrm{T}_{\mathrm{k}-1}+\mathrm{T}_{\mathrm{k}-2}\\\mathrm{d}=\left( -1 \right) ^{\mathrm{n}-1}\mathrm{S}_{\mathrm{n}}\mathrm{a}+\left( -1 \right) ^{\mathrm{n}}\mathrm{T}_{\mathrm{n}}\mathrm{b}
\]

2、判断题：0和1 是互质的。（对）

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

3、判断题：0和100的最高公因数是±100。（对）

$\mathrm{r}_{\mathrm{k}}$

$\mathrm{q}_{\mathrm{k}}$

$\mathrm{S}_{\mathrm{k}}$

$\mathrm{T}_{\mathrm{k}}$

判定同余式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)