模比较和余数运算

27

1. 除法有余数

你即将乘坐地铁。票价5戈比；入口处的控制是自动的：根据机器的反应，您需要投入五分钱，如果您没有五分钱，则可以在兑换台兑换五分钱。

假设您有一枚 20 戈比的硬币。你能从收银机得到多少镍币？大家都会说4。

好吧，如果你有 19 戈比，没有镍币怎么办？很明显，你只能换到 3 镍币和另外 4 戈比的零钱。我们这样写：$19 = 3 \cdot 5 + 4$。这是一个数字19除以5余数的记录。

现在假设有任意面额的硬币，即1戈比、2戈比、3戈比、4戈比等，需要兑换一枚$a$科比硬币，才能获得最大数量的$b$科比。请问我们如何做到这一点？

很明显，如果教你斥责$b$-科比币：

$b, 2b, 3b$等，

然后最终有一天，在收到几枚 $b$-科比硬币后，您将无法再获得下一枚；他们会给你一些东西

28

$b$-戈比硬币和其他一些剩余的数量，比如$r$戈比。这样的话，$r$肯定会小于$b$（当然也不排除$r = 0$）。

这种交换的结果可以写成如下：

$$a = kb + r, \quad r < b.$$

式中，$a, b$为自然数，即正整数，$k$和$r$为非负整数。

关于余数除法的极限。将整数$a$除以自然数$b$意味着将$a$表示为

$$a = kb + r,$$

其中$k, r$是整数，$b > r \geq 0$。

在这种情况下，数字$k$称为商，$r$是$a$除以$b$的余数。

实际中，除以余数的方式通常是“除以角度”。例如，

$$\frac{175}{14} = \frac{14}{12};$$

$$\frac{28}{7}$$

这里立即有一个余数和一个商：$175 = 12 \cdot 14 + 7$。

请注意，在这个定义中，我们不要求$a$小于$b$，甚至不要求$a$为正。例如，您可以划分

a) 5 × 7: $5 = 0 \cdot 7 + 5 \quad (k = 0, r = 5)$,

b) -13 到 7: $-13 = (-2) \cdot 7 + 1 \quad (k = -2, r = 1)$,

b) -224乘7：$-224 = (-32) \cdot 7 \quad (k = -32, r = 0)$。

在余数为零的情况下，即$a = kb$，表示$a$能被$b$整除。

很明显，如果数字$a$和$b$可以被数字$c$整除，那么$a+b$和$a-b$以及$ka, kb$（k - 自然）可以被$c$整除。

2. 按模块比较整数

通常存在这样的问题，其中主要作用不是由问题陈述中包含的数字本身发挥作用，而是由这些数字除法的余数发挥。

例一. Psesid 从城市$A$ 到城市$B$ 78 小时。他早上10点$A$出发。他$B$几点出发？

请记住一天有 24 小时，将数字 78 除以 24：

$$78 = 3 \cdot 24 + 6$$

这意味着从$A$到$B$需要三天零6小时。因此，他将于16:00到达$B$。

请注意，对于任何整数 $k$，如果从 $A$ 到 $B$ 花费的时间不是 78，而是 54、30 或 126、102，通常为 $24 \cdot k + 6$ 小时，也会获得完全相同的结果。

例二.一位数学老师在课堂上使用以下系统进行测试，他认为这保证了学生之间互助的需要。他给了他们一张连续的纸，上面写着问题的条件（“变体”），根据班上学生的数量改变它们，并告诉他们所有的选项都是不同的。事实上，坐在一起的学生可以解决各种问题。

事实上，老师只准备了7个不同的选项：选项8与选项1重合，9-与2重合，…，14-与7重合，15-与1重合，等等。

29

---

running_head:
folio:

学生们很快就弄清楚了老师的系统，在下一次测试中，坐在班级两端的朋友伊万诺夫和彼得罗夫同意解决同样的问题。坚强的学生伊万诺夫用手势向彼得罗夫展示了他的选项编号，彼得罗夫与坐在他附近的一名学生交换了选项，准确地确定了他应该拥有哪个选项编号，以便收到伊万诺夫的感谢备忘单。

