网站首页 (Homepage) 欢   迎   访   问  谢  国  芳 (Roy  Xie) 的  个  人  主  页
Welcome to Roy Xie's Homepage
返回 (Return)

 

从整数的世界到余数的世界(1)

—— A First Exploration into the Wonderful World of Numbers

 谢国芳(Roy Xie)                   Email:  roixie@163.com   

章节目录

1. 导言——整数集合 Z 中的算术回顾

2. 模 n 的余数集合 Zn 中的算术

  2.1 Zn 中的加法和乘法——“模 n 加法”和“模 n 乘法”

  2.2 Zn 中的方幂运算——“模 n 方幂”

 

1.导言——整数集合 Z 中的算术回顾

毕达哥拉斯(Pythagoras)说,“万物皆数”,不知然否?感觉有点夸大(学者都本能地倾向于夸大自家学科的作用,古往今来皆如此),但在数学中,我们却可以千真万确、不折不扣地说,“万物皆整数”。数学中的一切,归根结底,都是从整数(再进一步穷根究底说是自然数)构造出来的。所以,德国数学家闵可夫斯基(Hermann Minkowski)说,“所有数学的起源都是整数。”被誉为“数学王子”(更确切地说应该是“数学之王”吧)的高斯(Friedrich Gauss)更有一句几乎人人皆知的名言,“数学是科学的皇后,而数论(即关于整数的学问)是数学的皇后。”诚哉斯言!(但又有多少人真正理解和认同高斯的这句话呢!)

整数是数学中最基础最本原最“初等”的东西,几乎人人都懂得整数和整数的算术——加减乘除,这是我们在小学时就学会了的,现在,就让我们来简单地重温一下(我们将用一种比小学数学更高一点、更抽象一点的眼光)。  

在加减乘除这四种运算中,最基本的是加法,而所有加法最终都可以归结为“加1运算”:

......

一般地有

我们可以说 1 是全体整数的“(加法)生成元”[1](《道德经》云,“一生二,二生三,三生万物,……”,意相近也。)

有了加法,我们就可以定义减法:给定两个整数a, b,若存在另一个整数c,使得 a = b + c,我们就说 c 是 a 减 b 的差(difference)[2],记作

a - b = c 

乘法也可以从加法构造出来[3],因为

有了乘法,我们还可以定义方幂运算:

最后让我们来看除法(这稍微麻烦一点)。

