(1.8.1) a??m??1(momd. )证 设x1,x2,???,x?(m)是m的一个简系, 则由(a,m)?1及定理1.13知ax1,ax2,???,ax??m?亦是
m的一个简系, 因此有
x1?x2???x?(m)?ax1?ax2???ax?(m)(modm).
即
a?(m)?x1x2???x?(m)?1?(x1x2???x?(m))(modm). (1.8.2)
而由于(xi,m)?1, i?1,2,????(m), 故(x1?x2???x??m?,m)?1, 于是便得
定理1. 16（Fermat定理） 若
a??m??1(modm). ▋
p是一素数, a是任一整数, 则有
ap?a(modp). (1.8.3)
证 若(p,a)?1, 则由Euler定理及?(p)?p?1得ap?1?1(modp),再由a?a(modp)便有
ap?a(modp).
若(p,a)▋
例1. 16 求19992001?1, 即p|a, 则ap成立. ?0?a(modp), 即有ap?a(modp), 所以(1.8.3)除70的余数是多少？
解 因(1999,70)?1, ?(70)??(2)??(5)??(7)?24, 所以由Euler定理得
199924?1(mod70).
而2001?83?24?9及1999?28?70?39, 故
8319992001?(199924)?19999
?183?19999?19999?399?29(mod70).
所以19992001除70的余数是29. ▋
1998例1. 17 求证1?21998?????20001998是1999的倍数.
证 因1999是素数, 故?(1999)?1998.于是由Euler定理得
k1998?1(mod1999), k?1,2,???,1998,2000
从而
21
11998?21998?????19981998?19991998?20001998 ?1?1?????1?0?1?1999?0(mod1999).
这说明11998?21998?????20001998是1999的倍数. ▋
7例1. 18 证明对于任意整数n, 有n 证 由Fermat定理,
?n(mod42).
n7?n(mod7). 此外
n7?n?n(n6?1)?n(n2?1)(n4?n2?1） 从而有
?(n?1)n(n?1)(n4?n2?1)?0(mod6)，
n7?n?0(mod42). ▋
练习1.8
1．分别针对下列三种情况求模15的一个完系, 使
i) 该完系的每个数是偶数； ii）该完系的每个数是奇数； iii）该完系的每个数是绝对值最小的.
2．将上题1的“模15”换成“模12”后能否完成此题？ 3．设a1,a2,???,ak是模m(?2)的一个简系, 证明?ai?0(modm).
i?1k4．求模3的一个完系
i) ii）
完系.
?a1,a2,a3?及模5的一个完系?b1,b2,b3,b4,b5?使得
?abiij|i?1,2,3;j?1,2,3,4,5? 构成模15的一个完系.
j?a?b|i?1,2,3;j?1,2,3,4,5?及?aibj|i?1,2,3;j?1,2,3,4,5?同时是模
15的
5．将题7的“完系”换成“简系”后结论仍成立吗？ 6．设m1,m2是正整数, 证明当x跑遍m1的完系及完系.
§1. 9 一次同余方程
同余方程可以说是同余理论的核心, 象著名的中国剩余定理（孙子定理）及在公钥密码学很有应用价值的Legendre符号均源自于同余方程.
y跑遍m2的完系时, 则x?m1y跑遍m1m2的
22
定义1. 12 设m是一个大于1的正整数，a(?0),b是两个整数, 称同余式
ax?b?0(modm), 其中m?a. (1.9.1)
为x的模m的一次同余方程, 简称模m的同余方程.
如果整数x0满足ax0由此, 我们称x?b?0(modm), 那么所有关于模m同余于x0的整数均满足方程(1.9.1).
?x0(modm)是方程(1.9.1)的一个解.
x?x0(modm), 则ax0?b?0(modm),于是由dm及
设(a,m)?d, 如果(1.9.1)有解
dax0知db.这说明db是(1.9.1)有解的必要条件.
下面我们证明该条件也是(1.9.1)有解的充分条件, 即有 定理1. 17 同余方程
(1.9.1)有解的充要条件是db.
个解为
当
(1.9.1)有解时, 其解数为
d,若
x?x0(modm)为(1.9.1)的一个, 则其dx?x0?mk(modm), k?0,1,?,d?1. (1.9.2) d证明 必要性已经证明. 现证明充分性. 设db, 由(1.9.1)得
abm??x??0?mod? (1.9.1)* ddd???am?因?,??1, 故由?dd?得
Euler
?a?定理知???d?m??????d?m???a??1?mod?. 将(1.9.1)*两端乘??d???d?m??????1?d?便
即
?a????d?m??????d?x?b?a????d?d?m??????1?d?m???0?mod?,
d??
b?a?x????d?d?m??????1?d?m??mod??. (1.9.3)
d??b?a?????d?d?m??????1?d?这说明(1.9.3)是方程(1.9.1)*的一个解.进而可以验证x一个解, 充分性得证.
若xm??mod??是(1.9.1)的
d???x0(modm)是(1.9.1)的一个解, 则易证
23
x?x0?是(1.9.1)的d个不同的解.
如果x?mk(modm) (k?0,1,?,d?1) dx1(modm)是(1.9.1)的任一解, 即ax1?b?0(modm), 则由x?x0(modm)得
a(x1?x0)?0(modm).
于是m|a(x1?x0), 从而
mma?ma?(x1?x0).因为?,??1, 故有|(x1?x0), 亦即存在整数t,
ddd?dd?使得x1?x0?mt.设t?ld?k,0?k?d?1, 则 dmmmx1?x0?(ld?k)?x0?k?ml?x0?k(modm),
dddx1?x0?mk(modm),0?k?d?1. d即
所以(1.9.1)的任一解均是(1.9.2)的形式. ▋
由定理1. 17的证明中的(1.9.3)式, 我们有下列结论: 推论 当(a,m)?1时, 同余方程(1.9.1)有唯一解
x??b?a?(m)?1(modm). (1.9.4)
?(m)?1直观上看, 当模m较大时, 由于计算a实际.
例1. 19 求下列同余方程的解. i)
不易, 所以利用(1.9.4)来求得同余方程的解一般不大
3x?5?0(mod4)； ii) 58x?87?0(mod47)； 129x?831(mod1101).
?1(mod4)是所求方程的解.
iii)
解 i) 因(3,4)?1, 该方程有唯一解. 由(1.9.4)可得xii) 因(58,47)?1, 该方程有唯一解. 由于58?(47)?1不易计算, 我们不可利用(1.9.4)来求其解. 因
58?11(mod47), 87?40(mod47), 故原方程等价于
11x??7(mod47).
由于(4,47)?1, 将方程两端乘4后得：
24
44x??28(mod47),
即
3x?28(mod47),
再由(16,47)?1, 方程两端乘16后得
48x?448(mod47),
即
x?25(mod47).
iii) 因(129,1101)?3831, 故原方程有三个解. 化简原方程得
43x?277(mod367). (1.9.5)
因(43,367)?1, 故(1.9.5)有唯一解. 将其解形式地表为
277(mod367). 43277?367644?(mod367). 再分子、分母约去2得将分子、分母同加模数367得x?43?367410322?45?9x?(mod367). 将分子加上?367, 得x?(mod367), 约去5得x?(mod367).
20520541?81286(mod367). 将分子加367, 分母加?367后得x?(mod367). 约分子、分母同乘9得x?3692143(mod367). 即x?143(mod367)是同余方程(1.9.5)的解. 从而x?143(1101)去2得x?1x?是原方程的一个解.依据定理1.17, 原方程的三个解为
x?143, 143?367, 143?367?2(mod1101),
即x?143,510,877(mod1101). ▋
在例1.19的求解同余方程的过程中, 求解i)用的是公式法(1.9.3), 或称定理求解法.
求解ii) 是用与模互素的数乘或除同余方程的两端, 使x的系数逐渐减小, 以达到求解的目的, 此法可称为“数乘除法”.
求解iii) 的方法其原理同求解i) 的方法, 只不过这里是采用一种简便的形式表达法, 均是利用同余式的性质求解, 其步骤是：先将同余方程(1.9.1)两边约去因数得同余方程.
a1x1?b1?0(modm1), (a1,m1)?1. (1.9.1)**
然后将(1.9.1)**的解形式地表为x?ab1(modm1), 此处1b1a125
仅是一个分数形式的符号, 再将分子或分