您可能会报告说，彼得罗夫计算出了伊万诺夫和他自己的选项的数字为 7，并且只对这些除法的余数感兴趣：他必须用一个与伊万诺夫选项的余数相同的数字填写选项。选项编号本身并不重要，只有其余部分才重要。

例如，如果 Ivanov 收到选项 10（或 3、或 17），而 Petrov 收到选项 26（或 33、或 40），则将 10 和 26 除以 7：

$$10 = 1 \cdot 7 + 3, \quad 26 = 3 \cdot 7 + 5,$$

彼得罗夫与一名有选择权的学生交换了选择权

$$24 = 3 \cdot 7 + 3.$$

例三.让我们找出数字 $2^{999}$ 到底是哪一位。考虑二的连续幂：

$$2^1 = 2, \quad 2^2 = 4, \quad 2^3 = 8, \quad 2^4 = 16, \quad 2^5 = 32, \quad 2^6 = 64, \quad 2^7 = 128, \quad 2^8 = 256, \dots$$

很容易看出这些数字的最后一位数字在4之后是重复的。

这意味着数字 $2^n$ 的最后一位数字仅取决于 $n$ 除以 4 时得到的余数：

当$n$能被4整除时，即$n = 4k$时，所有$2^n$形式的数都为6，

在 $n = 4k+1$ — » » 2,

在 $n = 4k+2$ — » » 4,

在 $n = 4k+3$ — » » 8.

999 除以 4 余数为 3，因此 $2^{999}$ 为 8。

自从解决了这个例子之后，我们发现我们只需要知道 $n$ 除以 4 后得到的余数，所有数字的可能性被分为四类，由以下形式的数字 $n$ 组成

$$4k, 4k+1, \quad 4k+2 \quad \text{и} \quad 4k+3.$$

在第二个示例（带有测试选项）中，所有选项的可能性被分为 7 类，形式为

$$7k, \quad 7k+1, \quad 7k+2, \dots, \quad 7k+6.$$

一般来说，如果我们对除以某个固定数字 $m$ 时的余数感兴趣，那么所有整数（不仅是正整数！）的集合将被分为 $m$ 类。每类由除以 $m$ 时得到相同余数的数字组成。这些是课程：

0. $a = km,$ 形式的数字 $a$

1. » $a$ » $a = km+1,$

2. » $a$ » $a = km+2,$

… … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … …

30

现在让我们引入以下定义：

定义。如果整数$a$和$b$有可能它们的差可以被自然数$m$整除，那么就说$a$和$b$可以对模$m^*$进行比较）。

让我们比较一下 $a$ 和 $b$ 模 $m$ 的写法：

$$a \equiv b \pmod{m}.$$

显然，当且仅当两个数字除以 $m$ 时得到相同的余数时，它们才可以对 $m$ 取模，即它们属于同一类。

例如，

$$27 \equiv 7 \pmod{10}, \quad 78 \equiv 6 \pmod{24}, \quad 6 \equiv 0 \pmod{3}, \quad 25 \equiv -1 \pmod{13}.$$

事实证明，数字的清晰可比性有助于解决许多问题。

问题1.对于什么自然数$n$来说，$n^2+2$能被3整除，即$n^2+2 \equiv 0 \pmod{3}$？

解决方案。

如果$n \equiv 0 \pmod{3}$，则$n^2+2 \equiv 2 \pmod{3}$，

» $n \equiv 1 \pmod{3}$, » $n^2+2 \equiv 0 \pmod{3}$,

» $n \equiv 2 \pmod{3}$, » $n^2+2 \equiv 0 \pmod{3}$.

所以，$n^2+2 \equiv 0 \pmod{3}$当且仅当$n$不能被3整除。

比较的基本属性让人想起一般平等的属性。可以通过加、减、乘来进行比较：

如果 $a \equiv b \pmod{m}$ 和 $c \equiv d \pmod{m}$，那么

