文档介绍：全文:数论的基本知识本文将简单地介绍有关整数集合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=amodn称为除法的余数。我们有n|a当且仅当amodn=O,并且有下式成立:(1)或(2)当我们定义了一个整数除以另一个整数的余数的概念后,就可以很方便地给出表示同余的特殊记法。如果(amodn)=(bmodn),就写作a≡b(modn),并说a和b对模n是相等的。换句话说,当a和b除以n有着相同的余数时,有a≡b(modn)。等价地有,a≡b(modn)当且仅当n|(b-a)。如果a和b对模n不相等,则写作aTb(modn)。例如,61≡6(mod11),同样,-13≡22≡2(mod5)。根据整数模n所得的余数可以把整数分成n个等价类。模n等价类包含的整数a为:例如,[3]7={…,-11,-4,3,10,17,…},该集合还有其他记法[-4]7和[10]7。a∈[b]n。就等同于a≡b(modn)。所有这样的等价类的集合为:(3)我们经常见到定义(