整除 ·欧拉函数 ■设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互素，则𝝋 𝒎𝒏 = 𝝋 𝒎 𝝋 𝒏 ； 如果𝒏 = 𝒑𝟏 𝒂𝟏𝒑𝟐 𝒂𝟐 ⋯ 𝒑𝒕 𝒂𝒕 ，其中，p1<p2<…<pt都是素数， ai>0(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的乘法逆元