$$a + c \equiv b + d \pmod{m}, \quad a - c \equiv b - d \pmod{m}, \quad ac \equiv bd \pmod{m}.$$

例如，让我们证明比较可以成倍增加。由于$a \equiv b \pmod{m}$和$c \equiv d \pmod{m}$，因此$a-b$和$c-d$可被$m$整除。来自平等

$$ac - bd = ac - ad + ad - bd = a(c-d) + d(a-b)$$

显然$ac-bd$也能被$m$整除，即

$$ac \equiv bd \pmod{m}.$$

作为练习，证明比较可以进行加法和减法。

让$a \equiv b \pmod{m}$。从上述比较性质可以看出，$a^k \equiv b^k \pmod{m}$对于任何自然数$k$（即比较的两边都可以求幂），此外还有$ac \equiv bc \pmod{m}$，其中$c$是任何整数（也就是说，比较的两边都可以乘以任何整数）。

问题 2. 除以 3 后得到的余数是 $(2^2+1)(3^2+1)(4^2+1) \dots (1000^2+1)$？

解决方案。如果每个数字都是 2、3、…，则余数不会改变。 。 。 ，该表达式中的1000，将其替换为除以3的余数。因此，利息数模3等于$(2^2+1)^{333} (3^2+1)^{333} (1^2+1)^{333} \equiv 5^{333} \cdot 10^{333} \cdot 2^{333} \equiv 2^{333} \cdot 1^{333} \cdot 2^{333} \equiv 2^{2 \cdot 333} \equiv 4^{333} \equiv 1^{333} \equiv 1$，即所需的余数为1。

*）“模数”一词（来自拉丁语“模数”-测量）用于数学及其应用的各个领域；它被分配给一些特别重要的数字；例如，与其相关地进行计数或测量。

31

任务 3. 证明每个自然数 $n$ 都可以模 9 与其数字和进行比较。

解决方案。让

$$\overline{a = a_n a_{n-1} \dots a_0},$$

其中$a_0, a_1, \dots, a_n$是数字$a$的数字。我们有

$$a = a_n \cdot 10^n + a_{n-1} \cdot 10^{n-1} + \dots + a_0.$$

现在让我们写下以下估计比较：

$$1 \equiv 1 \pmod{9}, \quad 10 \equiv 1 \pmod{9}, \quad \dots, \quad 10^n \equiv 1 \pmod{9}.$$

将这些比较分别乘以$a_0, a_1, \dots, a_n$并相加，我们得到

$$a_0 + 10 \cdot a_1 + \dots + 10^n a_n = a \equiv (a_0 + a_1 + \dots + a_n) \pmod{9}.$$

顺便说一句，从这里我们立即得到了众所周知的数字能被 9（和 3）整除的符号。

3. 根据本模块的余数算术

给定一个自然数$m$（模）。考虑到所有可能的整数，我们只对它们除以 $m$ 时的余数感兴趣。因此，我们不会区分彼此可比较的模 $m$ 的数字。在这种情况下，我们有“不同”对象的余数 $m$ - 除以 $m$ 的余数：

$$0, 1, 2, 3, \dots, m-1,$$

对于它们，我们可以定义新的“加法”和“乘法”规则：即，如果$r_1$和$r_2$是两个余数，那么“和”$r_1 + r_2$我们将把除以$m$得到$r_1 + r_2$的余数称为“乘积”$r_1 \cdot r_2$，将$r_1 \cdot r_2$除以得到的余数$m$。例如，对于 $m = 10$ 除以 10 时的余数是其十进制的最后一位数字。因此，例如，在余数模 10 的算术中，等式也是成立的

$$7 + 3 = 0, \quad 1 + 2 = 3, \quad 7 + 5 = 2, \quad 7 \cdot 5 = 5, \quad 7 \cdot 6 = 2, \quad 2 \cdot 5 = 0.$$

在模 2 余数的 .ariphmetic 中，只有两个余数：0 和 1，因此这个 .ariphmetic 非常简单：

