资源描述
nA.1 素数与互素nA.2 同余与模运算nA.3 欧拉定理nA.4 几个有用的算法授课内容A.1 素数与互素授课内容1A.1 素数与互素A.1 素数与互素21 整除定定义1.1 设 a,b为整数，整数，a0.若有一整数若有一整数q,使得使得 b=aq,则称称 a是是b的因数的因数,b是是a的倍数的倍数;并称并称a整除整除b,记为a|b,可形式地可形式地表示表示为:a|b:=(q)(b=aq)n若a不能整除b，记为ab.n若b=aq,而a既非正负b又非正负1,则称a是b的真因数.1 整除定义1.1 设 a,b为整数，a0.若有一整数q31 整除n关于整除，显然有下列定理：定理定理1.1 对所有所有a,1|a.对所有所有a,a|0.对所有所有 a,a|a.若若a|b且且b|c,则a|c.若若a|b,则对任意的任意的c0,有有ac|bc.若若ac|bc且且c0,则a|b.1 整除关于整除，显然有下列定理：41 整除若若 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|.1 整除若 a|b且a|c,则对任意的 m,n,有 a52素数和合数n在正整数中,1只能被它本身整除.任何大于1的整数都至少能被1和它本身整除定定义2.1 一个大于一个大于1且只能被且只能被1和它本身整和它本身整除的整数除的整数,称称为素数素数;否否则,称称为合数合数.n由该定义可知，正整数集合可分三类:素数、合数和1.n素数常用p或p1,p2,来表示.2素数和合数在正整数中,1只能被它本身整除.任何大于1的62 素数和合数定定义2.2 若正整数若正整数a有一因数有一因数b,而而b又是素又是素数数,则称称b为a的的素因数素因数 n例:12=34,其中3是12的素因数,而4则不是.n素数有多少？公元前三世纪,古希腊数学家欧几里德Euclid就证明了素数有无穷多个.2 素数和合数定义2.2 若正整数a有一因数b,而b又是素数72 素数和合数 素数的一些基本结论：n素数有无穷多个n素数的整除性n素数定理n算术基本定理：有限分解和唯一分解2 素数和合数 素数的一些基本结论：83 最大公因数和最小公倍数定定义3.1 设al,a2,an和和d都是正整数都是正整数,n2.若若d|ai,1in,则称称d是是al,a2,an.的公因数的公因数.n在公因数中最大的那一个数,称为al,a2,an的最大公因数,记为gcdal,a2,an.(greatest common divisor)或者(al,a2,an).n若gcd(al,a2,an)=1,称al,a2,an是互素的.3 最大公因数和最小公倍数定义3.1 设al,a2,an93 最大公因数和最小公倍数n在互素的正整数中,不一定有素数.例如(25,36)=1,但25和36都不是素数而是合数.n在个数不少于3个的互素正整数中,不一定是每二个正整数都是互素的.例:(6,10,15)=1,但(6,10)=2,(6,15)=3,(10,15)=5.3 最大公因数和最小公倍数在互素的正整数中,不一定有素数.103 最大公因数和最小公倍数 最大公因子有下列性质：n任何不全为0的两个整数的最大公因子存在且唯一n设整数a与b不全为0，则存在整数x和y，使得ax+by=gcd(a,b)。特别地，如果a、b互素，则有ax+by=1n若若gcd(a,b)=d,则gcd(a|d,b|d)=1n若若gcd(a,x)=gcd(b,x)=1,那么那么gcd(ab,x)=1n若c|(ab),gcd(b,c)=1,则c|a3 最大公因数和最小公倍数 最大公因子有下列性质：113 最大公因数和最小公倍数定定义3.2 设a1,a2,an和和m都是正整数都是正整数,n2.若若ai|m,1in,则称称m是是a1,a2,an的公倍数的公倍数.n在a1,a2,an所有公倍数中最小的那一个,称为a1,a2,an的最小公倍数,记为lcma1,a2,an(least common multipler)或者a1,a2,an.3 最大公因数和最小公倍数定义3.2 设a1,a2,an12A.2 同余与模运算n同余是数论中一个基本概念,它的引人简化了数论中的许多问题n同余的很多性质和“等于”很类似A.2 同余与模运算同余是数论中一个基本概念,它的引人简131 带余除法若若a,b是二个正整数是二个正整数,b0,则唯一存在二个唯一存在二个整数整数k和和r,使得下式成立使得下式成立:a=bk+r,0r1，如果存在bZ使得a+b0(modn)，则称a、b为互为模n的加法逆元，也称负元，记为b-a(modn)n乘法逆元：设a,nZ且n1，如果存在bZ使得ab1(modn)，则称a、b为互为模n的乘法逆元，记为ba-1(modn)n逆元的存在性n加法逆元总存在，例如n-an乘法逆元存在的充要条件是a与n互素时消去律的条件21A.3 欧拉定理A.3 欧拉定理221 欧拉函数n对于正整数n，(n)定义为小于n且与n互质的正整数的个数。n例如(6)=2，这是因为小于6且与6互质的数有1和5共两个数n再如(7)=6，这是因为互质数有1，2，3，4，5，6共6个。n如果n为素数，则(n)=n-1n如果gcd(m,n)=1，则(mn)=(m)(n)1 欧拉函数对于正整数n，(n)定义为小于n且与n互质的正232 欧拉定理欧拉定理n费尔马定理（欧拉定理实际上是费尔马定理的推广）如果p是素数，则对任意的a，有 2 欧拉定理242 欧拉定理欧拉定理n如果p不是素数，则对任意的a，有 p1,p2,pk是p的所有素数因子 2 欧拉定理如果p不是素数，则对任意的a，有 p1,p2,25n例如，n5(6)mod 6=52 mod 6=25 mod 6=1，n3(7)mod 7=36 mod 7=729 mod 7=1，n也就是说，在对n求余的运算下，(n)指数具有周期性。例如，26
展开阅读全文