初等数论精讲与习题讲解.doc

初等数论精讲与习题讲解算术基本定理。大约公元前350年，欧几里得在他伟大的十三卷著作原本中，用了许多篇幅来讨论素数。特别是他证明了每一个比1大的数（即每个比1大的正整数）要么本身是一个素数，要么可以写成一系列素数的乘积，如果不考虑这些素数的在乘积中的顺序，那么写出来的形式是唯一的。例如：14=2*7，21=3*7，等等。等号右边的表达式分别是数14与21的“素数分解”。这样我们能把欧几里得的结果表达为：每一个大于1的计数数要么是素数，要么具有唯一的（次序变化不计）素数分解。这个事实被称为算术基本定理，它告诉我们素数好比化学家的原子所有整数得以构成的基本砌块。例1将8128的小于自身的全体正约数从小到大排成，求证：分析：（1）8128的正约数（数论知识），则其约数共有（6+1）（1+1）=14个。（柯西）数列的前n项和（估算）。裂项求和。解答：（1）8128的正约数（数论知识），则其约数共有（6+1）（1+1）=14个。8128的所有约数之和：。小于自身的正约数共（14-1=）13个，小于自身全体约数和：8128。即：。（2）（柯西）数列的前n项和（估算）。裂项求和。例2给定正整数，设两个不相等的正整数，使得求的最小值解：设，可使，若为奇数，若为偶数，时，8，时，例3求证：存在无穷多个正整数，使得都可以表示为两个正整数的平方和证明：，有：则，即：若，则不能写成平方程（整数）形式若，则，可找到，若，e，若，则，那么，例4有多少个十位数是66667的倍数，并且它们的个数仅为3，4，5和6，。解：前五位数记作A，后五位数记作B,设N满足条件,但 、 恰有一个解 、 所以 设 解 解 所以，共有种方法费马小定理是数论中的一个重要定理,其内容为:假如p是质数，且(a,p)=1，那么 a(p-1) （mod p）一、准备知识：引理1剩余系定理2若a,b,c为任意3个整数，m为正整数，且(m,c)=1,则当acbc(modm)时，有ab(modm)证明：acbc(mod m)可得acbc0(mod m)可得(a-b)c0(mod m)因为(m,c)=1即m,c互质，c可以约去，ab0(mod m)可得ab(mod m)引理2剩余系定理5若m为整数且m1,a1,a2,a3,a4,am为m个整数，若在这m个数中任取2个整数对m不同余，则这m个整数对m构成完全剩余系。证明：构造m的完全剩余系（0,1,2,m-1），所有的整数必然这些整数中的1个对模m同余。取r1=0,r2=1,r3=2,r4=3,r=i-1,1i1，b是一个整数且(m,b)=1。如果a1,a2,a3,a4,am是模m的一个完全剩余系，则ba1,ba2,ba3,ba4,bam也构成模m的一个完全剩余系。证明：若存在2个整数ba和baj同余即babaj(mod m)，根据引理2则有aaj(mod m)。根据完全剩余系的定义和引理4（完全剩余系中任意2个数之间不同余，易证明）可知这是不可能的，因此不存在2个整数ba和baj同余。由引理5可知ba1,ba2,ba3,ba4,bam构成模m的一个完全剩余系。引理4同余定理6如果a,b,c,d是四个整数，且ab(mod m),cd(mod m),则有acbd(mod m)证明：由题设得acbc(mod m),bcbd(mod m)，由模运算的传递性可得acbc(mod m)二、证明过程：构造素数p的完全剩余系P=1,2,3,4(p-1)，因为(a,p)=1，由引理3可得A=a,2a,3a,4a,(p-1)a也是p的一个完全剩余系。令W=1*2*3*4*(p-1)，显然WW(mod p)。令Y=a*2a*3a*4a*(p-1)a,因为a,2a,3a,4a,(p-1)a是p的完全剩余系，由引理2以及引理4可得a*2a*3a*(p-1)a1*2*3*(p-1)(mod p)即W*a(p-1)W(modp)。易知(W,p)=1，由引理1可知a(p-1)1(modp）中国余数定理:设 n=n1*n2.nk, 其中因子两两互质.有:a-(a1,a2,.,ak), 其中ai = a mod ni, 则 a和(a1,a2