数论-绪论
- 格式:ppt
- 大小:1.34 MB
- 文档页数:47
第一章整除理论整除性理论是初等数论的基础。
本章要介绍带余数除法,辗转相除法,最大公约数,最小公倍数,算术基本定理以及它们的一些应用。
第一节数的整除性定义1设a,b是整数,b≠ 0,如果存在整数c,使得a = bc成立,则称a被b整除,a是b的倍数,b是a的约数(因数或除数),并且使用记号b∣a;如果不存在整数c使得a = bc成立,则称a不被b 整除,记为b|/a。
显然每个非零整数a都有约数±1,±a,称这四个数为a的平凡约数,a的另外的约数称为非平凡约数。
被2整除的整数称为偶数,不被2整除的整数称为奇数。
定理1下面的结论成立:(ⅰ) a∣b⇔±a∣±b;(ⅱ) a∣b,b∣c⇒a∣c;(ⅲ) b∣a i,i = 1, 2, , k⇒b∣a1x1+a2x2+ +a k x k,此处x i(i = 1, 2, , k)是任意的整数;(ⅳ) b∣a ⇒bc∣ac,此处c是任意的非零整数;(ⅴ) b∣a,a≠ 0 ⇒ |b| ≤ |a|;b∣a且|a| < |b| ⇒a = 0。
证明留作习题。
定义2若整数a≠ 0,±1,并且只有约数±1和±a,则称a是素数(或质数);否则称a为合数。
以后在本书中若无特别说明,素数总是指正素数。
定理2任何大于1的整数a都至少有一个素约数。
证明 若a 是素数,则定理是显然的。
若a 不是素数,那么它有两个以上的正的非平凡约数,设它们是d 1, d 2, , d k 。
不妨设d 1是其中最小的。
若d 1不是素数,则存在e 1 > 1,e 2 > 1,使得d 1 = e 1e 2,因此,e 1和e 2也是a 的正的非平凡约数。
这与d 1的最小性矛盾。
所以d 1是素数。
证毕。
推论 任何大于1的合数a 必有一个不超过a 的素约数。
证明 使用定理2中的记号,有a = d 1d 2,其中d 1 > 1是最小的素约数,所以d 12 ≤ a 。
数论 1 知识点严文兰1.符号说明:如无特别说明,下面出现的字母表示的数都是整数2.整数的离散型:整数a <b ⇔a +1 ≤b ,3.n 次方差公式:a n -b n = (a -b)(a n-1 +a n-2b ++b n-1 ) ,4.带余除法:设a, b是两个给定的整数,且b ≠0,则存在唯一一对整数q和r,满足a =qb +r, 0 ≤r <| b |(1)当r=0 时,a =qb ,那么就说a 可被b 整除,记作b | a ,且称a 是b 的倍数,b 是a 的约数(也可称为因数,除数),a 不能被b 整除就记作b /|a ,(2)如果a 为素数,且a n | b, a n+1 /| b, 那么记为a n || b(3)设m ≠ 0 ,如果a, b 被m 除的余数相同,即m | a -b ,则称a 同余于b 模m,b 是a 对模m 的剩余,记为a ≡b(mod m) ,此关系式称为模m 的同余式,不然,则称a 不同余于b 模m,记为a≡/b(mod m),5.整除的性质:(1)a | b, b| c ⇒a | c(2)a | b, a | c ⇒a | bx +cy ,特别地a | b, b | c ⇒a | b ±c ,(3)设m ≠ 0 ,那么a | b ⇔ma | mb ,(4)a | b ⇒b = 0 或| a |≤| b | ,所以 a | b, b | a ⇒b =±a(5)若(a, b) = 1,则a | c, b | c ⇔ab | c ,(6)m | a, m | b ⇒m | (a, b) ,(7)若(a, b) =1, ,则a | bc ⇔a | c ,(8)p 为素数,p | ab ⇒p | a 或p | b6.最大公约数与最小公倍数:同时整除a, b 的整数,叫a, b 的公约数,其中最大的那个,叫a, b 的最大公约数,记为(a, b) ,同样,同时整除a, b, , c 的最大整数,叫a, b, , c 的最大公约数,记为(a, b, , c) ,1 2 1 2同样,同时是 a , b ,, c 的倍数的整数,叫 a , b , , c 的公倍数,其中最小的正整数,叫a ,b , ,c 的最小公倍数,记为[a , b , , c ] 。
数论选讲一、整除1.整数是离散的,每两个整数之间的距离至少为1.即1a b a b <⇔-≤,,a b Z ∈2.带余除法.设0b >,对于任一整数a ,总可以找到一对唯一确定的q ,r 满足 a qb r =+,0r b ≤<.我们称r 为a 除以b 的余数.当0r =时,我们说a 被b 整除或b 整除a ,记为|b a .并称a 是b 的倍数或b 是a 的约数(因数),此时b a ≤.当0r ≠时,我们说a 不被b 整除或b 不整除a ,记为|b a /.3.如果正整数a 除了1及a 以外没有其他的约数,则称a 为质数,否则称a 为合数. 100以内的质数如下: 2,3,5,7,11,13,17,19, 23,19,31,37,41,43,47,53,59,61,67,71,73,79,83,89,914.唯一分解定理.每一个大于1的自然数n 都可写成质数的连乘积,即表示成12121ki k k i i n p p p p αααα===∏的形式,其中12k p p p <<<为质数,*i N α∈,且这种表示是唯一的.5.利用唯一分解定理,我们可以得到关于n 的正约数的两个性质:n 的正约数个数为 121()(1)(1)(1)(1)kk i i d n αααα==+++=+∏. n 的所有正约数之和为 01()ik j i j i n p ασ===∑∏.6.若|x a 且|x b ,则称x 为a 、b 的公约数.设d 为所有x 中的最大者,则称d 为a 、b 的最大公约数,记作(,)d a b =.7.若|a y ,|b y ,则称y 为a 、b 的公倍数.设m 为所有y 中大于零的最小者,则称m 为a 、b 的最小公倍数,记作[,]m a b =.8.对于任意正整数a 、b ,都有(,)[,]ab a b a b =.9.贝佐特(1730~1783)定理.设(,)d a b =,则存在整数u 、v ,使得ua vb d +=.10.如果|a c ,|b c ,(,)1a b =,则|ab c .【例题选讲】1、证明两个连续正整数的积不可能是完全平方数,也不可能是完全立方数.反设存在正整数x ,y ,使x (x +1)=y 2,由于x ,x +1互质,故x ,y 都是完全平方数. 两个完全平方数相差1,只有0与1满足要求,此时x =0,y =0,与x 为正整数矛盾. 又反设存在正整数x ,y ,使x (x +1)=y 3,由于x ,x +1互质,故x ,y 都是完全立方数. 设x =u 3,x +1=v 3(u ,v ∈N *,v >u ),v 3-u 3=(v -u )(v 2+vu +u 3)=1,由于v -u ≥1,v 2+vu +u 2≥7,故v 3-u 3=1不成立,故证.2、设m >n ≥1,(m ,n )=d ,证明:d mC n m 为整数. 证明:由于C n m 为整数,又n m C n m =n m ×m !n !(m -n )!=C n -1m -1为整数. 存在x ,y ∈Z ,使xm +yn =d ,所以,d m C n m =xm +yn m C n m =x C n m +y n m C n m=x C n m +y C n -1m -1∈Z .3、证明:若(m ,n)=1,则m|C n m +n -1. C n m +n -1=m m +n C m m +n ⇒mC n m +n -1+nC n m +n -1=mC m m +n ⇒ nC n m +n -1=m(C m m +n -C n m +n -1), ∴ m|n C n m +n -1,但(m ,n)=1,故m|C n m +n -1. 4、在n 2与(n +1)2之间任取若干个互不相同的整数,则这些整数两两的乘积都互不相等. 证明:若只取3个整数a ,b ,c ,满足n 2<a <b <c <(n +1)2,则ab <ac <bc .故只有取的数至少有4个时才有可能使两两的积相等.设n 2<a <b <c <d <(n +1)2,且有ad =bc .于是b a =d c ,令b a =d c =u v(u ,v ∈N *, (u ,v )=1). 于是,必有b =up ,d =uq ,a =vp ,c =vq .由c >b >a ,知u >v ,q >p .所以,u ≥v +1,q ≥p +1.d =uq ≥(v +1)(p +1)=vp +p +v +1=a +(p +v )+1≥n 2+2pv +1≥n 2+2a +1>n 2+2n +1=(n +1)2.与d <(n +1)2矛盾.5、已知a 、b 为正整数,并且ab 2|(a 3+b 3),求证a =b .设(a ,b )=d ,且a =a 1d ,b =b 1d (a 1,b 1为自然数),则(a 1,b 1)=1.由ab 2|(a 3+b 3),可设a 3+b 3=kab 2 (k ∈N *),∴ a 3=b 2(ka -b ).即a 31=b 21(ka 1-b 1).于是,b 1|a 1,故(a 1,b 1)=b 1=1. a 31|(ka 1-1),于是a 1|(ka 1-1),∴ a 1|1,于是a 1=1. ∴ a =b =d .注:由于ab 2与a 3、b 3均为3次式,故可同时约去d 3而不影响问题的结论.故可设(a ,b )=1来做.又证:设a 3+b 3ab 2=k (k ∈N *),即(a b )2+b a =k .记x =a b,则x 为有理数,且x 3-kx +1=0. 此方程的有理根只能为x =±1,但a ,b 均为自然数,故x =1,∴a =b .6、存在1000个连续正整数,其中恰有20个素数.证明:取1001!+2,1001!+3,…,1001!+1000,1001!+1001,这1000个数都是合数. 记1001!+2=a .则a ,a +1,a +2,…,a +999均为合数.去掉a +999,添上a -1,又得1000个数:a -1,a ,a +1,…,a +998.由于去掉一个合数而添了一个整数,故所得1000个数中至多有1个素数.再去掉a +998而添上a -2,此时,这1000个数中素数的个数比刚才的1000个数多1个或相同或减少1个.这一过程可以一起进行到得到1,2,…999,1000这1000个数为止.此时,这1000个数中的素数个数多于20个(2至100中就有25个素数)由于每次置换1个数时,所得的1000个与与原1000个数相比较,素数的个数只能增加1个或相同或减少1个.于是这一过程中每次所得素数个数至多变化1个,于是必有某个时刻,恰有20个素数.说明:《离散的零点定理》设f (n )是定义在整数上的函数,取值也是整数.且|f (n +1)-f (n )|≤1,且存在不同两个整数a ,b (a <b ),使f (a )f (b )<0,则必存在整数c ,满足a <c <b ,使f (c )=0.7、求出具有下述性质的正整数n :它被≤n 的所有正整数整除.解:设q 2≤n <(q +1)2,(q ∈N *),则[n]=q .令n =q 2+r(0≤r ≤2q).由于q|n ,q|q 2,故q|r ⇒r =0,q ,2q .即所有满足n =q 2,q 2+q ,q 2+2q 的正整数均为本题的解.解:显然,n =1,2,3,4满足题意.现设n ≥5.由此题知,n =q 2,q 2+q ,q 2+2q .且q ≥2.又n 能被q -1整除.当n =q 2=q(q -1)+q ,于是q -1|q ⇒q -1=1⇒q =2时,此时,n =4;当n =q 2+q =(q -1)(q +2)+2,有q -1|2⇒q =2,3,此时,n =6,12;当n =q 2+2q =(q -1)(q +3)+3,有q -1|3⇒q =2,4,此时,n =8,24.∴ n =1,2,3,4,6,8,12,24.8、证明:有无穷多个n ,满足:n|2n +1.分析:证明满足某要求的整数有无穷多个,通常有:⑴ 给出一个公式,可以由此公式得出无穷多满足要求的数;⑵ 给出一个递推式,可以由其中任一个满足要求的数得出只一个满足要求的数;且这些数都互不相同;⑶ 用数学归纳法证明之.解法一:n =1时,1|21+1;n =3时,3|23+1;n =9时,9|29+1.即n =30,31,32时均满足要求.故推测3k |23k+1对于一切正整数k 成立.下用数学归纳法证明:设3k |23k +1.则存在正整数t ,使23k =3k t -1.故23k +1+1=(3k t -1)3+1=33k t 3-32k +1t 2+3k +1t =3k +1t(32k -1t 2-3k t +1).即3k +1|23k +1+1. ∴ 由数学归纳原理知,对于一切正整数k ,都3k |23k+1.从而有无穷多的整数n =3k 使n|2n +1,解法二:前已有n =1时,3|21+1=3,又有23|23+1=9,9|29+1=513.故推测:若m k |2m k +1,记m k +1=2m k +1,则m k +1|2m k +1+1.下用数学归纳法证明之:由于2m k +1为奇数,故m k 为奇数,令2m k +1=m k u ,u 为奇数.即m k +1=m k u .于是,2m k +1+1=(2m k )u +1=(2m k +1)((2m k )u -1-(2m k )u -2+…+1)=m k +1((2m k )u -1-(2m k )u -2+…+1).即m k +1|2m k +1+1成立.由数学归纳法知推测成立. 说明:解法一即给出一个解的公式,解法二给出了一个递推.均用数学归纳法证明.9、证明:任意正整数n 可以表示成a -b 的形式,其中a ,b 是正整数,且a 与b 不同的素因子个数相同.证明:n =pn -(p -1)n .若n 为偶数,取p =2,a =pn ,b =n .此时,a ,b 的不同素因子个数都与n 相同. 若n 为奇数,取不能整除n 的最小素数p ,p ≥3.此时,p -1的素因子或者只有2(p -1=2k ),或者除2外都是n 的因子(因小于p 的素数都能整除n),此时a ,b 的素因子都比n 多1个.故证.二、同余11.设*m N ∈,如果整数a 、b 除以m 的余数相同,则其差a b -必被m 整除,即存在q Z ∈使得a b qm -=.则称a 、b 模m 同余,或简称同余.记为()mod a b m ≡.12.同余的基本性质.①()mod a a m ≡.②若()mod a b m ≡,则()mod b a m ≡.③若a b ≡,()mod b c m ≡,则()mod a c m ≡.④若a b ≡,()mod c d m ≡,则 ()mod xa yc xb yd m +≡+,x 、y Z ∈.()mod ac bd m ≡. ()mod n n a b m ≡,n N ∈.⑤若()mod ac bc m ≡,则mod(,)m a b c m ⎛⎫≡ ⎪⎝⎭.⑥若()mod a b m ≡,|n m ,则()mod a b n ≡. ⑦若()mod i a b m ≡,则()12mod[,,,]k a b m m m ≡.13.同余是一种等价关系,整数集Z 可以根据模m 来分类:如果a 、b 模m 同余,则a 、b 属于同一类,否则不属于同一类.这样可以得到模m 的m 个剩余类(同余类),即: {}i M i km k Z =+∈,0,1,2,,1i m =-.从每一类中各取一个数作为代表得到的m 个数称为模m 的一个完全剩余类,简称完系, 当m 为奇数时,其由绝对值最小的数组成的完系为: 10,1,2,,2m -⎧⎫±±±⎨⎬⎩⎭. 当m 为偶数时,其由绝对值最小的数组成的完系为:0,1,2,,(1),22m m ⎧⎫±±±-⎨⎬⎩⎭. 14.在模m 的m 个剩余类{}i M i km k Z =+∈(0,1,2,,1i m =-)中,如果i 与m 互质,那么i M 中每一个数均与m 互质.这样的剩余类共有()m ϕ个,()m ϕ是1、2、…、m 中与m 互质的个数,称为欧拉函数.15.在()m ϕ个剩余类中各取一个代表,称为模m 的缩剩余系,简称缩系.质数p 的缩系由1p -个数组成,即 {}1,2,,1p -,或11,2,,2p -⎧⎫±±±⎨⎬⎩⎭. 16.设正整数m 、n 互质,则()()()mn m n ϕϕϕ=. 事实上,如果{}12,,,t a a a ,{}12,,,s b b b 分别是模m 与模n 的缩系, 那么{}1,1i j mb na i s j t +≤≤≤≤是模mn 的缩系.17.设1i k i i n p α==∏,i p 为不同的质数,*i N α∈.则1111()(1)(1)i kk i i i i i n n p p p αϕ-===-=-∏∏. 18.欧拉定理:设(),1a m =,则()()1mod m a m ϕ≡.19.费马小定理:设p 为质数,则()mod p a a p ≡.当(),1a p =时,()11mod p a p -≡.20.中国剩余定理(孙子定理):设正整数1m 、2m 、…、k m 两两互质,则对于任意给定的整数1a 、2a 、…、k a ,同余方程组()()()1122mod mod mod k k x a m x a m x a m ≡⎧⎪≡⎪⎨⎪⎪≡⎩一定有解.令1k i i M m ==∏,则其解为 1k i i i iM x a b m =≡⋅∑. 其中i b 满足()1mod i i iM b m m ⋅≡. 【例题选讲】10、证明:若整数a ,b ,c 满足a +b +c =0,记d =a 1999+b 1999+c 1999.则|d|不是素数.证明:首先,u n ≡u(mod 2),故d =a 1999+b 1999+c 1999≡a +b +c ≡0(mod 2),即2|d .又由Fermat 定理,u 3≡u(mod 3)⇒u 3k ≡u(mod 3),从而u 1999=u 33·74+1≡u 74+1=u 75≡u 25=u 24+1≡u 8+1≡u(mod 3),故d =a 1999+b 1999+c 1999≡a +b +c ≡0(mod 3),∴ 6|d ,即|d|不是素数.11、用1,2,3,4,5,6,7这7个数码组成7位数,每个数码恰用一次,证明:这些七位数中没有一个是另一个的倍数.设有两个这样的七位数a ,b ,(a >b),满足a =bc ,其中c 为大于1的整数.由于1+2+3+4+5+6+7=28≡1(mod 9),故a ≡b ≡1(mod 9).若a =bc ,则bc ≡1(mod 9),于是,c ≡1(mod 9).但c >1,从而c ≥10.此时bc 不是七位数,与a 是七位数矛盾.12、设p 为素数,a ≥2,m ≥1,a m ≡1(mod p),a p -1≡1(mod p 2).求证:a m ≡1(mod p 2).证明:a m ≡1(mod p)⇒a m =1+px ,故a pm =(1+px)p =1+p 2(……).所以,a pm ≡1(mod p 2).∵a p-1≡1(mod p2)⇒a(p-1)m≡1(mod p2).同乘以a m:a pm≡a m(mod p2)∴a m≡a pm≡1(mod p2)13、设p为给定正整数,m,n为任意正整数,试确定(2p)2m-(2p-1)n的最小正值.解:(2p)2m≡1(mod 2p-1),故(2p)2m-(2p-1)n≡1(mod 2p-1).若存在m,n,使(2p)2m-(2p-1)n=1,则有(2p)2m-1=(2p-1)n⇒((2p)m+1)((2p)m-1)=(2p-1)n.由于(2p)m+1,(2p)m-1)=1,故(2p)m+1=a n,(2p)m-1=b n,且(a,b)=1.即a n-b n =2.只有n=1,a=b+2时成立,此时,解(2p)2m-(2p-1)=1⇒2p((2p)2m-1-1)=1这是不可能的.故所求最小值≠1.再若存在m,n使(2p)2m-(2p-1)n=(2p-1)+1=2p,此时,(2p)2m-(2p-1)n≡-(-1)n≠0(mod 2p),故不可能.于是,所求最小值≥4p-2+1=4p-1.取m=1,n=2,得(2p)2-(2p-1)2=4p-1.∴所求最小值为4p-1,当m=1,n=2时取得此最小值.14、数列{x n}:1,3,5,11,…,满足x n+1=x n+2x n-1(n≥2),数列{y n}:7,17,55,161,…,满足y n+1=2y n+3y n-1(n≥2),证明:这两个数列没有相同的项.分析:证明这两个数列mod 8后都是周期数列.证明:mod 8:数列x n(mod 8):1,3,5,3,5,….若x2k-2≡3,x2k-1≡5(mod 8)成立,则x2k+1≡5+2×3=11≡3(mod 8),x2k≡3+2×5=13≡5(mod 8).即x2n≡3,x2n+1≡5(mod 8)对于一切n∈N*成立.而数列y n(mod 8):7,1,7,1,….若y2k-1≡7,y2k≡1(mod 8)成立,则y2k+1≡1×2+7×3=23≡7(mod 8),y2k+2≡7×2+1×3=17≡1(mod 8).即y2n≡1,y2n+1≡7(mod 8)对于一切n∈N*成立.在{x n}中,x1=1≡1(mod 8),但y n是单调增的,且y1>1,故y n>1,于是不可能y n =1,故证.说明:利用抽屉原理可以证明:若数列{x n}满足递推关系:x n+k=f(x n+k-1,x n+k-2,…x n),其中f为k元整系数多项式.初始值x1,x2,…,x k为给定整数.于是{x n}为一整数数列.则{x n}模m(m>1,m∈N*)后终将成为周期数列(可能除去开始的若干项).15、设m是给定正整数,证明:由x1=x2=1,x n+2=x n+1+x n(k=1,2,…)定义的数列{x n}的前m2个项中,必有一个能被m整除.证明:记x i≡y i(mod m)(0≤y i≤m-1).取数组(y1,y2),(y2,y3),…,(y i,y i+1),….由于只有m2个不同的数组.故取m2+1个数组,必有两个数组相同,即存在1≤i<j ≤m2+1,使y i=y j,y i+1=y j+1,于是(y i,y i+1)=(y j,y j+1),取满足此要求的最小的i,则i必须为1.否则,由i>1,则y i-1≡y i+1-y i,y j-1≡y j+-y j(mod m),1于是,y i-1=y j-1,得(y i-1,y i)=(y j-1,y j),这与i的最小性矛盾.从而i=1.即存在(y j,y j+1)=(1,1)(j≤m2+1),此时y j-1=0,即m|x j-1.故证.16、连结正n 边形的顶点,得到一个n -折线(即用这个正n 边形的n 个顶点为顶点连出一个有n 条边的闭折线).证明:若n 为偶数,则连线中有两条平行线;若n 为奇数,则连线中不可能恰有两条平行线.证明:按逆时针顺序把为n 个顶点编号:0,1,2,…,n -1.且按a 0-a 1-…-a n -1-a n =a 0连成折线,其中a 0,a 1,…,a n -1是0,1,2,…,n -1的一个排列.由于a i 为正n 边形的顶点,故a i a i +1∥a j a j +1⇔⌒a i a i +1=⌒a j a j +1⇔a i +a i +1≡a j +a j +1(mod n).⑴ 当n 为偶数时,2 |/ n ⁄-1,故模n 的任一完系之和≡0+1+…+(n -1)=12n(n -1)≡/0(mod n).但Σi =0n -1(a i +a i +1)=Σi =0n -1a i +Σi =0n -1a i +1=2Σi =0n -1a i =2×12n(n -1)≡0(mod n). 这说明全体a i +a i +1不构成完系.所以,必有0≤i ,j ≤n -1,i ≠j ,使a i +a i +1≡a j +a j +1(mod n),于是必有两条平行线.若n 为奇数,若恰有一对边a i a i +1∥a j a j +1,则a i +a i +1(mod n)的剩余类中,必有一对剩余类r 出现2次,故必有一对剩余类s 没有出现,于是Σi =0n -1(a i +a i +1)=Σi =0n -1a i +Σi =0n -1a i +1=2Σi =0n -1a i ≡0(mod n), 另一方面,Σi =0n -1(a i +a i +1)≡0+1+…+(n -1)+r -s ≡r -s ≠0(mod n). 这说明,n 为奇数时,不可能恰有一对边平行.17、设n 为奇数,n ≥3.集合S ={0,1,2,…,n -1}.证明:在S 中去掉任一个元后,余下的元都能划分成两个集合,每个集合都有n -12个元,且两组的和模n 同余. 证明:1° 首先,若去掉的元为0,⑴ n =4k +1,则余下4k 个元分成2k 对:{1,4k},{2,4k -1},…,{2k ,2k +1},每对的和mod n 均为0.于是,任取其中k 对为一组,余下k 对为另一组,两组的和模n 同余;⑵ n =4k +3,余下4k +2个元中,先取{1,2,4k},{3,4k +1,4k +2},再把其余的数分成2k -2对:{4,4k -1},{5,4k -2},…,{2k +1,2k +2},每对的和mod n 均为0.于是,任取其中k -1对加上{1,2,4k}为一组,余下k -1对加上{3,4k +1,4k +2}为另一组,两组的和模n 同余;2° 若去掉的数为a ,则把所有的数都加n -a 得到集合S '={n -a ,n -a +1,…,n ,n +1,2n -a -1},S '仍是模n 的完系.去掉S 中的a 对应于S '中的n .于是S '可以按1°分成满足要求的两组,再把分好的数各减去n -a 即得到S 的一个分法.18、一个立方体的顶点标上数+1或-1,各面中心标上一个数,它等于该面4个顶点上标的数的乘积.证明:这样标出的14个数的和不能为0.证明:设此14个数的和为S .现把任一个标-1的顶点改为标+1,则它同时使相关3个面上的数的符号改变,改变后14个顶点上数的和为S '.于是S -S '=2(±1±1±1±1)但任何4个+1或-1的和为偶数,于是S -S '≡0(mod 4).这样一起做下去,直到所有顶点标的数都为+1,此时和S "=14≡2(mod 4).于是S ≡2(mod 4),从而S ≠0.19、求所有正整数n ,使由n -1个数码1及1个数码7组成的n 位数都是素数.解:对于n ,所有这样的n 位数都可写成N =A n +6×10k (其中,A n 表示由n 个1组成的n 位数,k =0,1,…,n -1).若3|n ,则3|A n ,于是3|N .此时N 不是素数.现设3 |⁄ n , A n注意A 6≡0(mod 7),故有A 6k +r ≡A r (k ∈N *,1≤r ≤6).由于(10,7)=1,故1,10,102,…,105是7的一个缩系,从而6×10k (k =0,1,2,3,4,5)也是mod 7)的一个缩系.又有下表:且6×106k +r ≡6×10r (k ∈N *,0≤r ≤5).∴ n >6时,按n ≡1,2,4,5(mod 6),取k =0,4,5,2,即有7|N .此时N 不是素数.而n =4时,7111=13×547;n =5时,11711=7×1673,即n =4,5均不满足要求. ∴ n =1,2.三、高斯函数与不定方程21.高斯函数[]x :表示不超过x 的最大整数,称为x 的整数部分.同时记{}[]x x x =-为x 小数部分(或称尾数部分).22.[]x 的基本性质:①x R ∀∈,[][]11x x x x -<<+≤;②x R ∀∈,[]{}x x x =+;③x R ∀∈,n Z ∈,[][]x n x n +=+,{}{}x n x +=.④x R ∀∈,y R ∈,[][][]x y x y ++≤,{}{}{}x y x y ++≥.⑤0x ∀≥,0y ≥,[][][]xy x y ≥.【例题选讲】20、若n≡4(mod 9),证明不定方程x3+y3+z3=n没有整数解.证明:x≡1,2,0(mod 3)⇒x3≡1,2,0(mod 9),∴x3+y3+z3≡0,1,2,3,6,7,8(mod 9).故此方程无解.21、确定方程x41+x42+…+x4 14≡1599的全部非负整数解.解:x4≡0,1(mod 16),于是x41+x42+...+x4 14≡0,1,2, (14)而1599≡5(mod 16).故无解.22、证明:方程x!y!=z!有无穷多组正整数解(x,y,z)满足x<y<z.证明:由于n!=n·(n-1)!.故(n!)!=(n!)(n!-1)!从而取x=n,y=n!-1,z=n!,则有无穷多个解.说明:给出了一个解的公式.23、求不定方程x4+y4+z4=2x2y2+2y2z2+2z2x2+24的全部整数解.解:若(x,y,z)是其一个解,则(±x,±y,±z)也是方程的一个解.x4+y4+z4-2x2y2-2y2z2-2z2x2=x4+y4+z4-2x2y2-2y2z2+2z2x2-4z2x2=(x2-y2+z2)2-(2zx)2=(x2-y2+z2+2zx)(x2-y2+z2-2zx)=(x+y+z)(x-y+z)(x-y-z)(x+y-z)=-(x+y+z)(-x+y+z)(x-y+z)(x+y-z).于是,原方程即(x+y+z)(-x+y+z)(x-y+z)(x+y-z)=-23×3.由于x+y+z,-x+y+z,x-y+z,x+y-z的奇偶性相同.若它们全为奇数,则其积为奇数,不可能等于-24,若它们全为偶数,则其积可以被24整除,也不可能等于-24.从而本题无满足要求的解.解法2由于左边为偶数,故x,y,z或都为偶数,或两奇一偶.⑴若x,y,z两奇一偶,不妨设x,y为奇数,z为偶数,则x4≡1(mod 16),y4≡1(mod 16),z4≡0(mod 16),x4+y4+z4≡2(mod 16)x2≡1,9(mod 16),y2≡1,9(mod 16),z2≡0,4(mod 16).于是x2y2≡1,9(mod 16) 2x2y2+2y2z2+2z2x2+24=2x2y2+2z2(x2+y2)+24≡2+0+8≡10(mod 16).从而x4+y4+z4≡/2x2y2+2y2z2+2z2x2+24(mod 16);⑵若x,y,z均为偶数,则x4+y4+z4≡0(mod 16),2x2y2+2y2z2+2z2x2+24≡8(mod 16),仍有x4+y4+z4≡/2x2y2+2y2z2+2z2x2+24(mod 16)从而本题无满足要求的解.24、证明:方程y+y2=x+x2+x3没有非零整数解.证明:反设存在非零整数x,y满足方程,则(y-x)(y+x+1)=x3.下证(y-x,y+x+1)=1.设(y-x,y+x+1)=p,则p|x,于是由p|y-x,知p|y,但p|y+x+1,故p|1.即p=1.于是y-x与y+x+1都是完全立方数,设y+x+1=a3,y-x=b3,x=ab.则a3-b3=2x+1⇒a3-b3=2ab+1⇒(a-b)(a2+ab+b2)=2ab+1.由x=ab,①若ab>0,则x>0.有a>b.故a-b≥1,a2+ab+b2>2ab+ab=3ab =2ab+ab≥2ab+1.从而(a -b )(a 2+ab +b 2)>2ab +1,矛盾;② ab =0,则x =0,与x 非零矛盾;③ ab <0,于是2x +1<0,故a <b .b >0,a <0,|a -b |≥2.a 2+ab +b 2≥2|ab |+ab =|ab |,所以|a -b ||a 2+ab +b 2|≥2|ab |,而|2ab +1|<2|ab |,从而|(a -b )(a 2+ab +b 2)|>|2ab +1|,矛盾.故证.25、求不定方程(n -1)!=n k -1的全部正整数解.解:n =2时,有解(n ,k )=(2,1).当n >2时,左边为偶数,故n 只能为奇数.取n =3,(3-1)!=2=31-1,故有解(n ,k )=(3,1);取n =5,(5-1)!=24=52-1,故有解(n ,k )=(5,2).下设n ≥7且n 为奇数.于是n -12为整数且n -12≤n -4,所以,2×n -12|(n -2)!,从而(n -1)2|(n -1)!.∴ (n -1)2|n k -1=[(n -1)+1]k -1=(n -1)k +C 1k (n -1)k -1+C 2k (n -1)k -2+…+C k -2k(n -1)2+k (n -1).∴ (n -1)2|k (n -1)⇒(n -1)|k ⇒k ≥n -1.此时,n k -1≥n n -1-1>(n -1)!,故n ≥7时不定方程无解.即方程的解为(n ,k )=(2,1),(3,1),(5,2).26、证明方程x 2+y 2+z 2=3xyz 有无穷多组正整数解(x ,y ,z ).证明 由于方程具有对称性,故可改证此方程的满足x ≤y ≤z 的解有无数组.若x =y =z =a (a ∈N*),则3a 2=3a 3⇒a =1.即方程有解(1,1,1);若x =y =1,则得2+z 2=3z ,得方程的另一组解为(1,1,2);若x =1,y =2,则得方程z 2-6z +5=0,得方程的另一组解(1,2,5);现设(a 0,b 0,c 0) (其中a 0<b 0<c 0)是方程的一组正整数解,即a 20+b 20+c 20=3a 0b 0c 0成立,考虑方程b 20+c 20+z 2=3b 0c 0z ,即z 2-3b 0c 0z +(b 20+c 20)=0,此方程必有一正整数解z =a 0,由韦达定理,其另一解为z 1=3b 0c 0-a 0必为正整数.于是原方程必有解(b 0,c 0,3b 0c 0-a 0)且这一组解也满足b 0<c 0<3b 0c 0-a 0.令a 1=b 0,b 1=c 0,c 1=3b 0c 0-a 0为方程的一组满足a 1<b 1<c 1的正整数解,则又可从此解出发得到方程的另一组解(b 1,c 1,3b 1c 1-a 1).这一过程可以无限延续下去,从而原方程有无穷多组解.27、求不定方程组 ⎩⎨⎧x +y +z =3,x 3+y 3+z 3=3.的全部整数解. 解:(1,1,1)是一组解.消去z : x 3+y 3+(3-x -y)3=3⇒3(x +y)2-xy(x +y)-9(x +y)+8=0.∴ (x +y)(xy -3(x +y)+9)=8.于是x +y|8⇒x +y =±1,±2,±4,±8.若x +y =1,则xy =2(无解);x +y =-1,xy =-20⇒x =-5,y =4,z =4,或x =4,y =-5,z =4;x +y =2,xy =1⇒x =y =1,z =1;x +y =-2,xy =-19(无解);x +y =4,xy =5(无解);x +y =-4,xy =-23(无解);x +y =8,xy =16⇒x =y =4,z =-5;x +y =-8,xy=-34(无解).∴ 解为(1,1,1),(-5,4,4),(4,-5,4),(4,4,-5).28、求不定方程x 3+x 2y +xy 2+y 3=8(x 2+xy +y 2+1)的全部整数解.解:(x +y)((x +y)2-2xy)=8((x +y)2-xy +1).令x +y =u ,xy =v ,则得u(u 2-2v)=8(u 2-v +1)是一个关于v 的一次方程.显然u 必为偶数,设u =2w ,则得w(2w 2-v)=2(4w 2-v +1).∴ v =2w 3-8w 2-2w -2=2w 2-4w -8-18w -2.于是w -2=±1,±2,±3,±6,±9,±18. ∴ ⎩⎨⎧w = 3, 1, 4, 0,5,-1,8,-4,11,-7, 20,-16;v =-20,8,-1,1,16, 4,85,43,188,120,711, 569.x ,y 是方程t 2-2wt +v =0的整数解,故w 2-v 为完全平方数.其中只有w =5,v =16满足此要求. ∴ (x ,y)=(2,8),(8,2).29、对任意的∑∞=+*+=∈01].22[,K k kn S N n 计算和 解:因]212[]22[11+=+++k k n n 对一切k =0,1,…成立,因此,].2[]22[]212[111+++-⋅=+k k k n n n 又因为n 为固定数,当k 适当大时,.)]2[]2([,0]2[,1201n n n S n n K k k k k ==-==<∑∞=+ 故从而 30、计算和式.]503305[5020的值∑==n nS解:显然有:若.,,1][][][,1}{}{R y x y x y x y x ∈++=+=+则503是一个质数,因此,对n=1,2,…,502, 503305n 都不会是整数,但503305n +,305503)503(305=-n 可见此式左端的两数的小数部分之和等于1,于是,[503305n ]+.304]503)503(305[=-n 故 ∑∑===⨯=-+==25115021.76304251304]),503)503(305[]503305([]503305[n n n n n S 31、设M 为一正整数,问方程222}{][x x x =-,在[1,M]中有多少个解?解:显然x =M 是一个解,下面考察在[1,M]中有少个解.设x 是方程的解.将222}{}{}{2][x x x x x +⋅+=代入原方程,化简得=}]{[2x x ,1}{0].}{}]{[2[2<≤+x x x x 由于所以上式成立的充要条件是2[x ]{x }为一个整数..1)1(],1[,.)1())1(21(2),1[,11.2)1,[),12,,1,0(2}{,][个解中有原方程在因此个解中方程有可知在又由于个解中方程有即在则必有设+--⋅=-+++-≤≤+-==∈=M M M M M M M M m m m m m k mk x N m x 32、求方程.051][4042的实数解=+-x x解:.0][,1][][不是解又因<+<≤x x x x⎪⎪⎪⎩⎪⎪⎪⎨⎧≤≥>⎪⎪⎪⎩⎪⎪⎪⎨⎧≤≥<⎩⎨⎧≤-->--⎪⎩⎪⎨⎧≤+->+-+∴.217][,23][,211][;217][,23][,25][.07][2)(3][2(.0)11][2)(5][2(.051][4][4,051][40)1]([422x x x x x x x x x x x x x x 或 经检验知,这四个值都是原方程的解. 33、.][3]3[2]2[1][][:,,n nx x x x nx N n R x ++++≥∈+∈* 证明 【证】.,2,1,][2]2[][ =+++=k kkx x x A k 令 由于.,1],[1命题成立时则==n x A .2269,02694;2229,02294;2189,01894;229,0294:,876][2][2222==-==-==-==-==x x x x x x x x x x 分别代入方程得或或或解得.,,,],[][][][][][][])[])1([(]))2[(]2([])1[(]([][]2[])2[(])1[(][])1[(]2[][][])1[(]2[][][])1[(]2[][)(:].[],2[22,],)1[()1()1(],[,][,][,].)1[(,],2[],[,1122112111221111121证毕均成立故原不等式对一切命题成立时即故相加得所以成立对一切即因为即有时命题成立设*---------∈=≤∴=+++≤++-++-++-+=+++-+-++-+++≤++++++-+++=+-+++=+++-==--=---=-=-=--≤≤≤-≤N n k n kx A kx k kx kx kx kx kx x x k x k x x k x x x x k x k kx x k x x A A A A kx x k x x kA kx x k x x A A A kA x A x A A x k A k A k kx kA kA k kx kA kA kkx A A x k A x A x A k n k k k k k k k k k k k k k k k34、对自然数n 及一切自然数x ,求证:].[]1[]2[]1[][nx n n x n x n x x =-+++++++ . 解:M =|f(x)|max =max{|f ⑴|,|f(-1)|,|f(-2a )|} ⑴若|-2a |≥1 (对称轴不在定义域内部) ,则M =max{|f ⑴|,|f(-1)|} 而f ⑴=1+a +b f(-1)=1-a +b|f ⑴|+|f(-1)|≥|f ⑴+f(-1)|=2|a|≥4则|f ⑴|和|f(-1)|中至少有一个不小于2,∴ M≥2>21 ⑵|-2a |<1 M =max{|f ⑴|,|f(-1)|,|f(-2a )|} =max{|1+a +b|,|1-a +b|,|-4a 2+b|} =max{|1+a +b|,|1-a +b|,|-4a 2+b|,|-4a 2+b|} ≥41(|1+a +b|+|1-a +b|+|-4a 2+b|+|-4a 2+b|) ≥41[(1+a +b)+(1-a +b)-(-4a 2+b)-(-4a 2+b)] =)2a 2(412+ ≥21 综上所述,原命题正确.四、阶:对于(a ,n)=1的整数,满足a r ≡1 (mod n ) 的最小整数r,称为a 模n 的阶。
数论数论⽬录[隐藏]数论概述数论门类数论的发展简况数论的发展简况数论中的问题中国数论及专家数论的历史源头数论中的问题数论概述数论门类数论的发展简况数论的发展简况数论中的问题中国数论及专家数论的历史源头数论中的问题中国数论及专家[编辑本段]数论概述数论就是指研究整数性质的⼀门理论。
整数的基本元素是素数,所以,数论的本质是对素数性质的研究。
2000年前,欧⼏⾥得证明了有⽆穷个素数。
既然有⽆穷个,就⼀定有⼀个表⽰所有素数的素数通项公式,或者叫素数普遍公式。
它是和平⾯⼏何学同样历史悠久的学科。
⾼斯誉之为“数学中的皇冠” 按照研究⽅法的难易程度来看,数论⼤致上可以分为初等数论(古典数论)和⾼等数论(近代数论)。
初等数论主要包括整除理论、同余理论、连分数理论。
它的研究⽅法本质上说,就是利⽤整数环的整除性质。
初等数论也可以理解为⽤初等数学⽅法研究的数论。
其中最⾼的成就包括⾼斯的“⼆次互反律”等。
⾼等数论则包括了更为深刻的数学研究⼯具。
它⼤致包括代数数论、解析数论、算术代数⼏何等等。
数论门类初等数论同上所述,初等数论主要就是研究整数环的整除理论及同余理论。
此外它也包括了连分数理论和少许不定⽅程的问题。
本质上说,初等数论的研究⼿段局限在整除性质上。
初等数论中经典的结论包括算术基本定理、欧⼏⾥得的质数⽆限证明、中国剩余定理、欧拉定理(其特例是费马⼩定理)、⾼斯的⼆次互逆律,勾股⽅程的商⾼定理、佩尔⽅程的连分数求解法等等。
解析数论借助微积分及复分析(即复变函数)来研究关于整数的问题,主要⼜可以分为乘性数论与加性数论两类。
乘性数论藉由研究积性⽣成函数的性质来探讨质数分布的问题,其中质数定理与狄利克雷定理为这个领域中最著名的古典成果。
加性数论则是研究整数的加法分解之可能性与表⽰的问题,华林问题是该领域最著名的课题。
解析数论的创⽴当归功于黎曼。
他发现了黎曼zeta函数之解析性质与数论中的素数分布问题存在深刻联系。
确切的说,黎曼ζ函数的⾮平凡零点的分布情况决定了素数的很多性质。
数论:概念和问题
【原创实用版】
目录
1.数论的定义和起源
2.数论的概念
3.数论的问题
4.数论的应用
正文
数论:概念和问题
1.数论的定义和起源
数论,作为数学的一个分支,主要研究整数及其相关性质的理论。
它的起源可以追溯到公元前的古希腊数学家,如欧几里得和埃拉托色尼。
数论在数学领域具有悠久的历史,并与其他数学分支如代数、几何和分析等有着密切的联系。
2.数论的概念
数论涉及许多基本概念,如整数、分数、小数等。
其中,整数是最基本的概念之一。
整数可以分为正整数、负整数和零,它们构成了数论的主要研究对象。
另外,数论还研究整数的性质,如奇偶性、质数与合数、同余与最大公约数等。
3.数论的问题
数论的问题多种多样,包括但不限于以下几类:
(1)素数问题:研究质数的分布规律、性质及其应用,如著名的哥德巴赫猜想。
(2)同余问题:研究整数同余关系的性质及其应用,如求解模方程。
(3)最大公约数和最小公倍数问题:研究整数集合的公约数与公倍数,探讨它们之间的性质和关系。
(4)数的表示问题:研究整数及其相关概念的表示方法,如狄利克雷定理。
4.数论的应用
数论在许多领域都有广泛的应用,如计算机科学、密码学、统计学等。
例如,著名的 RSA 加密算法就是基于数论中的大素数分解问题。
此外,数论在数学分析、物理学、生物学等领域也发挥着重要作用。
总之,数论作为数学的一个重要分支,不仅拥有丰富的理论体系,还具有广泛的应用前景。
高等数学第一章第二章总结1 第一章:绪论第一章是高等数学的绪论,其中介绍了数学的定义、作用、历史及其发展等。
在第一章中,数学是定量和定性研究物质及其结构、关系及运动规律的科学。
它由实数、整数、有理数、分数和平面几何等基本概念组成,用各种计算、逻辑推理及分析等方法来描述客观的现象或思想的抽象模型,从而得出准确的结果。
另外,数学涉及到它在科学、技术、社会、文化等方面的应用,它是社会发展的基础。
数学发展史从古代有算术、代数、几何等学科,逐渐发展至近代以及现代,学科不断壮大,研究的领域越来越广泛,涉及到人类生活的方方面。
2 第二章:初等数学第二章主要介绍初等数学,包括数论、向量运算、数列和统计等。
数论是计算数值的研究,它涉及到质数分解、最大公约数、最小公倍数、随机数等概念,数论在正文、加密等方面有广泛的应用。
向量运算是向量和向量、向量和物体之间的运算关系,它包括线性组合、内积、外积等,向量运算在物理、声学、飞行、机器人等领域有着重要的用途。
数列是按数次递增或递减的数值序列,它包括等差数列和等比数列,比如阶乘及斐波那契数列,它们能够描述物理几何尺寸及次序关系,有着极为广泛的应用。
最后,统计是从测量、计数、比较等不同数据中抽象出的概念,它包括平均数、标准差、概率分布等,是综合应用概率论、数理逻辑及数学知识。
统计学主要用来分析和预测人们的意见、举措等,对于改进社会的规划、预防未来的决策都有着重要意义。
综上所述,第一章绪论介绍了数学的定义、作用、历史及其发展,第二章介绍了初等数学,包括数论、向量运算、数列和统计等,它们都是数学学科中非常重要的知识。
数论的概念数论,这听起来是不是有点高大上,有点让人摸不着头脑?嘿,其实它就像我们生活中的好朋友,一直陪伴着我们,只是我们可能没察觉到罢了。
你想想,咱们平时数数儿,1、2、3、4、5……这就是数论的基础呀!数论研究的就是数的性质和它们之间的关系。
比如说,为啥 2 是偶数,3 是奇数?为啥 6 能被 2 和 3 整除,而 7 就不行?就像我们每个人都有自己的特点和性格,数字也有它们独特的“脾气”。
质数,那可是数论里的“独行侠”,除了 1 和它本身,谁也别想整除它,像 5 啊,7 啊,11 啊,多有个性!合数呢,就像是善于交际的“社交达人”,能被好多数整除。
再来说说同余,这概念有点玄乎?其实没那么难!比如说,现在是8 点,再过 12 个小时是几点?20 点呗,因为 8 + 12 = 20。
但如果我们只看小时数除以 12 的余数,8 除以 12 余 8,20 除以 12 也余 8,这就是同余。
是不是有点像时钟转了一圈又回到了相似的位置?数论里还有好多有趣的东西,比如整除的规律。
能被 3 整除的数,它各个数位上的数字之和也能被 3 整除,这难道不神奇吗?你要是不信,随便找几个数试试。
还有那个著名的哥德巴赫猜想,说每个大于 2 的偶数都可以写成两个质数之和。
这就像是一个神秘的谜题,吸引着无数数学家去探索。
数论在我们生活中也有大用处呢!比如密码学,保护咱们的信息安全,靠的就是数论的知识。
还有计算机科学,没有数论的支持,那些高级的程序和算法怎么能运行得那么顺畅?所以啊,别觉得数论离我们很远,它就在我们身边,像个默默守护的精灵。
咱们要是多去了解它,就能发现数字世界里的无穷乐趣和奥秘。
总之,数论可不是什么高冷的陌生人,而是我们身边的好朋友,只要我们用心去感受,就能和它亲密无间!。