$$0 + 0 = 0, \quad 1 + 0 = 1, \quad 1 + 1 = 0,$$

$$0 \cdot 0 = 0, \quad 1 \cdot 0 = 0, \quad 1 \cdot 1 = 1.$$

对于 $m = 6$ 我们得到

$$5 + 3 = 2, \quad 4 + 2 = 0, \quad 3 + 3 = 0, \quad 3 \cdot 2 = 0, \quad 3 \cdot 4 = 0$$等

因此，模 $m$ 对应于它自己的算术。为了简洁起见，我们将其称为$m$-ariphmetic*）。

32

作为例子，我们给出 7 算术中的乘法和加法表。

乘法口诀表

| × | 1 | 2 | 3 | 4 | 5 | 6 |
| :— | :— | :— | :— | :— | :— | :— |
| 1 | 1 | 2 | 3 | 4 | 5 | 6 |
| 2 | 2 | 4 | 6 | 1 | 3 | 5 |
| 3 | 3 | 6 | 2 | 5 | 1 | 4 |
| 4 | 4 | 1 | 5 | 2 | 6 | 3 |
| 5 | 5 | 3 | 1 | 6 | 4 | 2 |
| 6 | 6 | 5 | 4 | 3 | 2 | 1 |

加法表

| + | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| :— | :— | :— | :— | :— | :— | :— | :— |
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 1 | 2 | 3 | 4 | 5 | 6 | 0 |
| 2 | 2 | 3 | 4 | 5 | 6 | 0 | 1 |
| 3 | 3 | 4 | 5 | 6 | 0 | 1 | 2 |
| 4 | 4 | 5 | 6 | 0 | 1 | 2 | 3 |
| 5 | 5 | 6 | 0 | 1 | 2 | 3 | 4 |
| 6 | 6 | 0 | 1 | 2 | 3 | 4 | 5 |

这些表是这样的设备：在行和列的交叉点，它们在这些行和列的开头构建余数的乘积（对应 - 总和）。

从比较的性质和对数字的通常作用规则可以清楚地看出，在$m$算术中，满足普通算术的给定规则，也就是说，对于任何余数$a, b, c$，都会有

$$a+b = b+a \text{ — коммутиативность (переместительность) сложения},$$
$$(a+b)+c = a+(b+c) \text{ — ассоциативность (сочетательность) сложения},$$
$$ab = ba \text{ — коммутиативность умножения},$$
$$(ab)c = a(bc) \text{ — сочетательность умножения},$$
$$a(b+c) = ab+ac \text{ — дистрибутивность (распределительность) умножения относительно сложения}.$$

因此，在我们的算术中，例如，以下公式将是正确的：

$$(a+b)^2 = a^2 + 2ab + b^2,$$
$$(a+b)(c+d) = ac + ad + bc + bd.$$

让我们考虑使用 $m$ 算术的几个问题。

任务 4. 求 $2^{1000}$ 除以 7 的余数。

解决方案。我们需要弄清楚 7 算术中的 $2^{1000}$ 等于什么。很容易看出$2^{1000} = (2^3)^{333} \cdot 2 = 1^{333} \cdot 2 = 2$。

任务 5. 找到数字 $7^{7^{1000}}$ 的最后一位数字。

解决方案。我们必须算出这个数字在 10 算术中等于多少。为此，请考虑 10 算术中数字 7 的连续幂：

$$7^1 = 7, 7^2 = 9, 7^3 = 3, 7^4 = 1, 7^5 = 7 \text{ и т. д.}$$

很明显

$$7^{4n} = 1, 7^{4n+1} = 7, 7^{4n+2} = 9, 7^{4n+3} = 3.$$

因此，我们需要找出数字 $7^{1000}$ 除以 4 时的余数。为此，请考虑 4 算术中的 $7^{1000}$。从 $7^{1000} = 3^{1000}$ 开始，我们现在考虑 4 算术中的余数序列：

$$3^1 = 3, 3^2 = 1, 3^3 = 3, 3^4 = 1, 3^5 = 3, \dots,$$

