登录
2017-03-26 10:15:20

同余 免费编辑 添加义项名

B 添加义项
?
义项指多义词的不同概念,如李娜的义项:网球运动员、歌手等;非诚勿扰的义项:冯小刚执导电影、江苏卫视交友节目等。 查看详细规范>>
穿剂宗便员他厂件属类别 :
词汇
词汇
编辑分类

数论中的重要概念。给定一个正整数m,如果二整数α、b)满足m│α-b)(α-b)被m整除),就称整数α、b)对模m同余,记作α≡b)(mod m)。对模m同余是整数的一个等价关系。

基本信息

  • 中文名

    同余

  • 外文名

    Modular arithmetic

  • 意思

    两个整数除以同一个整数,若得相同余数,则二整数同余

  • 拼音

    tongyu

折叠 编辑本久激住 基本简介

数学上,两个整数除以同一个整数,若得相同余数,则二整数同余(英文:Modular arithmetic;德文:Kongruenz)。同余理论常被用于苗序数论中。最先引用同来自余的概念与符号者为德国数学家高斯。

同余理论是初等数论的重要组成部分,是研360百科究整数问题的重要工具之一,利用同余来论证某些整除性的问题是很简便的.同余是数学竞赛的重要组成部分.

折叠 编辑本段 同余符号

数a,b,若它们除以整数m所得的余数相等,则称a与b对于模m同余或a同余于b模m同余同余

记作a ≡ b (m取木始od m)

读作a同余于b模m,或读作a与b关于模m同余。

比如 26 ≡ 2 (mod 12)

【定义】设m是大于1的正整数,a,b是整数,如果m|(a-b),则称a与b关于模m同余,记作a≡b(mod m),读作a与b对模m同余.

显然,有如下事实

者万未(1)若a≡0(mod m),则m|a;

(2)a≡b(mo慢今d m)等价于a与b分别用m去除,余数相同.

【证明】 充分性:设a=mq1+r1,b=mq2波造北减+r2,0<=r1,r2<m

∵ m|(a-b),a-b=m(q1-q2)+(r1-r2).

则有m|(r1-r2).

∵0<=r1,r2<m,∴0<=|r把企1-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),

a≡b(mod m).

折叠 编辑本段 ​性质信息

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(mo殖称计万按服轻系d m)

5 同余式相乘 若a ≡ 巴下任通伤期b (mod m),c≡d(mod m),则ac≡bd(mod m)

【证明】上述性质很容易证明,下面仅证明(3).

∵a≡b(mod m)∴m|(a-b) 同理m|(b-c),

∴m|[(a-b)+(b-c)]∴m|(a-c).

故a≡c(mod m).

4 线性运算如果a ≡ b (mod m),c ≡ d (mod m),那么(1)a ± c ≡ b ± d (mod m)侵盐投关我,(2)a * c ≡ b * d (杨去传眼事谓查余看卷mod m)

【证明】(1)∵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)

(2)∵ac-bd=ac-bc+bc-bd=c(a-b)+b(c-d)

又 m随触降|(a-b) , m|(c-d) ∴m|(ac-bd)

∴a * c ≡ b * d (mod m)

5 除法若ac ≡ bc (mod m) c≠0 则 a≡ b (mod m/(c,m)) 其中(c,m)表示c,m的最大公约数

特殊地 (c,m)=1 则a ≡ b (mod m)

6 乘方如果a ≡ b (mod m),那么a^n ≡ b今圆势八法议危微^n (mod m)

7 若a ≡ b (mod m),n|m,则 a ≡ b (mod n)

8 若a ≡ b (mod mi) i=1,2...球张期举亚究法n 则 a ≡ b (mod [m1,m2,...左含汽价情指负村黄世mn]) 其中[m1,m2,...mn]表示m1,m2,...mn的最小公倍数

9 欧拉定理

设a,m∈N,(a,m)=1,则a^(φ(m))≡1(mod m)

(注龙掌领往:φ(m)指模m的简系个数, φ(m)=m-1, 如果m是素数;φ(m=q1^r1 * q2^r2 * ...*qi^ri)=m (1-1/q1)(1-1/q2)...(1-1/qi))

推论: 费马小定理: 若立采概挥p为质数,则a^p ≡ a (mod p) 即a^(p-1) ≡ 1 (mod p)

(但是当p点类序事把杀照显|a时不等价)

10 中国剩余定理

设整数m1,m2,m3,......,mn 两两互素,令m=m1m2m3m4m5...愿赶航mn(mi的连乘)。则对于任意的J在(1,n)整数,下列联立的同余式有解:

{xj≡1(mo操据油负投江画指验王d mj)

{xj≡0(mod m练克们阿显温实数黑委i) i不等于j

令x为从1到najxj的和,则x适合下列联立同余式

x≡aj(mod mj), j=1,2,3,.....,n

另:求自然数a的个位数字,就是求a宗船击露与哪一个一位数对居王环于模10同余。

阅读全文

热点资讯

我的关注