给定两个整数a, b,若存在另一个整数q,使得 a = b×q(注意到此为止和我们上面定义减法的方法几乎一模一样[4],我们就说 a 能被 b 整除(divisible),并称 q 为 a 被 b 除的商(quotient),记作

a ÷ b = q 

除法运算在整数范围内是“不完善的”、“残缺”的(为了使它完善,就诞生了分数或者说有理数),因为并不是每个整数都能被另一个整数整除,在除不尽的情况下就会有一个余数,例如 27 被 5 除的余数是 2。

注意余数是一个小于除数的正整数(我们假定除数是正整数),而且它是唯一确定的,设 a 被 n 除的商(quotient)为 q, 余数(remainder)为 r, 用数学等式表示,我们有

a = qn + r      ( 0 ≤ r < n )

如果两个数 a, b 被 n 除的余数相同,我们就说这两个数关于模(modulus)n“同余”(congruent),用下面的记号表示:

a ≡ b     ( mod n )

例如,27 和 12 被 5 除的余数都是 2,所以它们对模 5 同余,即

27 ≡ 12     ( mod 5 )

显然,如果 a, b 对模 n 同余,那么它们的差 a – b 能被 n 整除,反之亦然。

特别地,“a 能被 n 整除” 等价于

a ≡ 0     (mod n)   

同余“≡”这个记号最早是高斯引入的,在他的不朽名著《算术研究》(Disquisitiones Arithmeticae )的开篇第一段他就开宗明义地引入了这个记号,一方面显示和一般的等号“=”的区别,同时又达到表达的绝对清晰和简洁。在数学中,引入一个表面看上去很简单的概念(notion)或者记号(notation)常常会有意想不到的巨大威力,同余记号就是一个好例。

同余记号“≡”的引入大大方便了处理关于整除和余数的问题,因为在很多方面,同余关系“≡”几乎和普通的等号“=”完全一样,正如两个相等的量可以互相替换一样,两个同余的数也可以互相替换(当然我们总是用小的那个数替换大的)

作为练习,试证明同余的下列基本性质。

同余(congruence)的基本性质

a ≡ b,  c ≡ d  ( mod n ),则

(1)       a + c  ≡  b + d         ( mod n )

(2)       ac  ≡  bd                  ( mod n )

(3)       a x  ≡  b x                 ( mod n ) 

           



 

Proof1

 

例1求 2011 × 2012 除 6 的余数

∵   2011 ≡ 1,    2012 ≡ 2   ( mod 6 )             // 注意 2010 能被 6 整除 [5]

∴   2011 × 2012 ≡ 1 × 2  ≡ 2    ( mod 6 )

    即2011 × 2012 除 6 的余数是 2(你可以笨算出来验证)

例2求 20112012 除 6 的余数

∵   2011 ≡ 1   ( mod 6 )           ∴   2011 2012   ≡ 12012   ≡ 1    ( mod 6 )

    即 20112012 除 6 的余数是 1(这次你怕是不能笨算出来验证了)

     

让我们用标准的数学符号 Z 表示全体整数的集合(Z 源自德语 Zahl(“数,数字”) 的首字母),用 Zn 表示以 n 为模的全体余数的集合,即集合{0, 1, 2, 3, …, n-1}。[6]

现在请思考这样一个问题,在集合 Zn 中,是不是也能像在整数集合 Z 上一样定义某种算术(如加法和乘法)呢?

设想有一个蒙昧的原始部落,他们只能从零数到 N(比如说10),大于 N 的数对他们来说是无法想象的(或者说没有意义的),那么,在这样一个有限的数字世界里,是否有着和我们的(无限的)整数世界中的算术平行的算术呢?如果有,它们又遵循怎样的法则呢?

接下来,我们就要从整数的世界走进这个“余数的世界”,去看一看,那里的算术又有着怎样异样的风景!

可以提前向诸位透露,这将会是一个充满发现的旅程,对“余数世界中的算术”的探索将揭示很多隐藏在整数世界内部的奥秘,一路上你会有一连串意想不到的收获,比如说,你将亲自独立地发现初等数论中很多著名的定理,像算术基本定理(the Fundamental Theorem of Arithmetic)又称素因子唯一分解定理(the Unique-Prime-Factorization Theorem),费马小定理(Fermat's Little Theorem)和欧拉定理(Euler's Theorem),它们一个个都会自动地自然而然地“蹦出来”,就像串在一条线上的一颗颗美丽的珍珠(而不是散落在角落里,只有凭极好的运气(英文所谓的serendipity才能发现)。

 

 

 

推导过程1

 注 解

[注1] 这实际上是一个群论中的术语(全体整数在加法运算下构成一个阿贝尔群)。

[注3] 注意虽然整环 Z 中的乘法可以从加法构造出来,但在其他环例如多项式环中的乘法则并不能从加法构造出来,它们是完全独立的。

[注4] 实际上这是构造逆运算的一般方法(减法和除法分别是加法和乘法的逆运算)。

[注5] 2010是偶数,故能被2整除,且其各位数字之和等于3,故又能被3整除(若一个数字的各位数字之和是3的倍数,则它能被3整除,这是判断一个数能不能被3整除的小诀窍,想必大家都知道。不知道的可以作为练习自己证明这一点,证明提示:10 1 (mod 3)),所以它能被 2 × 3 = 6 整除。

[注6] 现在只当它是一个集合,以后我们会明白它实际上是一个环(ring)。