Articles

什么样的数字能被9整除

记得小学学奥数课数学的时候,老师告诉大家如何一眼就能看出来一个整数能否被2、3、4、5、8、9整除。

  • 能被2整除的数字都是偶数,以0、2、4、6、8结尾,这条规则是最容易理解的。
  • 能被4整除的数字也比较容易看出来,因为100能被4整除,所以看一个数字能否被4整除,只要看后2位能否被4整除就可以了。
  • 能被5整除的数字最后1位不是0就是5,这个也好记。
  • 能被8整除的数字与能被4整除的数字规则差不多,因为1000能被8整除,所以看一个数字能否被8整除,只要看后3位能否被8整除就可以了。

而能被3、9整除的规则则有点让人难以理解,要看一个整数能否被3、9整除,只要把这个整数每一位的数字加起来,看看否能被3、9整除就可以了。例如51能被3整除,因为5+1=6,6能被3整除。117能被9整除,因为1+1+7=9。可是大家知道为什么这条规则成立吗?

其实这是数论的一部分,除了奥林匹克数学外,小学、初中、高中的课本里基本没有讲到任何数论的内容,甚至连大学数学专业都不一定会学数论。但这一理论实际上并不复杂,有兴趣的同学可以跟我一起学习一下。

同余

首先我们介绍一个概念,叫做同余。我第一次听说同余是在小学6年纪的时候,这一概念很容易理解。举个例子,10除以9等于1余1,1除以9等于0余1。所以,我们说10与1关于9同余。我们可以用如下关系式表示:

$$ 10 \equiv 1\pmod{9} $$

定义:如果a和b都是整数,并且他们除以整数n有着相同的余数,我们就称a和b对于n同余(congruent mod n),记做:

$$ a\equiv b\pmod{n} $$

同余类

我们把所有除以整数n,并且有着相同余数a的整数归为一类,叫做同余类(congruence class)。可以用以下集合表示:

$$ \{nk+a : k \in\mathbb{Z}\} $$

我们也可将这一集合记为\( n\mathbb{Z}+a \),例如:

$$ \begin{aligned} 2\mathbb{Z} & = {偶数}, \\ 2\mathbb{Z}+1 & = {奇数}. \\ \end{aligned} $$

关于同余的概念,我们已经掌握的差不多啦,下面我们再看看同余类之间的运算。

同余类的运算

我们思考这样一个问题,如果从\( n\mathbb{Z}+a \)中取一个元素,然后再从\( n\mathbb{Z}+b \)中取一个元素,两个元素相加之后得到的整数会落在哪个同余类中呢?我们不妨假设这两个元素分别是nk+a和nl+b,那么他们的和就是n(k+l)+(a+b),这个整数属于\( n\mathbb{Z}+(a+b) \)。这样,我们就可以定义同余类的加法了。类似的,我们也可以定义同余类的减法和乘法:

$$ \begin{aligned} (n\mathbb{Z}+a)+(n\mathbb{Z}+b) & = n\mathbb{Z}+(a+b), \\ (n\mathbb{Z}+a)-(n\mathbb{Z}+b) & = n\mathbb{Z}+(a-b), \\ (n\mathbb{Z}+a)(n\mathbb{Z}+b) & = n\mathbb{Z}+ab. \end{aligned} $$

有了同余类的运算,我们再回过头来看看同余等式间的运算:

$$ \begin{aligned} a_1\equiv a_2\pmod{n}, \\ b_1\equiv b_2\pmod{n}. \\ \end{aligned} $$

第一个式子告诉我们a1和a2属于同一个同余类\( n\mathbb{Z}+a \),第二个式子告诉我们b1和b2属于同一个同余类\( n\mathbb{Z}+b \)。根据上面我们对同余类运算的推导,我们知道a1+b1和a2+b2都属于\( n\mathbb{Z}+(a+b) \),他们同余。同样,对于减法和乘法也成立。于是我们得到了下面这些同余的运算法则:

$$ \begin{aligned} a_1+b_1 & \equiv a_2+b_2 & \pmod{n}, \\ a_1-b_1 & \equiv a_2-b_2 & \pmod{n}, \\ a_1b_1 & \equiv a_2b_2 & \pmod{n}. \end{aligned} $$

弃九法(Casting out nines)

我们知道:

$$ 10 \equiv 1 \pmod{9} $$

因此,我们可以很容易的推出以下同余等式:

$$ \begin{aligned} 10^2 & \equiv 1^2 \equiv 1 \pmod{9}, \\ 10^3 & \equiv 1^3 \equiv 1 \pmod{9}, \\ 10^i & \equiv 1^i \equiv 1 \pmod{9}. \end{aligned} $$

在最后一个等式两边同时乘上ai,我们可以得到:

$$ a_i10^i \equiv a_i \pmod{9} $$

对于上面的等式,我们取i = 0...k,并且将这k+1个等式相加,最后我们得到:

$$ a_k10^k+...+a_110+a_0 \equiv a_k+...+a_1+a_0 \pmod{9} $$

如果\( a_0, a_1, ..., a_k \)都是0和9间的数字,那么,等式左边表示一个k+1位的数字,右边表示这个数字的每一位相加,他们是同余的。也就是说,如果等式左边能被9整除,那等号右边也能被9整除。

同样的道理,我们也可以证明,如果一个整数每一位数字相加能被3整除,那么这个数字就能被3整除。