整数同余的性质与证明研
整数同余的性质与证明研究
(纯色禁忌,书)
摘 要:整数同余在研究数论的过程中占有很重要的地位,本文简单阐述了整数同余的概念,并对整数同余的性质进行了简单说明与证明研究。通过整数同余的性质与证明的研究,本文给出了整数同余的定义、性质及其证明。整数同余的性质包括反身性、对称性、传递性,从这三个性质还可延伸出一些其他的性质,从这些性质中,我们可以来对整数同余有功多的了解,从而在解决实际问题时可使问题简化 。 关键词:整数同余,性质证明,剩余类
1、引言
同余是数论中的基本概念,日常生活中就常常遇到,例如,1984年元旦是星期日,由于1984年共有366天,而366=7⨯25+2,所以,1985年元旦应是星期二,这里我们只关心余数。用一个固定的正整数去除所有的整数,把余数相同的归在一类,余数不相同的不在同一类,进而讨论分类整数的性质。
本文以m 为模,其中m 为正整数。
2、 整数同余的概念
定义:给定一个正整数m ,把它叫做模。如果用m 去除任意两个整数a 与b 所得的余数相同,我们就说a ,b 对模m 同余,记作a ≡b (modm )。如果余数不同,我们就说a ,b 对模m 不同余,记作a ≠b (modm )。
上述定义也可以叙述为:若a -b ,则叫a 同余b 模m ,记为a ≡b (modm )。自然,若m不整除a-b ,则a 不恒等于b (modm ),例如
15≡1(mod 7)
10) 43≡-7(mod 5≠2(mod 4) 13≠1(mod 5)
3、整数同余的性质及其证明
性质1(反身性)a ≡a (modm ), 证明:a ≡a (modm )显然成立。
性质2(对称性)若a ≡b (modm ),则b ≡a (modm )。
证明:由条件a ≡b (modm ),设a =qm +t ,b =pm +t ,显然,a ≡b (modm ), b≡a (modm )成立。 证完。
性质3(传递性)若a ≡b (modm ),b ≡c (modm ),则a ≡c (modm )。 证明:由
a ≡b (modm )和b ≡c (modm )可知a -b ,b -c ,从而(a -b )+(b -c )=(a -c ), 因此a ≡c (modm )。 证完
定理1 整数a ,b 对模m 同余的充要条件是m 整除a-b ,即a =b +mt ,t 是整数。 证明:设a =mq 1+r 1,b =mq 2+r 2,0≦r 1﹤m ,0≦r 2﹤m ,若a ≡b (modm ),则,r =r 2,因此a -b =m (q 1-q 2)。反之若a -b ,则m (q 1-q 2)+(r 1+r 2)m ,因此
r 1-r 2,但r 1-r 2的绝对值小于m ,故r 1=r 2. 证完。
由定理1及整除的性质可以很容易得到下列与相等类似的性质: 性质4
(ⅰ)a 1≡b 1(modm ),a 2≡b 2(modm ),则a 1+a 2≡b 1+b 2(modm ) (ⅱ)若a+b≡c (modm ),则a ≡c-b (modm )。
证明:由定理1,a1=b1+mt1,a2=b2+mt2,因此a1+a2=b1+b2+m(t1+t2),即得(ⅰ) 由(ⅰ),c-b ≡c+(-b )≡(a +b )+(-b )≡a (modm ),证完。
性质5 若a 1≡b 1(modm ),a 2≡b 2(modm ),则a 1a 2≡b 1b 2(modm )特别的若a ≡b (modm ),则ak ≡bk (modm )
证明:由定理1,a 1=b 1+mt 1,a 2=b 2+mt 2,a 1a 2=b 1b 2+m (b 1t 2+b 2t 1+mt 1t 2), 故
a 1a 2≡b 1b 2(modm ),证完。
性质4与性质5也可叙述为:
如果a ≡b (modm ),x ≡y (modm ),则: (1)a ±x ≡b ±y (modm ); (2)ax ≡by (modm ).
通常复数的等式有消去律,即若a ,b ,c 为复数,c ≠0,则ab =bc 可得出a =b 。下面引理表明,对于同余式也有类似性质,但是条件c ≠0要改成引理1
(c ,m )=1。
⎛m ⎫
⎪(c, m )=1, 则由ac =bu (mod m ),得到设ac ≡bc (modm ),则a ≡b mod ⎪。特别的,若c ,m ⎝⎭ a ≡b (mod m )。
证明:由引理条件可知m -bc =(a -c )c ,于是
m
a -b )c 。则由于
c ,m c ,m ⎛m ⎛c ⎫m m ⎫
即 ⎪ ⎪)=1,因此a -b ,a ≡b mod c ,m c ,m ⎪ ⎪。证完 c ,m c ,m ⎝⎭⎝⎭
引理2 (1)若d m ,a ≡b (modm ),则a ≡b (mod d )。
(2)若a ≡b (mod m ), 则(a , m )=(b , m )。
(3)a ≡b (mod m i )(1≤i ≤r )⇐⇒a ≡b (mod [m 1, m 2, ⋯⋯m r ]). 证明:(1)是显然的。(2):由条件知,存在整数x 使得a =b +mx , 于是
(a , m )=(b +mx , m )=(b , m ).
(3)由(1)知“⇐”是成立的。另一方面,如果a ≡b (mod m i )(1≤i ≤r ), 则
m i
a -b (1≤i ≤r ), 即a-b 是m 1, m 2, ⋯⋯m r 的公倍数,从而a-b 是[m 1, m 2⋯⋯m r ]的倍数,
即a ≡b (mod [m 1⋯⋯m r ])。 证完
谈到整数同余,我想在这提一下剩余类
设m 是一个固定的正整数,利用带余除法,每个整数均模m 同余于0,1,„,m-1当中的一个。由于0,1,„m-1彼此模m 不同余,所以每个整数也只能同余于他们当中的一个。对于整数i ,考虑m 同余于i 的整数所构成的集合
-
i ={n ∈Z n ≡i (mod m )},
那么上面是说:0, 1⋯⋯m -1是彼此不想交的m 个集合,并且他们的并集就是Z 。 我们把每个集合i 叫做模m 的一个剩余类,于是,模m 共有m 个剩余类。同一个剩余类中任意两个整数是模m 同余的,不同的剩余类中两个整数是模m 不同余的。
关于剩余类我们暂且讨论到这一点。下面我们给出定理2,由定理2,我们还可以引出其他的性质。
定理
2 若A α1⋯^2≡B α1⋯^2(mod m ), x i ≡y i (mod m ), i =1, 2, ⋯⋯k , 则:
αk
x α⋯x k ≡
A α∑αα
1⋯⋯2
1⋯α21
B α∑αα
1⋯2
1⋯⋯αk
α1βk
(mod m )。特别的,若:y 1⋯y k
a i ≡b i (mod m ), i =0, 1, ⋯⋯,n , 则
a n x n +a n -1x n -1+⋯⋯+a 0≡b n x n +b n -1x n -1+⋯⋯+b o (mod m )。
性质6 若a ≡b (mod m ), 且a =a 1d , b =b 1d , (d , m )=1, 故a 1-b 1,即:
a 1≡b 1(mod m )。
证明:由定理1,m a -b ,但a -b =d (a 1-b 1), (d , m )=1,故a 1-b 1,a 1≡b 1(mod m )。
证完
性质7 (1)若a ≡b (modm ), k >0, 则ak =bk (modmk ) 。 (2)若a ≡b (modm ), d 是a , b 及m 的任一正公因数,则
a b ⎛m ⎫
≡ mod ⎪. d d ⎝d ⎭
证明:(1)由a ≡b (modm ) ,则存在一个整数t ,使mt =a -b (*),在(*)是两边同时乘上k (k ﹥0)得:mtk =ak -bk ,故ak =bk (mod mk )。
(2)由(1)可证(2)成立。 证完
性质8 若a ≡b (modm i ), i =1, 2⋯⋯k , 则 a ≡b (mod[m 1, m 2, ⋯⋯m k ])
。
证明 :由定理1,m a -b , i =1, 2, ⋯,k ,则m 的最小公倍数整除a-b ,故有:
[m 1, m 2, ⋯⋯m k ]) a ≡b (mod
证完
性质9 若a ≡b (modm ), d m , d >0, 则。a ≡b (modd )
证明:由a ≡b (modm ), d m , d >0, 可得, m整除a-b ,又d 整除m ,则,d 整除a-b ,故
a ≡b (modd ) 证完
性质10 若a ≡b (modm ), 则(a , m ) =(b , m ) , 因而若d 能整除m ,及a ,b 二数之一,则d 必能整除a ,b 中的另一个。
证明:由定理1,a ≡b (modm ) ⇒mt =a -b ,(其中,t 是整数),故a =mt +b ,则a ,m 与m ,b 有相同的公因数,因而(a , m ) =(b , m ) . 证完。
关于整数同余的性质及其证明,到此我们讨论研究完毕。
参考文献
李复中。初等数论选讲,第二章第一节. 东北,东北师范大学出版社。1991 年6月,76—77。
冯克勤,余红兵。初等数论,第二章第一节,合肥,中国科学技术大学出版社,1995年10月,16—17。
闵嗣鹤,严士健。初等数论,第三版,第三章,第一节。北京,高等教育出版社,2003年12月,48—50。
数学与应用数学专业2009级
《初等数论》课程
整数同余的性质与证明研究
小组成员:xxx ,xxx
2011年6月