费马小定理和欧拉定理解析-初等数论成果

在第一章我们曾经从整除的角度介绍过费马小定理.现在，我们从同余的角度再看费马小定理.

第一章的表述是：设a为整数，p为质数，若p|/a，则p|（ap-1-1).

从同余的角度看，p|（ap-1-1)⇔ap-1=pq＋1⇔ap-1≡1（modp).而p|/a⇔（p，a)=1，故用同余可表述小费马定理如下.

定理1 设a为整数，p为质数，若（p，a)=1，则ap-1≡1（modp).证明 ∵p为质数，∴其最小非负完全剩余系为

∵（p，a)=1，∴0a，a，2a，3a，…，（p-1)a是p的一个完全剩余系.其中每个数都与且只与最小非负完全剩余系中的一个数取自同一个剩余类，即对模p同余.

尽管我们不能确定两个完全剩余系中的各对数的同余关系，但总有

例1 2018年儿童节是星期五，这以后的第4737天是星期几？

解 由费马小定理知，

那天是星期三.

例2 求17除477385的余数.

解 ∵17为质数，17与47互质，

故余数是13.

推论 设a为整数，p为质数，则ap≡a（modp).

证明 若（p，a)=1，则ap-1≡1（modp).

同乘a，则ap≡a（modp).

若（p，a)=p，则a≡0（modp)，ap≡0（modp)，

∴ap≡a（modp).

该命题的逆命题“设a为整数，若an≡a（modn)，则n为质数”是假命题.

满足同余式2n≡2（modn)成立的合数n叫作伪质数.

例3 求证：341是伪质数.

证明 341=11×31.

故341是伪质数.

341是最小伪质数，561也是一个伪质数，大家自己可试证一下.

在费马小定理中，p-1恰为不超过p的与p互质的正整数的个数φ（p)，因此，费马小定理的结论也可表述为aφ（p)≡1（modp).

那么，对一般正整数m，是否有这样的结论成立呢？我们有如下的欧拉定理.

定理2 设m，a∊Z，m＞1，若（m，a)=1，则aφ（m)≡1（modm).

证明 设r1，r2，…，rφ（m)是模m的一个简化剩余系，因为（m，a)=1，则ar1，ar2，…，arφ（m)也是模m的一个简化剩余系，其中，每个数与且只与r1，r2，…，rφ（m)中某个数对模m同余，故

例4 用欧拉定理证明341是伪质数.

证明 ∵φ（341)=300，∴2300≡1（mod341).

∵241=（210)4×2≡（341×3＋1)4×2≡2（mod341)，

∴2341=2300×241≡2（mod341).

例5 求20172018的末两位数.

解 ∵（2017，100)=1，φ（100)=40，∴201740≡1（mod100).

∵2018=40×50＋18，

∴20172018≡201718≡1718≡2899≡（-11)9≡-119（mod100).

∵112≡21（mod100)，114≡41（mod100)，118≡81（mod100)，(www.xing528.com)

∴119≡81×11≡91（mod100)，-119≡-91≡9（mod100).

故末两位数是09.

例6 求60除132018的余数.

解 ∵（13，60)=1，φ（60)=16，∴1316≡1（mod60).

∴132018=1316×126＋2≡132=169≡49（mod60).

故余数为49.

显然，费马小定理是欧拉定理的特例.费马小定理在1640年由费马提出但未证明，1737年欧拉给出证明，欧拉又在1760年给出并证明了欧拉定理.

由欧拉定理可知，若m，a∊Z，m＞1，（m，a)=1，则aφ（m)≡1（modm).

但使得ah≡1（modm)成立的h可能小于φ（m).例如，当m=8，a=5时，h=2，h=φ（8)=4都满足5h≡1（mod8).

如何找到使得ah≡1（modm)成立的最小h呢？我们有如下定理.

定理3 设m，a∊Z，m＞1，（m，a)=1，若k是满足ah≡1（modm)成立的所有正整数h中的最小者，则k|h.

证明 ∵k≤h，∴可设h=kq＋r（0≤r＜k)，则

∵ah≡1（modm)，ak≡1（modm)，

∴ar≡1（modm).

而k是满足ah≡1（modm)成立的所有正整数h中的最小者，故r=0.

故k|h.

推论 设m，a∊Z，m＞1，（m，a)=1，若k是满足ah≡1（modm)成立的所有正整数h中的最小者，则k|φ（m).

该推论告诉我们，欲求k，只要在φ（m)的正因数中去找即可.

例7 求使5h≡1（mod21)成立的最小正整数.

解 （5，21)=1，φ（21)=12，由欧拉定理当然有512≡1（mod21).

12的正因数有1，2，3，4，6，12.逐个试验：

51≡5（mod21)，52≡4（mod21)，53≡20（mod21)，54≡16（mod21)，

56≡4×4×4=64≡1（mod21).

故使5h≡1（mod21)成立的最小正整数为6.

习题2.3

1.求314159被7除所得的余数.

2.求314162被163除所得的余数.

3.求19941993的末两位数.

4.求652000被8除所得的余数.

5.判断494-1可否被15整除.

6.求证：7|（22225555＋55552222).

7.设p为质数，a，b为整数，求证：（a＋b)p≡ap＋bp（modp).

8.设p，q为互异质数，a为整数，且ap≡a（modq)，aq≡a（modp)，求证：

9.设（m，n)=1，求证：mφ（n)＋nφ（m)≡1（modmn).

10.求使18h≡1（mod77)成立的最小正整数.