2022年数论基础知识 .pdf

《2022年数论基础知识 .pdf》由会员分享，可在线阅读，更多相关《2022年数论基础知识 .pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数论基础知识.txt丶喜欢的歌，静静的听，喜欢的人，远远的看我笑了当初你不挺傲的吗现在您这是又玩哪出呢？全文: 数论的基本知识本文将简单地介绍有关整数集合Z=,-2,-1,0,1,2,和自然数集合N=0,1,2,的最基本的数论概念。可除性与约数一个整数能被另一个整数整除的概念是数论中的一个中心概念，记号d|a （读作“ d 除 a” ）意味着对某个整数k，有 a = kd。 0 可被每个整数整除。如果a0 且 d|a ，则 |d| ? |a| 。如果 d|a ，则我们也可以说a 是 d 的倍数。如果a 不能被 d 整除，则写作dFa。如果 d|a 并且 d? 0，则我们说d是 a 的约数。注意

2、，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。素数与合数对于某个整数a1，如果它仅有平凡约数1 和 a，则我们称a 为素数 ( 或质数 ) 。素数具有许多特殊性质，在数论中举足轻重。按顺序，下列为一个小素数序列: 2，3，5，6，11，13， 17，19，23，29，31，37，41， 43

3、，47，53，59，,不是素数的整数a1 称为合数。例如，因为有3|39 ，所以 39 是合数。整数1 被称为基数，它既不是质数也不是合数。类似地，整数 0 和所有负整数既不是素数也不是合数。定理 1 素数有无穷个。证明：假设素数只有有限的n 个，从小到大依次排列为p1,p2,.,pn，则 x = (p1p2.pn)+1 显然是不能被p1,p2,.,pn中的任何一个素数整除的，因此x 也是一个素数，这和只有n个素数矛盾，所以素数是无限多的。这个证明的最早来自亚里士多德，非常漂亮， 是反证法的经典应用，这个证明被欧拉称为“直接来自上帝的证明” ，历代的数学家也对其评价很高。除法定理，余数和同模已

4、知一个整数n，所有整数都可以分划为是n 的倍数的整数与不是n 的倍数的整数。对于不是 n 的倍数的那些整数，我们又可以根据它们除以n 所得的余数来进行分类，数论的大部分理论都是基于上述分划的。下列定理是进行这种分划的基础。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - 定理 2 ( 除法定理 ) 对任意整数a 和任意正整数n，存在唯一的整数q 和 r ，满足 0 r ? n ，并且 a = qn + r 。这个定理是整数的基本定

5、理之一，这里就不给出具体证明了。值 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 -

6、 a) 。如果 a 和 b 对模 n 不相等， 则写作 a T b (mod n)。例如， 61 6 (mod 11) ，同样， -13 22 2 (mod 5) 。根据整数模n 所得的余数可以把整数分成n 个等价类。模n 等价类包含的整数a 为：例如， 37=, ,-11,-4,3,10,17, ，该集合还有其他记法-47和 107 。a bn 。就等同于 a b(mod n) 。所有这样的等价类的集合为: (3) 我们经常见到定义 (4) 如果用 0 表示 0n ，用 1 表示 1n 。等等，每一类均用其最小的非负元素来表示，则上述两个定义 (3) 和(4) 是等价的。但是，我们必须记住相

7、应的等价类。例如，提到Zn 的元素 -1 就是指 n-1n，因为 -1 = n-1 (mod n)。公约数与最大公约数如果 d 是 a 的约数并且也是b 的约数，则d 是 a 与 b 的公约数。例如，24 与 30 的公约数为1,2,3和 6。注意， 1 是任意两个整数的公约数。公约数的一条重要性质为: 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - (5) 更一般地，对任意整数x 和 y，我们有 (6) 同样，如果a|b ，则

8、或者 |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 与

9、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 O， 可知 gcd(a,b)? s。而上面已证明gcd(a,b)? s，所以得到gcd(a,b) = s，我们因此可得到s 是 a 与 b 的最大公约数。推论 4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - -

10、 - - - - 第 3 页，共 6 页 - - - - - - - - - 对任意整数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)

11、=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+yax+pyy)

12、 = 1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - 因为 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 。证明：为了引入

13、矛盾，我们假设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 个素数， p1p2,pr ，且 ei 为非负整数（注意ei 可以为 0） 。证明：（略）例如，数6000 可唯一地分解为24

14、3153。这个定理非常重要，在计算理论中很多重要的定理都可以基于这个定理来证明，因为这个定理实际上给出了Z 和Z*的一一对应关系，换句话说，任何的整数a 都可以用一组整数(e1,e2,er) 来表示， 反之也成立， 其中 a和 (e1,e2,er) 满足定理9 的公式。 比如 6000可以用一组整数(4,1,3)表示，因为6000=243153。从另一个角度看，这也提供了一种大整数的压缩方法，可惜由于这种分解太费时间，所以此压缩方法并不可行:-( 。但是在很多定理的证明中 （尤其是计算理论，形式语言和数理逻辑的定理中），用这种方法可以将一串的整数用唯一的一个整数来表示。比如在一台图灵机中，输入

15、是一串长度不定的整数，经过某种转换，输出另外一串长度不定的整数，我们可以用定理9 将输入和输出都用唯一的一个整数来表示，这样转换的过程就看作是一个简单的从整数集到整数集的函数，对我们从理论上研名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - 究这种转换过程提供了方便。歌德尔不确定性原理的证明中就利用了这种技巧，所以这种编码方式又称为哥德尔编码。再举个简单的例子，如果我们将中文的每个汉字编码，用一个整数表示一个汉字；将英文的26 个

16、字母编码， 用一个整数表示一个字母，现在我们要将一句输入的中文翻译成英文句子输出，输入和输出都可以用一组整数表示，利用上面的哥德尔编码，可以将输入和输出用唯一的一个确定的整数表示，翻译的过程就是做某种函数运算，该函数是 ZZ 的简单整数函数，只要找到了这个函数，就作出了机器翻译机来。事实上， 世界上所有的能够用算法处理的过程都可以利用哥德尔编码转化成简单的整数函数来研究，这就是为什么计算理论中只研究简单的整数函数。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -