5.整数的同余
一个固定的整数d去除整数(Zi)如果余数相同,我们则称这组整数Zi是模d同余的,例如,2,7,12,17,22,⋯,-3,-8,-13,-18,⋯都是模5同余的。如果整数a、b模d同余,我们记做:a三b(mod d)
在日常生活中,同余的概念是经常出现的,例如,一个钟的指针表示的小时是模12同余的;一个汽车的里程表,它给出的行程总里数是模10𠆢5同余的。整数的同余具有如下等价性:
a三b(mod d) <=> 存在某个整数n,使a=b+nd <=>d整除(a-b)
因此我们可以证明整数同余具有如下性质:
1)a三a(mod d);2)如果a三b(mod d),则b三a(mod);3)如果a三b(mod d)、b三c(mod d),则a三c(mod d)
其次,如果a三a’(mod d),b三b’(mOd d)则4)a+b三a’+b’(mod d);5)a-b三a’-b’(mod d);6)ab三a’b’(mod d)
下面我们用一个例子来看(性质6)的用途
因为10=-1+11,所以10三-1(mod 11);10𠆢2三(-1)·(-1)=1(mod11);10𠆢3三一1(mod11);10𠆢4三1(mod11)
这样任何一个(在十进位系统中表示的)整数Z=a。+a1·10+a2·10𠆢2+⋯+an·10𠆢n被11除后的余数与它的数码变替变号求和t=a。-a1+a2-a3+⋯被11除后的余数是一样的,这是因为:
Z-t=a1·11+a2·(10𠆢2-1)+a3·(10𠆢3+1)+a4·(10𠆢4-1)+⋯
而且11,10𠆢2-1,10𠆢3+1,⋯,所有这些数和0都是模11同余,即Z三t(mod11)
例.判断Z=3162819能否被11整除。能。这是因为t=9-1+8-2+6-1+3=22能被11整除
同样的道理10三1(mod3 or9),因此10𠆢n三1(mod3 or9)对于任意的n都成立。故知一个整数Z能被3or9整除,当且仅当它的数码之和S=a。+a1+a2+⋯+an也同样相应地被3or9整除。
(费马定理).在17世纪,近代数论的奠基者费马发现了一个十分重要的定理:如果p是任意一个不能整除整数a的素数,则a𠆢(p-1)三1(modp)证明略。
如,10𠆢6三1(mod7);10𠆢10三1(mod11);5𠆢10三1(mod11);10𠆢2三1(mod3);2𠆢12三1(mod13)