2017-11-14

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)