5 3合同 次同余式（PPT63页).pptx

文档介绍：§ 合同 一次同余式
引入
看任意整数a除以3所得的余数：
0 ＝ 0×3 + 0;
1 ＝ 0×3 + 1;
-1 ＝ (-1)×3 + 2;
2 ＝ 0×3 + 2;
-2 ＝ (-1)×3 + 合同并不普遍成立，例如，虽
然20(mod 6)，却不能从合同式
814〔mod 6〕
的两边消去2得出47(mod 6)。但是，下
列两个事实成立：
合同的根本性质
性质9 假设c0而acbc(mod mc)，那么ab(mod m)。
证明：由题设有q使ac-bc=qmc， c0，于是
　　　a-b=qm，因而ab(mod m)。
性质10 假设c和m互质，那么由acbc(mod m)可以推出ab(mod m)。
证明：ac  bc(mod m)表示m|(a-b)c，但c和m互质，
　　　，有
m|(a-b)，故ab(mod m)。
例. 8 22(mod 7)，〔2，7〕=1，那么4 11(mod 7)。
合同的根本性质
性质11 假设acbc(mod m)，且〔c, m〕=d， 那么ab(mod m/d)
证明：由acbc(mod m)知，m|(a-b)c，而
(c, m)=d，故 m/d | (a-b)c/d。注意到〔m/d, c/d〕=1，，
m/d|(a-b)，即 ab(mod m/d)。
结论：假设(c,m)=d,那么(c/d , m/d)=1
①证明：反证法，假设(c/d , m/d)=d’不是1，即d’ >1 , 那么d’|c/d ，dd’|c ,并且d’|m/d ，dd’|m ，得到 dd’为c,m的公因数，那么dd’|d ，即d’|1，矛盾。
合同的根本性质
性质12 假设p为质数，c0(mod p)，而acbc(mod p)，那么ab(mod p)。
证明：因为p是质数，c 0(mod p)就表示p | c, 即c和p互质，(c, p)=1，因而性质12不过是性质10的推论(原来的整数模m换成了现在的质数模p)。
合同的根本性质
性质13 设p(x)是整系数多项式，x和y是整数变量，那么由xy(mod m)可得
p(x) p(y) (mod m)。
证明：设p(x)=anxn+an-1xn-1+…+a1x1+a0,
p(y)=anyn+an-1yn-1+…+a1y1+a0,
由xy(mod m)和性质8, xkyk(mod m).
由性质7得akxkakyk(mod m).
由性质4得 anxn+an-1xn-1+…+a1x1+a0 
anyn+an-1yn-1+…+a1y1+a0 (mod m).
即p(x) p(y) (mod m)。
。
设N=an10n+an-110n-1+…+a110+a0为一正整数，因为101(mod 9)，由性质13得
N an1n+an-11n-1+…+a1+a0(mod 9)
即 。于是 9|N当且仅当9|
§ 剩余类 一次同余式
模m合同既然是一种等价关系，就可以把所有整数按照模 m合同的关系分为等价类，每一个等价类称为模m的一个剩余类。
例如，整数集合Z，模3，得到：
余数为0: {…, -6, -3, 0, 3, 6, …}
余数为1: {…, -5, -2, 1, 4, 7, …}
余数为2: {…, -4, -1, 2, 5, 8, …}
§ 剩余类 一次同余式
同一个剩余类中的数互相合同，不同的剩余类中的数不互相合同。
因为以m去除任意整数，可能得到的余数恰有0，1，…，m-1，这m个数，所以模m共有m个剩余类.
§ 剩余类 一次同余式
从模m每个剩余类中任意取出一个数作为代表，得到m个数，比方r1, r2, …,rm，称这m个数作成一个完全剩余系。
例 0，1，…，m-1便是这样一个完全剩余系，称为模m 的非负最小完全剩余系。
任意整数模m恰好合同于此完全剩余系中的一个数。
例 模3，三个数0，1，2作成一个完全剩余系，-1，0，1也作成一个完全剩余系。
例 模2，两个数0，1作成一个完全剩余系，0代表所有偶数，1代表所有奇数.
同余式
有棋子假设干枚，三个三个的数剩两个，问至少有多少个棋子？
答：由题意，棋子的个数