haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

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

发布时间:2014-04-21 08:09:17  

初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

第9讲 费尔马小定理

一、基础知识:

法国数学家费尔马在1640年提出了一个有关整数幂余数的定理,在解决许多关于某个整数幂除以某个整数的余数问题时非常方便有用,在介绍这个定理之前,我们先来看一些具体的同余式,请同学们注意观察,发现这些同余式符合什么规律.

3≡1(mod 2),5≡1(mod 2),7≡1(mod 2)…

22≡1(mod 3),42≡1(mod 3),52≡1(mod 3)…

24≡1(mod 5),34≡1(mod 5),44≡1(mod 5)…

26≡(23)2≡1(mod 7),36≡(33)2≡1(mod 7),46≡(43)2≡1(mod 7)…

这些同余式都符合同一个规律,这个规律就是费尔马小定理.

费尔马小定理:如果p是质数,(a,p)=1,那么ap1≡1(mod p) -

与费马小定理相关的有一个中国猜想,这个猜想是中国数学家提出来的,其内容为:当且仅当2p-1≡1(mod p),p是一个质数。

假如p是一个质数的话,则2p-1≡1(mod p)成立(这是费马小定理的一个特殊情况)是对的。但反过来,假如2p-1≡1(mod p)成立那么p是一个质数是不成立的(比如341符合上述条件但不是一个质数)。

如上所述,中国猜测只有一半是正确的,符合中国猜测但不是质数的数被称为“伪质数”。

对于中国猜测稍作改动,即得到判断一个数是否为质数的一个方法: 如果对于任意满足1 < b < p的b下式都成立: bp-1≡1(mod p),则p必定是一个质数。

实际上,没有必要测试所有的小于p的自然数,只要测试所有的小于p的质数就可以了。

这个算法的缺点是它非常慢,运算率高;但是它很适合在计算机上面运行程序进行验算一个数是否是质数。

(一)准备知识:

引理1.若a,b,c为任意3个整数,m为正整数,且(m,c)=1,则当ac≡bc(modm)时,有a≡b(modm)

证明:ac≡bc(mod m)可得ac–bc≡0(mod m)可得(a-b)c≡0(mod m)因为(m,c)=1即m,c互质,c可以约去,a–b≡0(mod m)可得a≡b(mod m)

引理2.若m为整数且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<i≤m。

第 1 页 共 8 页

初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

令(1):a1≡r1(mod m),a2≡r2(mod m), …am≡rm(mod m)(顺序可以不同),因为只有在这种情况下才能保证集合{a1,a2,a3,a4,…am}中的任意2个数不同余,否则必然有2个数同余。由式(1)自然得到集合{a1,a2,a3,a4,…am}对m构成完全剩余系。

引理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 (mod m),

根据引理1则有ai≡aj (mod m)。根据完全剩余系的定义可知这是不可能的,因此不存在2个整数bai和baj同余。由引理2可知ba1,ba2,ba3,ba4,…bam构成模m的一个完全剩余系。

引理4.如果a,b,c,d是四个整数,且a≡b(mod m),c≡d(mod m),则有ac≡bd(mod m)

证明:由题设得ac≡bc(mod m),bc≡bd(mod m),由模运算的传递性可得ac≡bc(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),显然W≡W(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)a≡1*2*3*…(p-1)(mod p)即W*ap-1≡W(modp)。易知(W,p)=1,由引理1可知ap-1≡1(modp)

二、典型例题:

例1 设n为正整数.证明:73?n的充要条件是73n?1.

证明 若 73?n,

则 7|n,

于是,由Fermat小定理,知

n?1(mod7),

从而,由 73?n,

知 7(3?n)n,

故 73n?1.

反过来,若 73n?1,

则 7|n,

并且 7(3n?1)?n,

即 73?n?n,

第 2 页 共 8 页 n63n33n3n3n36n3n33n3n3

初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

利用Fermat小定理知 n?1(mod7),

故 73?n.

命题获证。

说明 涉及指数的同余式经常需要用到Fermat小定理,因为由Fermat小定理得出的结论中,同余式的一边是1,这带来很大的方便.

例2 由Fermat小定理知,对任意奇质数p,都有2

使得2n?1p?1n36?1(modp).问:是否存在合数n,?1(modn)成立?

解 这样的合数n存在,而且有无穷多个.其中最小的满足条件的合数n?341?11?31(它是从两个不同奇质数作乘积去试算出来的).

