发信人: Lerry (想不开·撞树), 信区: Algorithm
标 题: 数论的基本知识
发信站: 哈工大紫丁香 (2002年03月22日14:36:39 星期五), 站内信件
本文将简单地介绍有关整数集合Z={…,-2,-1,0,1,2,…}和自然数集合N={0,1,2,…}的最
基本的数论概念。
可除性与约数
一个整数能被另一个整数整除的概念是数论中的一个中心概念，记号d|a（读作“d 除a
”）意味着对某个整数k，有 a = kd。0可被每个整数整除。如果a>0且d|a，则|d|≤|a
|。如果d|a，则我们也可以说a是d的倍数。如果a不能被d整除，则写作dFa。
如果d|a并且d≥0，则我们说d是a的约数。注意，d|a当且仅当(-d)|a，因此定义约数为
非负整数不会失去一般性，只要明白a的任何约数的相应负数同样能整除a。一个整数a的
约数最小为1，最大为|a|。例如，24的约数有1，2，3，4，6，8，12和24。
每个整数a都可以被其平凡约数1和a整除。a的非平凡约数也称为a的因子。例如， 20的
因子有2，4，5和10。
素数与合数
对于某个整数a>1，如果它仅有平凡约数1和a，则我们称a为素数(或质数)。素数具有许
多特殊性质，在数论中举足轻重。按顺序，下列为一个小素数序列:
2，3，5，6，11，13，17，19，23，29，31，37，41，43，47，53，59，…
不是素数的整数a>1称为合数。例如，因为有3|39，所以39是合数。整数1被称为基数，
它既不是质数也不是合数。类似地，整数 0和所有负整数既不是素数也不是合数。
定理 1
素数有无穷个。
证明：
假设素数只有有限的n个，从小到大依次排列为p1,p2,...,pn，则 x = (p1·p2·...·
pn)+1 显然是不能被p1,p2,...,pn中的任何一个素数整除的，因此x也是一个素数，这和
只有n个素数矛盾，所以素数是无限多的。
这个证明的最早来自亚里士多德，非常漂亮，是反证法的经典应用，这个证明被欧拉称
为“直接来自上帝的证明”，历代的数学家也对其评价很高。
除法定理，余数和同模
已知一个整数n，所有整数都可以分划为是n的倍数的整数与不是n的倍数的整数。对于不
是n的倍数的那些整数，我们又可以根据它们除以n所得的余数来进行分类，数论的大部
分理论都是基于上述分划的。下列定理是进行这种分划的基础。
定理2 (除法定理)
对任意整数a和任意正整数n，存在唯一的整数q和r，满足0 < r ≤ n，并且a = qn + r
。
这个定理是整数的基本定理之一，这里就不给出具体证明了。
值q=?a/n? 称为除法的商（? x? 表示地板符号floor，即小于等于x的最大整数）。值
r = a mod n 称为除法的余数。我们有n|a 当且仅当 a mod n = O，并且有下式成立：
(1)
或
(2)
当我们定义了一个整数除以另一个整数的余数的概念后，就可以很方便地给出表示同余
的特殊记法。如果 (a mod n)=(b mod n)，就写作 a ≡ b (mod n)，并说a和b对模n是
相等的。换句话说，当a和b除以n有着相同的余数时，有a ≡ b (mod n)。等价地有，a
≡ b (mod n)当且仅当n|(b - a)。如果a和b对模n不相等，则写作a T b (mod n)。例
如， 61≡ 6 (mod 11)，同样，-13≡ 22≡2 (mod 5)。
根据整数模n所得的余数可以把整数分成n个等价类。模n 等价类包含的整数a为：
例如，[3]7={…,-11,-4,3,10,17,…}，该集合还有其他记法[-4]7和[10]7。a ∈[b]n
。就等同于a ≡ b(mod n)。所有这样的等价类的集合为:
(3)
我们经常见到定义
(4)
如果用0表示[0]n，用1表示[1]n。等等，每一类均用其最小的非负元素来表示，则上述
两个定义(3)和(4)是等价的。但是，我们必须记住相应的等价类。例如，提到Zn的元素
-1就是指[n-1]n，因为-1 = n-1 (mod n)。
公约数与最大公约数
如果d是a的约数并且也是b的约数，则d是a与b的公约数。例如，24与30的公约数为1,2,
3和6。注意，1是任意两个整数的公约数。
公约数的一条重要性质为:
(5)
更一般地，对任意整数x和y，我们有
(6)
同样，如果a|b，则或者|a|≤|b|，或者b=O，这说明：
(7)
两个不同时为0的整数a与b的最大公约数表示成gcd(a,b)。例如，gcd(24,30)=6，gcd(5
,7)=1，gcd(0,9)=9。如果a与b不同时为0，则 gcd(a,b)是一个在1与min(|a|,|b|)之间
的整数。我们定义gcd(O,0)=0，这个定义对于使gcd函数的一般性质(如下面的式 (11))
普遍正确是必不可少的。
下列性质就是gcd函数的基本性质：
(8)
(9)
(10)
(11)
(12)
定理 3
如果a和b是不都为0的任意整数，则gcd(a,b)是a与b的线性组合集合{ ax + by : x,y ∈
Z}中的最小正元素。
证明：
设s是a与b的线性组合集中的最小正元素，并且对某个x,y ∈Z，有s = ax + by，设q =
?a/s? ，则式(2)说明
因此，a mod s也是a与b的一种线性组合。但由于a mod s < s，所以我们有a mod s =
O，因为s是满足这样的线性组合的最小正数。因此有s|a，并且类似可推得s|b。因此，
s是a与b的公约数，所以gcd(a，b)≥ s。因为gcd(a，b)能同时被a与b整除并且s是a与b
的一个线性组合，所以由式(6)可知gcd(a,b)| s 。但由gcd(a,b)|s 和s > O，可知 gc
d(a,b)≤s。而上面已证明gcd(a,b)≥s，所以得到gcd(a,b) = s，我们因此可得到s是a
与b的最大公约数。
推论 4
对任意整数a与b，如果d|a并且d|b，则d|gcd(a,b)。
证明：
根据定理3，gcd(a，b)是a与b的一个线性组合，所以从式(6)可推得该推论成立。
推论 5
对所有整数a 和b以及任意非负整数n，gcd(an ,bn)=n gcd(a,b)。
证明：
如果n = 0，该推论显然成立。如果n ≠ 0，则gcd(an,bn)是集合{anx + bny}中的最小
正元素，即为集合{ax + by}中的最小正元素的n倍。
推论 6
对所有正整数n，a和b，如果n|ab并且gcd(a,n)=1，则n|b。
证明：
（略）
互质数
如果两个整数a与b仅有公因数1，即如果gcd(a,b)=1，则a与b称为互质数。例如，8和15
是互质数，因为8的约数为1，2，4，8，而15的约数为1，3，5，15。下列定理说明如果
两个整数中每一个数都与一个整数p互为质数，则它们的积与p与互为质数。
定理 7
对任意整数 a，b和p，如果gcd(a,p)=1且gcd(b,p)=1，则gcd(ab,p)=1。
证明：
由定理3可知，存在整数x，y，x'，y' 满足
ax+py=1
bx'+py'=1
把上面两个等式两边相乘，我们有
ab(xx')+p(ybx'+y'ax+pyy') = 1
因为1是ab与p的一个正线性组合，所以运用定理3就可以证明所需结论。
对于整数n1,n2,…,nk，如果对任何 i≠j 都有gcd(ni,nj)=1，则说整数n1,n2,…,nk两
两互质。
唯一的因子分解
下列结论说明了关于素数的可除性的一个基本但重要的事实。
定理 8
对所有素数p和所有整数a，b，如果p|ab，则pla或者p|b。
证明：
为了引入矛盾，我们假设p|ab，但pFa并且pFb。因此，gcd(a,p)=1 且gcd(b,p)=1，这是
因为p的约数只有1和p。又因为假设了p既不能被a也不能被b整除。据定理7可知，gcd(a
b,p)=1；又由假设p|ab可知gcd(p,ab)=p，于是产生矛盾，丛而证明定理成立。
从定理8可推断出，一个整数分解为素数的因子分解式是唯一的。
定理 9 (唯一质因子分解)
任意的整数a能且仅能写成一种如下积的形式
其中pi为自然数中的第i个素数，p1<p2<…<pr，且ei为非负整数（注意ei可以为0）。
证明：
（略）
例如，数6000可唯一地分解为24·31·53。
这个定理非常重要，在计算理论中很多重要的定理都可以基于这个定理来证明，因为这
个定理实际上给出了Z和Z*的一一对应关系，换句话说，任何的整数a都可以用一组整数
(e1,e2,…,er)来表示，，反之也成立，其中a和(e1,e2,…,er)满足定理9的公式。比如
6000可以用一组整数(4,1,3)表示，因为6000=24·31·53。从另一个角度看，这也提供
了一种大整数的压缩方法，可惜由于这种分解太费时间，所以此压缩方法并不可行:-(。
但是在很多定理的证明中（尤其是计算理论，形式语言和数理逻辑的定理中），用这种
方法可以将一串的整数用唯一的一个整数来表示。比如在一台图灵机中，输入是一串长
度不定的整数，经过某种转换，输出另外一串长度不定的整数，我们可以用定理9将输入
和输出都用唯一的一个整数来表示，这样转换的过程就看作是一个简单的从整数集到整
数集的函数，对我们从理论上研究这种转换过程提供了方便。歌德尔不确定性原理的证
明中就利用了这种技巧，所以这种编码方式又称为哥德尔编码。再举个简单的例子，如
果我们将中文的每个汉字编码，用一个整数表示一个汉字；将英文的26个字母编码，用
一个整数表示一个字母，现在我们要将一句输入的中文翻译成英文句子输出，输入和输
出都可以用一组整数表示，利用上面的哥德尔编码，可以将输入和输出用唯一的一个确
定的整数表示，翻译的过程就是做某种函数运算，该函数是Z→Z的简单整数函数，只要
找到了这个函数，就作出了机器翻译机来。事实上，世界上所有的能够用算法处理的过
程都可以利用哥德尔编码转化成简单的整数函数来研究，这就是为什么计算理论中只研
究简单的整数函数。
--
不在乎天长地久，就怕你从来没有！
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]