离散数学（数论基础）

整除性辗转相除

互质质因数分解

合同一次同余式

秦九韶定理 Euler函数

第九次作业

第十次作业

码农公寓

离散数学（数论基础）

整除性辗转相除

互质质因数分解

合同一次同余式

秦九韶定理 Euler函数

第九次作业

第十次作业

相关链接

码农公寓

整除性 辗转相除

互质 质因数分解

合同 一次同余式

秦九韶定理 Euler函数

第九次作业

第十次作业

相关链接

整除性辗转相除

互质质因数分解

合同一次同余式

整除及其性质

整数互质

质数与合数算术基本定理

合同及其性质

剩余类一次同余式

一次同余式组秦九韶定理

Euler函数

整除及其性质

整数互质

质数与合数算术基本定理

合同及其性质

剩余类一次同余式

一次同余式组秦九韶定理

Euler函数

整除及其性质

整数互质

质数与合数 算术基本定理

合同及其性质

剩余类 一次同余式

一次同余式组 秦九韶定理

Euler函数

质数与合数算术基本定理

剩余类一次同余式

一次同余式组秦九韶定理

5.1.2 辗转相除

5.1.2 辗转相除

5.1.2 辗转相除

相关文章

2024-01-20 07:53:58

定义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。（对）

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

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

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

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

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

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