事实上,由于 210?1?1 023?341?3,

故 210

340?1(mod341), ?134?1(mod341),

a所以 2故341符合要求.

分解可知)。再设2a?1 进一步,设a是一个符合要求的奇合数,则2?1是一个奇合数(这一点利用因式?1?a?q,q为正奇数,则

2(2a?1) 2?1?2?1

?22aq?1

a2q ?(2)?1

?12q?1

a ?0(mod2?1).

因此2a?1也是一个符合要求的数.依此类推(结合341符合要求),可知有无穷多个满足条件的合数.

说明 满足题中的合数n称为“伪质数”,如果对任意(a,n)?1都有a

成立,那么合数n称为“绝对伪质数”.请读者寻找“绝对伪质数”.

例3 设p为质数.证明:存在无穷多个正整数n,使得p2?n.

证明 如果p?2,那么取n为偶数,就有p2?n,命题成立.

设p?2,则由Fermat小定理知

2

2p?1nn2a?1?1n?1?1(modn)?1(modp). 因此,对任意正整数k,都有 ?1(modp),

所以,只需证明存在无穷多个正整数k,使得

k(p?1)?1(modp)(这样,令n?k(p?1),就有p2n?n).

而这只需k??1(modp),这样的k当然有无穷多个.

所以,命题成立.

说明 用Fermat小定理处理数论中的一些存在性问题有时非常方便、简洁.

第 3 页 共 8 页 k(p?1)

初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

例4 设x为整数,p是x?1的奇质因子,证明:p?1(mod4).

证明 由于p为奇质数,若p≡/1(mod4),

由x??1(modp),得

x2p?12则p?3(mod4),可设p?4k?3,此时,?x4k?2?(x2)2k?1?(?1)2k?1??1(modp).

而由Fermat小定理,应有

p?1 x?1(modp), 结合上式将导出p2.矛盾.

所以,p?1(mod4).

说明 利用此题的结论,我们可以证明:存在无穷多个模4余1的正整数为质数. 事实上,若只有有限个质数模4余1,设它们是p1,p2,?,pn.考虑数(2p1p2?pn)2?1的质因子即可导出矛盾.

2p?1?1例5 求所有的质数p,使得是一个完全平方数. p

解 设p是一个满足条件的质数,则显然p是一个奇质数.由Fermat小定理知 p2p?1?1,

p?1

2而 2p?1?1?(2

故 p2p?1

2?1)(2p?12p?12?1), ?1.

p?1

2?1或p2由于 (2

所以,p2p?1

2p?12?1,2p?12p?12?1)?(2?1,2)?1, ?1与p2?1中恰有一个成立.

p?1

2 若p2

使得 p?12?1,则由条件及(2?1,2p?12?1)?1可知存在正整数x,

2p?1

2?1?x2,

p?1

2此时 (x?1)(x?1)?2,

所以,x?1与x?1都是2的冥次,而x为奇数,故x?1与x?1是两个相继的偶数,所以,只能是

x?1?2,x?1?4,

故 x?3,

此时 p?7. 若p2p?1

2?1,则同上知存在正整数x,使得

第 4 页 共 8 页

初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

2?1?x2,

当p?3时,导致

x?2

矛盾,故p?3. 2p?12p?12?1??1(mod4),

2p?1?1 另一方面,当p?3.和7时,分别为1和9,都是完全平方数. p

综上可知p?3或7.

892002例6.求145+3除以13的余数.

解:因13是质数,且(145,13)=1,(3,13)=1

12 由费尔马小定理得:145≡1(mod 89),312≡(mod 89)

∴14589≡(14512)7·1455≡1455(mod 13)

32002≡(312)166·310≡310(mod 13)

又∵145≡2(mod 13),33≡1(mod 13)

∴1455≡25≡6(mod 13),310≡(33)33≡3(mod 13)

所以,14589+32002≡6+3≡9(mod 13),即14589+32002除以13的余数是9.

例7.设p是质数,且p≠2.求证:1p+2p+3p+…+(p-1)p≡0(mod p)

证明:由于p是质数且p≠2,所以对任意正整数n<p,都有(n,p)=1,根据费尔马小定

-理得,np1≡1(mod p),于是np≡n(mod p)(n=1,2,3,…,p-1)

因此,1p+2 p+3 p+…+(p-1)p≡1+2+3+…+(p-1)(mod p)≡

由于p是不等于2的质数,所以

故p(p?1)(modp) 2p?1是整数. 2p(p?1)≡0(mod p),所以1p+2 p+…+(p-1)p≡0(mod p) 2

说明:①费尔马小定理也可以写成另外一种形式:如果 p是质数,对任意正整数a,都有ap≡a(mod p),

-这是因为当p时,(p,a)=1,有ap1≡1(mod p)故a p≡a(mod p);

当p | a时,显然有p | ap-a,即ap≡a(mod p).

-②费尔马小定理的逆定理不成立,也就是说,当ap1≡1(mod p)时,p不一定是质数,

例如53≡1(mod 4),且(5,4)=1,但4不是质数.

例8.求证:对任意整数a,b,ab(a4-b4)都能被30整除.

分析:因为30=2×3×5,所以只需证明2 | ab(a4-b4),3 | ab(a4-b4),5 | ab(a4-b4),因为2,3,5都是质数,所以可以考虑用费尔马小定理.

证明:因为30=2×3×5,所以只需证明2,3,5都能整除ab(a4-b4)即可,

因2是质数,根据费尔马小定理得,a2≡a(mod 2),b2≡b(mod 2),所以

42224222a≡(a)≡a≡a(mod 2),b≡(b)≡b≡b(mod 2)

44∴ab(a-b)≡ab(a-b)≡a2b-ab2≡ab-ab≡0(mod 2),即2 | ab(a4-b4).

又因为3也是质数,根据费尔马小定理得a3≡a(mod 3),b3≡b(mod 3)

第 5 页 共 8 页

初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

∴ab(a4-b4)≡ab(a2-b2)(mod 3)≡a3b-ab3(mod 3)

≡ab-ab(mod 3)≡0(mod 3),即3 | ab(a4-b4).

例9.证明:对任意自然数n>1,2n-1都不能被n整除

证明:若n为偶数,2n-1必是奇数,则n-1

若n为奇数,且n>1,假设n | 2n-1

设p为n的最小质因数,则2 n≡1(mod p),

x再设r是满足2 ≡1(mod p)的最小正整数,

即2 r≡1(mod p),若rx= kr+q,0<q<r,那么

2 x≡2 k r+q≡(2 r)k·2 q≡2q≡1(mod p)

这与r的最小性矛盾,因此r | x,又因2 n≡1(mod p),所以r | n.

p-1根据费尔马小定理得2≡1(mod p),因此r | p-1

由r | n,r | p-1知r是n的小于p的正约数,故r = 1,得p | 2-1,即p | 1,矛盾,假设不成立,即n | 2 n-1,综上所述,对任意自然数n>1,2n-1都不能被n整除.

三、模拟训练:

1.求出258000除以7的余数是多少。

解:由于25与7互质,由费马小定理可知对模7而言,256≡1(mod 7)

所以258000≡256×1333+2≡(256)1333×252≡42≡2(mod 7)

故余数为2

2.假设p为任意一个大于5的质数,试证:p必可整除np=111??11 ????

p?1个

证明:由于p和10互质且9np=10p-1-1,由费马小定理可知对模p而言,10p-1≡1(mod p) 因此,p一定能整除9np,又由于p和9互质,因此p一定能整除np

3.假设p=3k+2是一个质数,试证:如果p可整除a2+ab+b2(a和b都是整数),那么a和b必定都是p的倍数。

证明:由p可整除a2+ab+b2,p必定也能整除(a-b)(a2+ab+b2)=a3-b3,

因此a3≡b3(mod p)

左右两边同时取k次方,得a3k≡b3k(mod p) (1)

假设p不能整除a,那么p必定也不能整除b:由费马小定理可知对模p而言,

ap-1≡bp-1≡1(mod p)

将p=3k+2代入上式得:a3k+1≡b3k+1≡1(mod p) (2)

综合(1)(2)可知 a≡b≡1(mod p)

因此a2+ab+b2≡a2+a2+a2≡3a2(mod p)

所以3a2是p的倍数,又3和p互质,可知a一定是p的倍数,这与假设p不能整除a矛盾,因此a和b必定都是p的倍数。

四、【延伸阅读】

(1)形如4k+1的质数个数有无数个。

假设n是任意一个大于1的正整数:n!显然为偶数,因此(n!)2+1为奇数,而(n!)2+1的每个质因子都可表示为4k+1或4k-1的形式。

假设p=4k-1是(n!)2+1的一个质因子(可知p和n!互质),由于(n!)2≡ -1(mod p)将

第 6 页 共 8 页

初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

p?1p-1p-1左右两边同时取次方,得(n!)≡?-1?2(mod p) 2

p-12k-1为奇数,因此(n!)p-1≡ (-1)(mod p) 2

但这与费马小定理矛盾,因此根据费马小定理,由于p和n!互质,(n!)p-1必定会和1对模p同余。

由此我们推知(n!)2+1不可能有形如4k-1的质因子,也就是(n!)2+1只有形如4k+1的质因子。又由于(n!)2+1的每个质因子显然都大于n,因此我们就证明了:不管n是多少,一定有比n大而且形如4k+1的质数存在,这就说明了等差数列1,5,9,13,…中包含无穷多个质数。

(2)费马小定理的逆定理

当p为质数,由费马小定理我们知道2p-2必定是p的倍数(即前面的讨论中当a=2的情形);反过来成不成立呢?也就是说,如果有某个正整数n可以整除2n-2,我们能不能断定n一定是质数呢?如果可以的话,这将是个不错的判断任意整数n是否为质数的方法;历史上确实曾经有一段时期数学家们猜测这个方法可行,不过法国数学家Pierre Sarrus于1819年指出n=341是一个反例:341是11与13的积,因此不是质数,但是由

2341-2=2[(210)34-134]=2[(210-1)(…)]=2(1023)(…)=2(3)(341)(…)

可知341能整除2341-2.

对任意正整数a,如果有某个大于1的正整数n本身不是质数却能整除an-a,我们称n对底数a而言是一个[伪质数](英文常称作a-pseudoprime),因此对底数2而言,341是一个伪质数(即341是一个2-pseudoprime)。

几个衍生出来的问题是:341是唯一的2-pseudoprime吗?除了奇数的伪质数外,是否还存在着[偶伪质数]?对任意正整数a,a-pseudoprime的个数是有限还是无限?

对底数2而言,如果n是一个奇伪质数,我们不难证明2n-1将是另一个更大的奇伪质数;既然我们已知奇伪质数341的存在,对底数2来说奇伪质数的个数因此是无穷的,寻找偶伪质数(对底数2而言)的工作比寻找奇伪质数要困难许多,其中最小的数直到1950年才由美国数学家D.H.Lehmer找到,其值为161038=2?73?1103.由于2161038-2=2(2161037-1)要说明161038可以整除2161038-2,我们只要说明73和1103(皆为质数)都能整除2161037-1即可。由于161037可经质因数分解为32?29?617,因此

2161037-1=2(29)29?617-129?617=(29-1)(…)=(511)(…)=7(73)(…) 可知73能整除2161037-1。又由于

2161037-1=2(229)9?617-19?617==(229-1)(…)=1103(486737)(…)

因此1103的确也能整除2161037-1,数学家N.G.W.H.Beeger于1951年还证明了对底数2而言,偶伪质数的个数也是无穷的。

数学上还能证明:对任意正整数a,以a为底数的伪质数的个数都是无穷的。

(3)需要洗几次牌?

考虑以下动作:将一副扑克牌(52张)由中间分成各含26张牌的两小迭,然后洗牌

第 7 页 共 8 页

初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

使得这两迭牌一张一张交错,重新组合成52张牌,下图显示了洗牌前后位置的变化:

我们称上述动作为一次洗牌,请问:经过洗牌几次后可使得每张牌都回到它最原始的位置?

由上图洗牌前后的位置变化,我们看到原来在位置编号1,2,3,…,26的牌经过一次洗牌后被放到编号为2,4,6,…,52的位置,而原来编号为27,28,29,…,52的牌则被放到了编号1,3,5,…,51的位置,因此如果某张牌原来的位置为x,经过一次洗牌后的位置为y,那么y与x的关系为y≡ 2x(mod53):因此这张牌经过n次洗牌后的位置必定与2nx对模53同余,而我们的目标是希望能找到某个n使得对所有1≤x≤52,2nx≡x(mod53) 既然x与53互质(因为53为质数),我们可将上式左右两边的x约掉而得

2n≡1(mod53)

由费马小定理我们知道n=52次洗牌后所有的牌必定都回到原来的位置。

一般而言,如果一副牌有m张(m为偶数),而正整数n满足

2n≡1(mod m+1)

那么经过上述方式的洗牌n次后所有牌必定回到原始位置。

举例来说,如果m=62,那么我们只需洗牌6次即可,因为26≡1(mod63)。

第 8 页 共 8 页

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com