4第四讲同余初步(2)学生版

1、第四讲 同余初步(2)阶和数论中的定理©本讲概述从费尔马小定理出发，我们还将研究与它有很大联系的一个数论中新的工具：阶.阶的概念在联赛大纲中并未明确提及，但是不论在联赛中还是冬令营乃至IMO中，与阶相联系的问题都比比皆是.完系与最小非负完系：在m个剩余类中各任取一个数作为代表，这样的m个数称为模m的一个完全剩余系，简称 完系.例如：0,1,.,m-1是模m的一个完系，这称作模m的最小非负完系.缩系与欧拉函数: 如果i与m互素，则同余类Mj中所有数都与 m互素，这样的同余类称为模 m的缩同余类.模m的缩同余类的个数记作 申(m)，称为欧拉函数.在护(m)个缩同余类中各取一数为代表，这样

2、的申(m)个数称为模 m 的一个缩剩余系，简称缩系.显然，W(1) = 1,而对m :>lW(m)为1,2,.,m-1中与m互素的数的个数，特别地，对素数p,有申(p)= p-1.欧拉函数可以如下计算:设 m=prp；2 Fk 为m的标准分解形式，则申(m)=m(1-丄-丄)PkPi此定理的证明较复杂，且远远超出了联赛要求，故略去.有兴趣同学可自行参考相关书籍显然，当(m,n) =1 时，有 W(mn) =®(m)®(n).完系与缩系的几个重要性质 当(a, m) =1， b为任意整数时,(1) 若C1,C2,.,Cm是模m的完系，那么aG +b,ac2 +b,.,a

3、cm +b也是模m的完系.(2)若r1,r2,., rq(m)是模 m的缩系，那么 ar,ar2,.,aR(m)也是模 m的缩系.以下给出数论中最为有名的两个定理：欧拉定理与费马小定理®(m)_. ,. X欧拉定理：设(a,m)=1，则a 三1(modm).费马小定理：设P是素数,p?a，贝U ap7 三 1(mod P)费马小定理的另一形式：设P是素数，则对任意整数a,有ap三a(mod p).(p|a时，上式两端同余 0；P ?a时，上式等价于费马小定理的上一形式)阶: 设m A1是一个固定的整数，(a,m)=1，可以证明(见例3),存在整数k(1<kcm)，使得ak三1(

4、modm)，我们将具有这一性质的最小正整数k称为a模m的阶.它具有极其锐利的性质:(1) 设(a, m)=1 , k是a模m的阶,u,v是任意整数，则au三av(modm)二u三v(modk).特别地，a三 1(modm)二 k|u(2)设(a, m) =1 , k是a模m的阶,则数列a,a2,a3,.,模m呈周期出现，且最小正周期为 k.数列前k项模m互不同余.设(a,m) =1，k是a模m的阶,则k|申(m)，特别地，a模素数P的阶整除P-1.事实上，我们在以前的很多题中都运用到了阶的思想，只不过是没有明确提出但是，确定a模m的阶通常是极为困难的，逐一计算a,a2,a3,.,模m的余数可以

5、求得阶，利用上述的性质(3)，可以使这一过程稍微加快一些.我们将以例题的形式给出上述性质与定理的证明，以及阶的性质©例题精讲【例1】试设法证明欧拉定理及费马小定理20【例2】设正整数a与10互素，求a (在十进制中)的末两位数码【例3】设m, n亡N*，且m为奇数，(mQ -1) = 1.证明： m(1n+2W+mn).【例4】将顺序为1,2,，2n的2n张牌变成n +1,1,n + 2,2,，n-1,2n,n，即原先的前 n张牌移至第2,4,，2n张，这称为一次洗牌.试确定有哪些n,从顺序1,2，2n开始，经过若干次洗牌可以恢复到原 来状况.【例20.n是否存在正整数 m，n使得m

6、 +11为完全平方数？请证明你的结论.【例设mAl是一个固定的整数，(a,m)=1，证明：存在整数 k(1<kcm)，使得ak三1(modm)证明阶的性质(1)【例设P是奇素数，证明：2P -1的任一素因子具有形式 2px + 1，其中x是正整数.【例【例【例10】数列an定义如下:8】设p是一个奇素数，证明： 已卫的任一正约数=1 （mQd4p）9】（1）n>1,n不整除卩一设n>1,证明：i殳n>l訓（摯+ 1）,证明:3|n.% =2n +3n +6n -1(n =1,2,3,.).求与此数列的每一项都互质的所有正整数©大显身手1.求证：任何数的末位数与

7、该数的五次方的末位数字相同;2.设a和m都是正整数，a>1.证明：m护（am-1）.3.求证：421 n7-n4.设P是奇素数，证明：21的素因子或者是 3,或者具有形式2pX+1 （ X是正整数）.5.设n为一个正奇数，证明：存在一个各数码都为奇数的正整数6.p是奇素数,m与P和p-1都互素，P与a, b,互素。证明：二Jm，使得n m.（uM加化护恤舟7证明费马数 = 2* + iCk>（Q的任意一个约数均8.设a和n为整数，均不为土1，且（a,n） =1.证明：至多有有限个 k，使得|1幵（泸=19.对于任意固定的整数 11>1， 求证数列：i巩2匚,伽皿）1）自某项开始是常数。10.证明对于任何正整数k（k：>1），都能找到一个 2的方幕数，在它的末尾的k个数字中至少有一半是9.11.证明：方程组16,3,3,. ._157I X +x +x y +y =147< 3 丄 3 亠 2 丄,._147X +x y+y +y+z =157没有整数解.12设a,d,n,为自然数，且3 <北2时i。求证:d不整除a护+1。13.试定出所有满足以