荔园在线

荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀

[回到开始] [上一篇][下一篇]


发信人: kaman (天外飞仙), 信区: ACMICPC
标  题: 还是数论
发信站: 荔园晨风BBS站 (Fri Jul 23 10:58:12 2004), 站内信件

数论的基本知识
本文将简单地介绍有关整数集合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,7,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,可知 gcd(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(ab,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的简单整数函数,只要找到了
这个函数,就作出了机器翻译机来。事实上,世界上所有的能够用算法处理的过程
都可以利用哥德尔编码转化成简单的整数函数来研究,这就是为什么计算理论中只
研究简单的整数函数。

--
       灬 灬 灬灬 灬灬  灬 灬 ════════════════════╗╮
   ╭╯  灬 灬▂╱   _灬灬ジ  ヾ                                   灬╰╗
   ║ 灬◢◢ "▔ 灬╱          灵台无计逃神矢  风雨如磐暗故园  ▁  灬|"|║
   ║     ◤,  |,╱_ ◣◣      寄意寒星荃不察  我以我血荐轩辕▕心▏  ◣|║
   ║     _,|\▄/ \▌◥                                        ▔ヾ◥◥|║
   ╚═ "\▌| ▔ | | /" ════════════════════════╯

※ 修改:·kaman 於 Jul 23 14:38:02 修改本文·[FROM: 192.168.14.107]
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.14.107]


[回到开始] [上一篇][下一篇]

荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店