整除

在小学,我们学过这样的除法:

其中, $a$ 为被除数, $b$ 为除数, $q$ 为商,$r$ 为余数.

我们可以将它改写成一个新的形式,即带余数除法

特别地,当 $r = 0$ 时,我们称 $a$ 能被 $b$ 整除(或 $b$ 能整除 $a$ , $a$ 为 $b$ 的倍数),记作 $b \mid a$. 否则称 $a$ 不能被 $b$ 整除,记作 $b \nmid a$.

整除的性质

1.

一般地,我们只讨论正整数之间的整除关系.

2.

这表明整除具有传递性.

3.

模运算

让我们回到上文的 $(1)$ 式来,如果我们只需要得到 $r$ 的结果,可以定义如下运算,即模运算:

模运算的另一种计算式为($\lfloor\rfloor$ 代表向下取整):

在大部分编程语言中,模运算符号为 %.

模运算的性质

在 OI 的部分题目中,会遇到结果非常大的情况,这时会要求答题者在答案中对一个较大的素数进行取模.
学习模运算相关性质后,你将掌握对这类情况的处理方法.

1.

证明如下:

设 $\space u = aq_1 + r_1, v = bq_2 + r _2$ .
则 $\space (a + b) \bmod m = (r_1+r_2) \bmod m$ ,
$\space \space \space \space \space a \bmod m = r_1, b \bmod m = r_2$ .
所以 $((a \bmod m) + (b \bmod m)) \bmod m = (r_1 + r_2) \bmod m = (a+b) \bmod m$ .

2.

证明过程与 $1.$ 类似.

3.

证明过程与 $1.$ 类似.

同余

如果两个整数 $a$, $b$ 存在下列关系:

则称 $a$, $b$ 对模 $m$ 同余,记作 $ a \equiv b \pmod{m} $.

同余的性质

1.

$ a \equiv b \pmod{m} $ 的充要条件是 $m \mid a-b$.

证明如下:

充分性
不妨设 $a = mp + r_1$, $b = mq + r_2$ .
则 $ a - b = m(p - q) + r_1 - r_2$ .
由 $ m \mid a - b $,
得 $ a - b = mv $
所以 $v = p - q, \space r_1 - r_2 = 0$.
所以 $r_1 = r_2$.
由同余定义得,$ a \equiv b \pmod{m} $ .

必要性
根据同余定义,不妨设 $ a = mp + r, \space b = mq + r$.
则 $ a - b = m(p - q) $.
显然,$ m \mid a - b $.

参考文献

[1] 冯志刚. 数学奥林匹克小丛书. 初中卷. 整除、同余与不定方程. —2版 [M]. 上海: 华东师范大学出版社,2011.12


本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!