例 9 2.1整除与同余
2.1整除与同余
整除与同余 例 学6 整除 同余
整除与同余 整除 同余
整除 。整除的定义 ■对于整数4b(呋0)，如果存在整数x使得b=心，则称整除b, 或a是b的因子，记作db。 。性质 ■da。 ■如果db,ba,则=士b。 ■如果adb,blc,则ac。 ■如果db,dlc,则对任意的整数x,y,有dl(br+gy)
整除 整除的定义 对于整数a, b(a≠0)，如果存在整数x使得b=ax，则称a整除b， 或a是b的因子，记作a|b。 性质 a|a。 如果a|b, b|a，则a=±b。 如果a|b, b|c，则a|c。 如果a|b, a|c，则对任意的整数x, y，有a|(bx+cy)
整除 。公因子 ■如果，b,c都是整数，a和b不全为0且ca,cb,则称c是a和b的 公因子。 ·最大公因子 ■d是a和b的公因子； ■a和b的任一公因子，也是d的因子。 ■则称d是a和b的最大公因子(greatest common divisor),记为 =gcd(a,b)。 ■gcd(a,b)=1台a,b互素
整除 公因子 如果a, b, c都是整数，a和b不全为0且c|a, c|b，则称c是a和b的 公因子。 最大公因子 d是a和b的公因子； a和b的任一公因子，也是d的因子。 则称d是a和b的最大公因子(greatest common divisor)，记为 d=gcd(a, b)。 gcd(a, b)=1 ⇔ a，b互素
整除 。素数 ■对于任一整数p(>1),如果p的因子只有士1和士p,则称p为 素数；否则称为合数。 。算数基本定理 ■对于任一整数（心1），都可以唯一的分解为素数的乘积，即 a=pp2…p 其中，p1p20(i=1,2,,)
整除 素数 对于任一整数p(p>1)，如果p的因子只有±1和±p，则称p为 素数；否则称为合数。 算数基本定理 对于任一整数a(a>1)，都可以唯一的分解为素数的乘积，即 其中，p10(i=1, 2, …, t)。 1 2 1 2 t a a a t a p p p
整除 ·欧拉函数 ■设n是一正整数，小于n且与n互素的正整数的个数称为欧拉 (Euler)函数，记为p(n)。 。性质 ■如果n是素数，则p(n)=n-1; ■如果m和n互素，则p(mn)=p(m)p(n); 如果n=p1p2p,其中，p1<p,<<印，都是素数， a0(-1,2,0则p(m）=n(1-点(1-动(1-。 ■p(9)=6,可以知道1,2,4,5,7,8与9互素
整除 欧拉函数 设n是一正整数，小于n且与n互素的正整数的个数称为欧拉 (Euler)函数，记为𝝋(𝒏)。 性质 如果n是素数，则𝝋 𝒏 = 𝒏 − 𝟏； 如果m和n互素，则𝝋 𝒎𝒏 = 𝝋 𝒎 𝝋 𝒏 ； 如果𝒏 = 𝒑𝟏 𝒂𝟏𝒑𝟐 𝒂𝟐 ⋯ 𝒑𝒕 𝒂𝒕 ，其中，p10(i=1, 2, …, t)，则𝝋(𝒏) = 𝒏(𝟏 − 𝟏 𝒑𝟏 ) (𝟏 − 𝟏 𝒑𝟐 ) ⋯ (𝟏 − 𝟏 𝒑𝒕 )。 𝝋(𝟗) = 𝟔，可以知道1，2，4，5，7，8与9互素
同余 ·同余定义 ■设n是一正整数，a是整数，如果用n除a,得商为q,余数为r,即 a =qn+r,0≤r<n,q= 其中lx表示小于或等于x的最大整数。定义r为a mod n,记为=a modn。如果两个整数a和b满足 a mod n=b mod n 则称a和b模n同余，记作=b mod n。 ●Example ■设a=42,n=8。由于42=5×8+2，则2三42m0d8
同余 同余定义 设n是一正整数，a是整数，如果用n除a，得商为q，余数为r，即 𝒂 = 𝒒𝒏 + 𝒓，0 ≤ 𝒓 < 𝒏，𝒒 = 𝒂 𝒏 其中 𝒙 表示小于或等于x的最大整数。定义r为a mod n，记为r≡a mod n。如果两个整数a和b满足 𝒂 𝐦𝐨𝐝 𝒏 = 𝒃 𝐦𝐨𝐝 𝒏 则称a和b模n同余，记作a≡b mod n。 Example 设a=42，n=8。由于42=5×8+2，则2≡ 42 mod 8
同余 ●同余性质 ■如果n(a-b),则=b mod n。 m如果a mod n=b mod n,则≡b mod n。 ■=a mod n。 m如果三b mod n,则b=a mod n。 ■如果=b mod n,b=c mod n,则a∈c mod n。 ■如果=b mod n,c=d mod n,则(a叶c)=(b+)modn,ac=bd mod n
同余 同余性质 如果n|(a-b)，则a≡b mod n。 如果a mod n=b mod n，则a≡b mod n。 a≡a mod n。 如果a≡b mod n，则b≡a mod n。 如果a≡b mod n, b≡c mod n，则a≡c mod n。 如果a≡b mod n, c≡d mod n，则(a+c)≡(b+d) mod n, ac≡bd mod n
同余 ·同余类（剩余类） ■定义Zn为小于n的所有非负整数集合，即Zn={0,1,2,…,n-1}, 称Zn为模n的同余类集合。 。Zn中的加法和乘法都为模n运算，有如下性质 ■交换律：(+x)modn=(x+w)modn和(wXx)modn=(化Xw)modn ■结合律：[(+x)ty]mod n=w+(c+y川modn和[(wXx)Xy]mod =[wX(cxXy)川modn ■分配律：[wX(c+y)川modn=[(wXx)+(wXy)川modn
同余 同余类(剩余类) 定义𝒁𝒏为小于n的所有非负整数集合，即𝒁𝒏 = {𝟎, 𝟏, 𝟐, … , 𝒏 − 𝟏}， 称𝒁𝒏为模n的同余类集合。 𝒁𝒏中的加法和乘法都为模n运算，有如下性质 交换律:(w+x) mod n=(x+w) mod n和(w×x) mod n=(x×w) mod n 结合律:[(w+x)+y] mod n=[w+(x+y)] mod n和[(w×x)×y] mod n=[w×(x×y)] mod n 分配律:[w×(x+y)] mod n=[(w×x)+(w×y)] mod n
同余 ■有单位元：对加法，存在一个元素0，对wEZn,有(0+w)mod n=w mod n,元素0称为加法单位元；对乘法，存在一个元素1，对 weZn,有(1Xw)modn=w mod n,元素1称为乘法单位元。 ■有逆元：对wE Zn,若存在x∈Zn,(w+x)=0modn,则称x为w的 加法逆元；同理，对乘法(w×x)=1modn,则称x为w的乘法逆元
同余 有单位元：对加法，存在一个元素0，对∀w∈ 𝒁𝒏，有(0+w) mod n=w mod n，元素0称为加法单位元；对乘法，存在一个元素1，对 ∀w∈ 𝒁𝒏，有(1×w) mod n=w mod n，元素1称为乘法单位元。 有逆元：对∀w∈ 𝒁𝒏，若存在x ∈ 𝒁𝒏 ，(w+x) =0 mod n，则称x为w的 加法逆元；同理，对乘法(w × x) =1 mod n，则称x为w的乘法逆元