初中数学竞赛讲座——数论部分9(费马小定理).doc

《初中数学竞赛讲座——数论部分9(费马小定理).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9讲费尔马小定理一、基础知识：法国数学家费尔马在1640年提出了一个有关整数幂余数的定理，在解决许多关于某个整数幂除以某个整数的余数问题时非常方便有用，在介绍这个定理之前，我们先来看一些具体的同余式，请同学们注意观察，发现这些同余式符合什么规律．3≡1（mod2），5≡1（mod2），7≡1（mod2）…22≡1（mod3），42≡1（mod3），52≡1（mod3）…24≡1（mod5），34≡1（mod5），44≡1（mod5）…26≡（23）2≡1（mod7），36≡（33）2≡1（mod7），46≡（43）2≡1（mod7）…这些同余式都符合同一个规律，这个规律就是费

2、尔马小定理．费尔马小定理：如果p是质数，（a，p）=1，那么ap－1≡1（modp）与费马小定理相关的有一个中国猜想，这个猜想是中国数学家提出来的，其内容为：当且仅当2p-1≡1(modp)，p是一个质数。　　假如p是一个质数的话，则2p-1≡1(modp)成立（这是费马小定理的一个特殊情况）是对的。但反过来，假如2p-1≡1(modp)成立那么p是一个质数是不成立的（比如341符合上述条件但不是一个质数）。　　如上所述，中国猜测只有一半是正确的，符合中国猜测但不是质数的数被称为“伪质数”。　　对于中国猜测稍作改动，即得到判断一个数是否为质数的一个方法：　　如果对于任意满足1<

3、b

4、整数且m>1,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,…ri=i-1,1

5、3．设m是一个整数，且m>1，b是一个整数且(m,b)=1。如果a1,a2,a3,a4,…am是模m的一个完全剩余系，则ba1,ba2,ba3,ba4,…bam也构成模m的一个完全剩余系。证明：若存在2个整数bai和baj同余即bai≡baj(modm)，根据引理1则有ai≡aj(modm)。根据完全剩余系的定义可知这是不可能的，因此不存在2个整数bai和baj同余。由引理2可知ba1,ba2,ba3,ba4,…bam构成模m的一个完全剩余系。　　引理4．如果a,b,c,d是四个整数，且a≡b(modm),c≡d(modm),则有ac≡bd(modm)　　证明：由题设得ac≡b

6、c(modm),bc≡bd(modm)，由模运算的传递性可得ac≡bc(modm)（二）证明过程：构造素数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)，显然W≡W(modp)。令Y=a*2a*3a*4a*…(p-1)a,因为{a,2a,3a,4a,…(p-1)a}是p的完全剩余系，由引理2以及引理4可得a*2a*3a*…(p-1)a≡1*2*3*…(p-1)(modp)即W*ap-1≡W(modp)。易知(W,p)=1，由引理1可知ap-1

7、≡1(modp）二、典型例题：例1设为正整数.证明：的充要条件是.证明若，则

8、，于是，由Fermat小定理，知从而，由，知，故反过来，若则

9、，并且，即，利用小定理知故命题获证。说明涉及指数的同余式经常需要用到小定理，因为由小定理得出的结论中，同余式的一边是，这带来很大的方便.例2由小定理知，对任意奇质数，都有问：是否存在合数，使得成立？解这样的合数存在，而且有无穷多个.其中最小的满足条件的合数（它是从两个不同奇质数作乘积去试算出来的）.事实上，由于故所以故341符合要求.进一步，设是一个符合