竞赛数论基础

数论基础A.1素数与互素A.2同余与模运算A.3欧拉定理A.4几个有用的算法授课内容A.1素数与互素1整除定义1.1设a,b为整数，a≠0.若有一整数q,使得b=aq,则称a是b的因数,b是a的倍数;并称a整除b,记为a|b,可形式地表示为:a|b:=(q)(b=aq)若a不能整除b，记为ałb.若b=aq,而a既非正负b又非正负1,则称a是b的真因数.1整除关于整除，显然有下列定理：定理1.1①对所有a,1|a.②对所有a,a|0.③对所有a,a|a.④若a|b且b|c,则a|c.⑤若a|b,则对任意的c≠0,有ac|bc.⑥若ac|bc且c≠0,则a|b.1整除⑦若a|b且a|c,则对任意的m,n,有a|(bm+cn).⑧若a|b,则b=0或|a|≤|b|,其中|a|是a的绝对值.⑨若a|b,则(-a)|b,a|(-b),(-a)|(-b),|a|||b|.2素数和合数在正整数中,1只能被它本身整除.任何大于1的整数都至少能被1和它本身整除．定义2.1一个大于1且只能被1和它本身整除的整数,称为素数;否则,称为合数.由该定义可知，正整数集合可分三类:素数、合数和1.素数常用p或p1,p2…,来表示.2素数和合数定义2.2若正整数a有一因数b,而b又是素数,则称b为a的素因数．例:12=3×4,其中3是12的素因数,而4则不是.素数有多少？公元前三世纪,古希腊数学家欧几里德Euclid就证明了素数有无穷多个.2素数和合数素数的一些基本结论：素数有无穷多个素数的整除性素数定理算术基本定理：有限分解和唯一分解3最大公因数和最小公倍数定义3.1设al,a2,…,an和d都是正整数,n≥2.若d|ai,1≤i≤n,则称d是al,a2,…,an.的公因数.在公因数中最大的那一个数,称为al,a2,…,an的最大公因数,记为gcd{al,a2,…,an}.(greatestcommondivisor)或者(al,a2,…,an).若gcd(al,a2,…,an)=1,称al,a2,…,an是互素的.3最大公因数和最小公倍数在互素的正整数中,不一定有素数.例如(25,36)=1,但25和36都不是素数而是合数.在个数不少于3个的互素正整数中,不一定是每二个正整数都是互素的.例:(6,10,15)=1,但(6,10)=2,(6,15)=3,(10,15)=5.3最大公因数和最小公倍数最大公因子有下列性质：任何不全为0的两个整数的最大公因子存在且唯一设整数a与b不全为0，则存在整数x和y，使得ax+by=gcd(a,b)。特别地，如果a、b互素，则有ax+by=1若gcd(a,b)=d,则gcd(a|d,b|d)=1若gcd(a,x)=gcd(b,x)=1,那么gcd(ab,x)=1若c|(ab),gcd(b,c)=1,则c|a3最大公因数和最小公倍数定义3.2设a1,a2,…,an和m都是正整数,n≥2.若ai|m,1≤i≤n,则称m是a1,a2,…,an的公倍数.在a1,a2,…,an所有公倍数中最小的那一个,称为a1,a2,…,an的最小公倍数,记为lcm{a1,a2,…,an}(leastcommonmultipler)或者[a1,a2,…,an].A.2同余与模运算同余是数论中一个基本概念,它的引人简化了数论中的许多问题同余的很多性质和“等于”很类似1带余除法若a,b是二个正整数,b≠0,则唯一存在二个整数k和r,使得下式成立:a=bk+r,0≤rb.分别称k和r为a除以b(或者b除a)的商和余数。还可表示为：a=[a/b]b+a(modb)例A.1参见教材p144。2整数同余与模运算定义2.1给定一正整数m,若用m去除两个整数a和b所得余数相同,则称a与b模m同余,记作ab(modm);若余数不同,则称a与b模m不同余,记作ab(modm).m称为模数，a(modm)称为a模m的余数。显然，a0(modm)iffm|a.ab(modm)a=km+bm|a-b例A.2（参见教材p145）2整数同余与模运算模n同余类（剩余类）任何整数a除以正整数n的余数一定在集合{0，1，2，…，n-1}中，所有整数根据模n同余关系可以分成n个集合，每一个集合中的整数模n同余，这样的集合称为模n同余类（剩余类）思考：从同余类的记法可以看出，它是否与代表元的选取有关？模n的完全剩余系从每一个模n同余类中取一个数为代表，形成一个集合，此集合称为模n的完全剩余系，记为ZnZn最简单表示就是集合{0，1，2，…,n-1},即Zn={0，1，2，…n-1}2整数同余与模运算模运算的性质：自反性:aa(modm).对称性:若ab(modm),则ba(modm).传递性:若ab(modm),bc(modm),则:ac(modm).可见,同余关系是等价关系.若ab(modm),cd(modm),则:a±cb±d(modm)acbd(modm).模运算具有普通运算的代数性质，可交换、可结合、可分配[(amodn)+(bmodn)]modn=(a+b)modn[(amodn)-(bmodn)]modn=(a-b)modn[(amodn)X(bmodn)]modn=(axb)modn[(aXb)modn)±(aXcmodn)]modn=(ax(b±c)modn加法消去律：如果a+ba+c(modn),则bc(modn)乘法消去律：如果abac(modn)且gcd(a,n)=1，则bc(modn)如果abdc(modn)且ad(modn)以及gcd(a,n)=1，则bc(modn)例A.3参见教材P145。指数模运算可以变成模指数运算，从而使运算得以简化，例如887mod187=[(884mod187)x(882mod187)x(88mod187)]mod187882mod187=7744mod187=77884mod187=[(882mod187)x(882mod187)]mod187=(77x77)mod187=132887mod187=(132X77X88)mod187=11例A.4参见教材P146。消去律的条件逆元的概念加法逆元:设a,n∈Z且n1，如果存在b∈Z使得a+b≡0(modn)，则称a、b为互为模n的加法逆元，也称负元，记为b≡-a(modn)乘法逆元：设a,n∈Z且n1，如果存在b∈Z使得ab≡1(modn)，则称a、b为互为模n的乘法逆元，记为b≡a-1(modn)逆元的存在性加法逆元总存在，例如n-a乘法逆元存在的充要条件是a与n互素时A.3欧拉定理1欧拉函数对于正整数n，(n)定义为小于n且与n互质的正整数的个数。例如(6)=2，这是因为小于6且与6互质的数有1和5共两个数再如(7)=6，这是因为互质数有1，2，3，4，5，6共6个。如果n为素数，则(n)=n-1如果gcd(m,n)=1，则(mn)=(m)(n)2欧拉定理费尔马定理（欧拉定理实际上是费尔马定理的推广）如果p是素数，则对任意的a，有1mod1pap2欧拉定理如果p不是素数，则对任意的a，有1mod)(papphikpppppphi111111)(21p1,p2,…,pk是p的所有素数因子例如，5(6)mod6=52mod6=25mod6=1，3(7)mod7=36mod7=729mod7=1，也就是说，在对n求余的运算下，(n)指数具有周期性。