4 特殊的同余式
本章我们将学习三个比较重要的同余式，无论是在理论上还是应用上。 4.1 威尔逊定理和费马小定理
威尔逊定理证明了如果p是素数，那么p除(p?1)!?1的余数是-1，而费马小定理给出了一个整数的p次幂模p的同余式。尤其当p时素数，a是整数时，a和a被p除有相同的余数。
定理4.1（威尔逊定理） 若p是素数，则
(p?1)!??1(modp)。
p 该定理是由威尔逊根据计算事实给出了这个猜想，但并没有证明上述结论，最后由约瑟夫·拉格朗日在1771年证明出，并将定理描述为如上的同余式。在证明之前，我们先引入一个定理( 设p是素数，正整数a是其自身模p的逆，当且仅当a?1(modp)或者a??1(modp))
证明 当p?2时，我们有(p?1)!?1??1(mod2)，因此，当p?2时定理是成立的。现在我们设p是大于2的素数，根据定理2.13对于任何满足1?a?p?1的整数a都存在逆a，使得1?a?p?1，aa?1(modp)。根据上述引入的定理，我们有在小于p的正整数中，逆等于其自身的只有1和p-1。所以，我们可以将2到p-2分成(p?3)/2组整数对。并且，每一组的乘积模p余1。所以我们有
( 2?3???p?3)p?(?2)?1(mp o接着我们用1和p?1同时乘以上式得到
!1?2?3??p?(?3p)?(?p2?)(?1?p)?1(? (p?1)?1?)? p上述定理得证。我们还可以证明威尔逊定理的逆也是正确的，我们在这里不再证明。
定理4.2（费马小定理） 设p是一个素数，a是一个正整数并且p|a，则
ap?1?1(modp)。
证明 在这里我们考虑p-1个整数：a,2a,...,(p?1)a，它们的共同点是都不
31
能被p整除，并且在a,2a,...,(p?1)a中任何俩个整数模p不同余。因为整数
a,2a,...,(p?1)a是p-1个均不整除p的数，并且是两两都互不同余的整数组成的
集合中的元素，那么这些数模P的最小正剩余一定可以是1,2,...,(p?1)。再根据同余性，整数a,2a,...,(p?1)a的乘积模p要同余于前p-1个正整数的乘积，也就是
,?( a,2a,...pa?1)1,2p?,...,( p1所以
p?1a(p?1)?!p(?1)!(mp od)又因为(p?1)!与p互素，我们消去(p?1)!，得到
p?1a?1(mopd )
定理得证。
pa 定理4.3 设p是素数且a是一个正整数，则?a(modp)
证明 如果p|a，根据费马小定理我们可知，
ap?1?1(modp)。我们将同余
ppp|ap|aa?a(modp)式两边同时乘以a，使得。如果那么我们就有，所以
ap?a?0(modp)。综上，我们有对于p|a和p|a结束。
我们均有
ap?a(modp)。证明
2011033 利用费马小定理，我们可以得到模11的最小正剩余，因为?1(mod11)。
因此，3201?(310)20?3?3(mod11)
费马小定理的应用
定理4.4 若p是素数，a是一个正整数并且p|a 证明 如果p|a，根据费马小定理，我们有a?aap?2是a模p的逆。
92例4.1 根据定理4.4,易知，?512?6(mod11)是2模11的逆。
，那么
ap?2是a模p的逆。
p?2?ap?1?1(modp)。因此，
4.2 欧拉定理
费马小定理告诉我们当模是素数的情况下，如何处理指数形式的特殊的同余
32
式，而欧拉定理则将费马小定理推广到了模不是素数的情形。 在此我们定义一个特殊的计数函数。
定义 设n是一个正整数，欧拉?函数?(n)定义为不超过n且与n互素的正整数的个数。下面我们给出在1?n?12时?(n)的值。
表4.1 欧拉函数?(n)的值，1?n?12
n 1 2 3 4 5 6 7 8 9 10 11 12 ?(n)1
1 2 2 4 2 6 4 6 4 10 4 定义 模n的既约剩余系是由?(n)个整数构成的集合，集合中的每个元素均与n互素，且任何两个元素模n不同余。
例4.2 集合1,3,5,7是模8的一个既约剩余系，集合-3，-1,1,3也是模8的一个既约剩余系。
定理4.5 设r1,r2,...,r?(n)是模n的一个既约剩余系，如果a是一个正整数并且a与n互素，那么集合
ar1,ar2,...,ar?(n)也是模n的一个既约剩余系。
例4.3 集合1,3,5,7是模8的一个既约剩余系，因为3与8互素，根据定理4.5我们有集合3?1?3,3?3?9,3?5?15,3?7?21也是模8的一个既约剩余系。 定理4.6（欧拉定理） 设m是一个正整数，a是一个整数，并且a与m互素，那么
a?(m)?1(modm)
证明 令r1,r2,...,r?(m)是由不超过m并且和m互素的元素组成的既约剩余系，根据定理4.5，因为a和m互素，所以集合既约剩余系，那么
ar1,ar2,...,ar?(m)也是模m的一个
ar1,ar2,...,ar?(m)在一定条件下的最小正剩余可以是
r1,r2,...,r?(m)，
我们将每个矩矱剩余系都乘起来，得到
arar...ar?m(?...12)rr1r2?m()(mmod
)
33
所以
a?(m)rr12...r?(m)?rr12...r?(m)(modm)
又因为
(rr12...r?(m),m)?1，根据推论，有
a?(m)?1(modm)。
利用上个式子，我们可以求出模m的逆。如果a和m互素，则
a?a?(m)?1?a?(m)?1(modm)
因此，
a?(m)?1是a模m的逆。 例4.4 2?(9)?1?26?1?25?32?5(mod9)可以知道，
34
2?(9)?1是2模9的逆。
5 Maple 语言或Mathematic语言
Maple系统被广泛应用于数值和符号计算。Mathematic系统同样也被广泛应用此环境。
本章借助Maple或者Mathematic等语言编程计算同余相关的问题 5.1 求解多项式同余方程
x4?13x3?11x?3?0(mod78) 相应的maple语言为
msolve(x4?13x3?11x?3,78) 得到的解为
{x = 5764800}
5.2 求解同余方程组
例5.1 求解线性同余方程组
x?2y?1(mod5 2x?y?1(mod 5)则相应的Maple语言为
solve({(x?2y?1)mod5,(2x?y?1)mod5},{x,y})
得到解
44??x??,y????33??
例5.2 求解同余方程组
2x1?5x2?6x3?3(mod7)2x1?x3?4(mod7) x1?2x2?3x3?1(mod7) Maple语言为
solve({(2x1?5x2?6x3?3)mod7,(2x1?x3?4)mod7,(x1?2x2?3x3?1)mod7},{x1,x2,x3})得到解
35