约2550字。
第二讲 同余及数论四大定理
一、同余符号
【定义】 设m是大于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)为欧拉函数,见补充材料)
资源评论
共有 0位用户发表了评论 查看完整内容我要评价此资源