北京四中“矩阵变换·数论”选修课同余讲义

　　此资源为用户分享，在本站免费下载，只限于您用于个人教学研究。

　　约2550字。
     第二讲    同余及数论四大定理
　　一、同余符号
　　【定义】 设ｍ是大于1的正整数,a,b是整数,如果m|(a-b),则称a与b关于模m同余,记作a≡b(mod m),读作a同余b模m。或读作a与b关于模m同余。
　　比如 26 ≡ 14 (mod 12)
　　基本性质：
　　(1) 若a≡0(mod m),则m|a
　　(2) a≡b(mod m)等价于a与b分别用m去除,余数相同.
　　证明：
　　充分性:设a=mq1+r1  b=mq2+r2  0≤r1,r2＜m
　　∵a≡b(mod m),∴m|(a-b),a-b=m(q1-q2)+(r1-r2)
　　则有m|(r1-r2)
　　∵0≤r1,r2＜m,∴0≤|r1-r2|＜m
　　即r1-r2=0,∴r1=r2
　　必要性:设a,b用m去除余数为r,即a=mq1+r,b=mq2+r
　　a-b=m(q1-q2) ∴m|(a-b)
　　二、性质
　　1 反身性 a ≡ a (mod m)
　　2 对称性 若a ≡ b(mod m) 则b ≡ a (mod m)
　　3 传递性 如果a ≡ b (mod m)，b ≡ c (mod m) 那么a ≡ c (mod m)
　　4 同余式相加  如果a ≡ b (mod m)，c ≡ d (mod m) 那么a±c ≡ b±d (mod m)
　　【证明】   ∵a≡b(mod m),∴m|(a-b) 同理 m|(c-d)
　　∴m|[(a-b)±(c-d)] ∴m|[(a±c)-(b±d)]
　　∴a ± c ≡ b ± d (mod m) 
　　5 同余式相乘  如果a ≡ b (mod m)，c ≡ d (mod m) 那么ac ≡ bd (mod m)
　　【证明】                                                           
　　
　　∴a * c ≡ b * d (mod m)
　　6 除法                                                              
　　特别地 若               ， 则                           
　　7 乘方 如果a ≡ b (mod m)，那么an ≡ bn (mod m)
　　8 若a ≡ b (mod m)，n|m,则 a ≡ b (mod n)
　　9 若a ≡ b (mod mi） i=1,2...n 则 a ≡ b (mod [m1,m2,…mn]) 其中[m1,m2,…mn]表示m1,m2,...mn 的最小公倍数 
　　特别地 若m1,m2,...mn 两两互素，则有a ≡ b (mod m1m2…mn)
　　三、数论四大定理
　　1 欧拉定理
　　设a,m∈N,(a,m)=1,则aφ(m)≡1(mod m)
　　(注1: φ(m)为欧拉函数，见补充材料)