同余式
定义：a≡b (mod m) =>a和b关于模m同余
数学式子表示：∃ q,q1,r，a=mq+r,b=mq1+r (0≤r≤m-1)
①a≡a (mod m)
②若a≡b (mod m) ,则b≡a (mod m)(对称性)
③若a≡b (mod m) 且b≡c (mod m),则a≡c (mod m)(传递性)
等价类的集合表示：Z/mz={[k] | 0≤k≤m-1}(对于模数m，共会有m个等价类)
定理1：
a≡ b (mod m) ，当且仅当m|a-b
证明：
①（必要性 a≡ b (mod m)-> m|a-b）
∃ q,q1,r,a=mq+r,b=mq1+r (0≤r≤m-1)
则a-b=m*(q-q1),即m|a-b
②(充分性m|a-b->a≡ b (mod m))
假设a=mq+r, b=mq1+r1 (0≤r≤m-1, 0≤r1≤m-1)
则a-b=m*(q-q1)+(r-r1)
∵m|(a-b),故(r-r1)|m
又∵0≤r≤m-1, 0≤r1≤m-1,故r=r1
即a≡b (mod m),得证
定理2:
若a≡b (mod m),且α≡β (mod m)，则
①ax+αy=bx+βy (mod m)
②aα ≡ bβ (mod m)
③an≡ bn (mod m)
④f(a)≡f(b) (mod m)
证明：
①∵a≡b (mod m),且α≡β (mod m)
故m|a-b, m|α-β
∴m|(a-b)x+(α-β)y
即ax+αy≡bx+βy(mod m)
②aα-bβ=aα-bα-bβ+bα=(a-b)*α+b(α-β)
∵m|a-b, m|α-β
∴m|aα-bβ
即aα≡bβ (mod m)
③∵a≡b (mod m)
∴aa≡bb (mod m)(根据②)
故a3≡b3 (mod m)
…
an≡ bn (mod m)
④令f(x)=Cn(xn)+Cn-1(xn-1)+…C1x+C0*1
Cn(an)≡Cn(b**n) (mod m)
Cn-1(an-1)≡Cn-1(b**n-1) (mod m)
C1a≡C1b (mod m)
C0≡C0 (mod m)
左边、右边相加即得f(a) ≡ f(b) (mod m)
定理3：
若ac≡bc (mod m) 且(m,c)=d，则a≡b (mod m/d)
证明：由同余式可知m|(a-b)*c
故存在k，使得(a-b)c=mk
∵(m,c)=d
∴(a-b)c/d=mk/d
∵c/d,m/d互质
故m/d|(a-b)
即a≡b (mod m/d)
定理4：
a≡b (mod m1)
a≡b (mod m2)
a≡b (mod mn)
则a≡b (mod [m1,m2,m3…,mn])
证明：
∵m1|a-b, m2|a-b,…,mn|a-b
∴(a-b)为m1,m2…,mn的公倍数
故[m1,m2,…,mn] | a-b，所以a≡b (mod [m1,m2,m3…,mn])
Original: https://www.cnblogs.com/jane315/p/13728182.html
Author: jane_315
Title: 数论-同余式
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/583764/
转载文章受原作者版权保护。转载请注明原作者出处！