33

$$3^{2n+1} = 3, \quad 3^{2n} = 1.$$

但1000是偶数；表示$7^{1000} = 1$，即$7^{1000} = 4n+1$。因此，在 10 算术中$7^{71000} = 7^{4n+1} = 7^{4n} \cdot 7 = 7$。

答案：数字$7^{71000}$以7结尾。

问题 6. 证明如果 $a^2+b^2$ 能被 3 整除，那么 $a$ 和 $b$ 都能被 3 整除。

解决方案。传递到除以 3 的余数，我们得到 3 算术等式 $a^2+b^2 = 0$。 3 算术中有 3 个余数：0、1、2。

我们有：$1^2 = 1, 2^2 = 1$。很容易看出，对于$a \neq 0$$a^2+b^2 \neq 0$，即从等式$a^2+b^2 = 0$它遵循$a = 0$和$b = 0$。这意味着 $a$ 和 $b$ 可同时被 3 整除。

任务 *)

1. 除法有余数
   1.0。将余数 -297 除以 31，-1005 除以 98。

2. 证明任意自然数$N$的约数个数不超过$2\sqrt{N}$。

3. 求数字相除的余数（$n$ - 自然数）：a) $n$ 除以$(n-1)$ 和$(n-2)$； b) $(n^2+n+1)$、$(n+1)$ 和$(n+2)$； c) $(n^4+1)$ 至 $(n+3)$（$n \geqslant 80$）。

4. 查找 $\frac{n^2+1}{n-1}$ 也是整数的所有整数 $n$。

5. 证明任意三个连续整数的乘积能被6整除。

6. 证明如果$a+b+c$能被6整除，那么$a^3+b^3+c^3$也能被6整除（$a, b, c$是整数）。
   7*。 15个素数组成一个等差数列。证明其差异大于30000。

7. 比较整数模
   8.0。查找所有自然数$n$，其中数字$n^3+n+1$可被3整除。
   9.0。求解比较 $6n+5 \equiv 0$ (mod 7)。

8. 证明以下可被 11 整除的测试：
   $$a = \overline{a_n a_{n-1} \dots a_0} \equiv 0 \pmod{11}$$

然后且仅当
$(-1)^n a_n + (-1)^{n-1} a_{n-1} + \dots + a_n \equiv 0 \pmod{11}$.
11. 利用 $1000 \equiv -1$ (mod 7) 以及 $1000 \equiv 1$ (mod 37)，获得 7 和 37 的整除标准。
12. 证明如果数字 $A$ 和 5$A$ 的位数和相同，则 $A$ 能被 9 整除。
13. 证明方程$15x^2-7y^2=9$无整数解。
14. 证明对于没有整数 $n$ 的数字 $n^2+3n+5$ 能被 11 整除。
15. 证明 $3n+2, 5n \pm 2, 7n+3, 7n-1, 7n-2$ 形式的数字对于任何自然数 $n$ 都不是完全平方数。
3. 给定模数的余数算术
16.0。构建 4 进制、6 进制、8 进制、11 进制和 13 进制算术的加法和乘法表。
17. 用 9 算术构建平方表和立方表。
18. 使用问题 17 中获得的立方表，证明$9n+5$ 和 $9n+4$ 形式的数字不能表示为三个数字的立方之和。
19. 证明在$p$算术中，其中$p$是素数，根据$ab=0$与$a \neq 0$的等式可得出$b=0$。
20. 证明在 $m$ 算术中，任何余数 $a$ 都存在唯一的余数 - $a$，使得 $a+(-a)=0$。由此推断，对于任何 $a$ 和 $b$，方程 $a+x=b$ 在任何 $m$ 算术中都有解。
21. 证明对于$m$算术中的复合$m$，存在余数$a \neq 0$和$b \neq 0$以及$ab=0$。
22. 使用 31 算术，证明 $1^{255}+2^{255}+\dots+30^{255}$ 能被 31 整除。

*) 简单的任务用零标记，最困难的任务用星号标记。