这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。 定理2：（费尔马（Fermat）小定理）对于质数
设
p及任意整数a有ap?a(modp)。
ap?0?a(modp)。若
p为质数，若
a是
p的倍数，则
a不是
p的倍数，则
(a,p)?1由引理及欧拉定理得
?(p)?p?1,a?(p)?1(modp)，?ap?1?1(modp),ap?a(modp)，由此即得。
定理2推论：设
*p为质数，a是与p互质的任一整数，则?ap?1?1(modp)。
p为质数，则(p?1)!??1(modp)。
p?1个数，然后来对应乘法。
定理3：（威尔逊（Wilson）定理）设
分析与解答：受欧拉定理的影响，我们也找证明：对于(x,0。
p)?1，在x,2x,?,(p?1)x中，必然有一个数除以p余1，这是因为x,2x,?,(p?1)x则好是p的一个剩余系去
从而对?x?{1,2,?p?1},?y?{1,2,?, 若xy1p?1}，使得xy?1(modp)；
?xy2(modp)，(x,p)?1，则x(y1?y2)?0(modp)，p|(y1?y2)，故对于y1,y2?{1,2,?,p?1}，有
1，然后有
xy1 xy2(modp)。即对于不同的x对应于不同的y，即1,2,?,p?1中数可两两配对，其积除以p余
x，使
2x2?1(modp)，即与它自己配对，这时x?1?0(modp)，(x?1)(x?1)?0(modp)，x??1或x?1(modp)，x?p?1或x?1。
?1,p?1外，别的数可两两配对，积除以p余1。故(p?1)!?(p?1)?1??1(modp)。
fj(x)为整系数多项式（1?j?k），我们把含有x的一组同余式fj(x)?0(modmj)（1?j?k）称为同余方组程。特
除x定义：设
别地，，当
fi(x)均为x的一次整系数多项式时，该同余方程组称为一次同余方程组.若整数c同时满足：fj(c)?0(modmj)
，则剩余类
1?j?kMc?{x|x?Z,x?c(modm)}（其中
m?[m1,m2,?,mk]）称为同余方程组的一个解，写作
x?c(modm)
定理4：（中国剩余定理）设m1,m2,?,mk是两两互素的正整数，那么对于任意整数a1,a2,?,ak，一次同余方程组x?aj(modmj)，
1?j?k必有解，且解可以写为：
x?M1N1a1?M2N2a2???MkNkak(modm)
这里m?m1m2?mk，Mi?m(1?i?k)，以及Nj满足MjNj?1(modmj)，1?j?k（即Nj为Mj对模mj的逆）。 mi中国定理的作用在于它能断言所说的同余式组当模两两互素时一定有解，而对于解的形式并不重要。 定理5：（拉格郎日定理）设
p是质数，n是非负整数，多项式f(x)?anxn???a1x?a0是一个模p为n次的整系数多项式（即p
an），则同余方程f(x)?0(modp)至多有n个解（在模p有意义的情况下）。
定理6：若l为a对模m的阶，s为某一正整数，满足as?1(modm)，则s必为l的倍数。
以上介绍的只是一些系统的知识、方法，经常在解决数论问题中起着突破难点的作用。另外还有一些小的技巧则是在解决、思考问题中起
着排除情况、辅助分析等作用，有时也会起到意想不到的作用，如：n2??里我们只介绍几个较为直接的应用这些定理的例子。 典例分析
例1.设(91,ab)?1，求证：91|(a12?1(mod8)n为奇数时，2?0(mod9)3整除n时。这
n??0(mod4)n为偶数时??0(mod3)3不整除n时?b12)。
证明：因为91?7?13，故由(91,ab)?1知(91,a)?1，从而(7,a)?1,(13,a)?1，但是?(7)?6,?(13)?12，故由欧拉定理得：a12?(a6)2?12?1(mod7)，a12?1(mod13)，从而a12?1(mod91)；同理，b12?1(mod91)。
12于是，a?b12?1?1?0(mod91)，即91|(a12?b12)。
a的幂an所成的数列：
注明：现考虑整数
a,a2,?,an,?若有正整数k使
ak?1(modm)，则有an?ar(modm)，其中
n?kq?r,0?r?k；
因而关于mod(m)，数列a,a2,?,an,?的项依次同余于a,a2,?,ak,a,a2,?,ak,a,?这个数列相继的k项成一段，各段是完
全相同的，因而是周期数列。如下例： 例2．试求不大于100，且使11|(3nn?7n?4)成立的自然数n的和。
解：通过逐次计算，可求出3关于mod11的最小非负剩余（即为被11除所得的余数）为：
3?3(mod11),32?9(mod11),33?5(mod11),34?5?3?4(mod11),35?4?3?1(mod11)
因而通项为3的数列的项的最小非负剩余构成周期为5的周期数列：
3，9，5，4，1，3，9，5，4，1，………
类似地，经过计算可得7的数列的项的最小非负剩余构成周期为10的周期数列：
7，5，2，3，10，4，6，9，8，1，………
于是由上两式可知通项为3nnn?7n?4的数列的项的最小非负剩余，构成周期为10（即上两式周期的最小公倍数）的周期数列：
3，7，0，0，4，0，8，7，5，6，………
这就表明，当1?n?10时，当且仅当n?3,4,6时，3n?7n?4?0(mod11)，即11|(3n?7n?4)；
又由于数列的周期性，故当10k?1?n?10(k?1)时，满足要求的n只有三个，即
n?10k?3,10k?4,10k?6
从而当1?n?100时，满足要求的n的和为：
?(10k?3)?(10k?4)?(10k?6)??30k?13?30?k?10?13?30?45?130?1480.
k?0k?0k?0999下面我们着重对Fetmat小定理及其应用来举例： 例3．求证：对于任意整数x，证明：令
15137x?x?x是一个整数。 5315117f(x)?x5?x3?x，则只需证15f(x)?3x5?5x3?7x是15的倍数即可。
53155由3，5是素数及Fetmat小定理得x?x(mod5)，x3?x(mod3)，则
3x5?5x3?7x?3x?7x?0(mod5)；3x5?5x3?7x?2x?x?0(mod3)
而（3，5）=1，故3x例4．求证：2730证明：令所以
5?5x3?7x?0(mod15)，即15f(x)是15的倍数。所以f(x)是整数。
|n13?n（n为任意整数）。
f(n)?n13?n，则f(n)?n(n?1)(n?1)(n2?n?1)(n2?n?1)(n6?1)；
f(n)含有因式n7?n,n5?n,n3?n,n2?n
13由Fetmat小定理，知13|n?n,7|n7?n,5|n5?n,3|n3?n,2|n2?n
13又13，7，5，3，2两两互素，所以2730=13?7?5?3?2能整除n?n。
例5．设a,b,c是直角三角形的三边长。如果a,b,c是整数，求证：abc可以被30整除。 证明：不妨设c是直角三角形的斜边长，则c若2 a，2 b，2 c，则c所以2|abc.
若3 a，3 b，3 c，因为(3k若 5 a，5 b，5 c，因为(5k所以a222?a2?b2。
?a2?b2?1?1?0(mod2)，又因为c2?1(mod2)矛盾！
?1)2?1(mod3)，则a2?b2?1?1?2(mod3)，又c2?1(mod3)，矛盾！从而3|abc. ?1)2?1(mod5)，(5k?2)2??1(mod5)，
?b2??2或0(mod5)与c2??1(mod5)矛盾！
从而5|abc.
又(2,3,5)=1，所以30|abc. 下面讲述中国剩余定理的应用
例6．证明：对于任意给定的正整数n，均有连续n个正整数，其中每一个都有大于1的平方因子。 证明：由于素数有无穷多个，故我们可以取n个互不相同的素数
p1,p2,?,pn，而考虑同余组x??i(modp2),i?1,2,?,n ①
因为
p1,p2,?,pn22222显然是两两互素的，故由中国剩余定理知，上述同余组有正整数解。于是，连续n个数x?1,x?2,?,x?n分
2别被平方数
p1,p2,?,pn整除。
注：（1）本题的解法体现了中国剩余定理的一个基本功效，它常常能将“找连续n个正整数具有某种性质”的问题转化为“找n个两两互素的数具有某种性质”，而后者往往是比较容易解决的。
（2）本题若不直接使用素数，也中以采用下面的变异方法：由费尔马数
Fk?2?1(k?0)两两互素，故将①中的pi2转化为
2kFi2(i?1,2,?,n)后，相应的同余式也有解，同样可以导出证明。
例7．证明：对于任意给定的正整数n，均有连续n个正整数，其中每一个都不是幂数。
分析：我们来证明，存在连续n个正整数，其中每一个数都至少有一个素因子，在这个数的标准分解中仅出现一次，从而这个数不是幂数。 证明：取n个互不相同的素数
p1,p2,?,pn，考虑同余组x??i(modp2),i?1,2,?,n
因为
p1,p2,?,pn222显然是两两互素的，故由中国剩余定理知，上述同余组有正整数解。
对于1?i?n因为x?i?pi(modpi2)，故pi2|(x?i)，但由①式可知pi2 (x?i)，即pi在(x?i)的标准分解中恰好出现一次，
故x?1,x?2,?,x?n都不是幂数。
例8． 设n,k是给定的偶数，n?0且k(n?1)是偶数。
证明：存在整数x,y使得(x,n)?(y,n)?1，且x?证明：我们先证明，当n为素数幂
y?k(modn)。
p?时结论成立。实际上，能够证明，存在x,y使
p xy且x?y?k：
若若
p?2，则条件表明k为偶数，此时可取x?1,y?k?1；
p?2，则x?1,y?k?1与x?2,y?k?2中有一对满足要求。
a2p1a1p2?prar,i?1,2,,?,r是n的一个标准分解，上面已经证明，对每个pi存在整数xi,yi使得pixiyi且
一般情形下，设n?xi?yi?k(i?1,2,?r)，而由中国剩余定理，
同余式x同余式
?xi(modpi?i)(i?1,2,?,r) ①有解x，
y?yi(modpi?i)(i?1,2,?,r) ②有解y。
现不难验证解x,y符合问题中的要求：因于是(xy,n)?1，又由①②知x?故x?pixiyi，故pi xy(i?1,2,?r)，
y?xi?yi(modpi?i)(i?1,2,?,r)，
y?k(modn)。
注：此题的论证表现了中国剩余定理最为基本的作用：将一个关于任意正整数n的问题，化为n为素数幂的问题，而后者往往是比较好处理的。 练习： 1．设
p是给定的素数，证明：数列{2n?n}(n?1)中有无穷多项被p整除。
1111f(x)=x5?x4?x3?x为整值多项式。
523302．求证：
3．数列：1，31，331，3331，………中有无穷多个合数。
4．设n为任意给定的正整数，证明：存在连续n个正整数，其中每一个都不是素数的幂。 5．设m,n为正整数，具有性质：等式(11k证明：m?11r?1,m)?(11k?1,n)对所有的正整数k成立。
n，其中r是某个整数。
第六节 不定方程
所谓不定方程，是指未知数的个数多于方程个数，且未知数受到某些（如要求是有理数、整数或正整数等等）的方程或方程组。不定方程也称为丢番图方程，是数论的重要分支学科，也是历史上最活跃的数学领域之一。不定方程的内容十分丰富，与代数数论、几何数论、集合数论等等都有较为密切的联系。不定方程的重要性在数学竞赛中也得到了充分的体现，每年世界各地的数学竞赛吉，不定方程都占有一席之地；另外它也是培养学生思维能力的好材料，数学竞赛中的不定方程问题，不仅要求学生对初等数论的一般理论、方法有一定的了解，而且更需要讲究思想、方法与技巧，创造性的解决问题。在本节我们来看一看不定方程的基础性的题目。 基础知识
1．不定方程问题的常见类型： （1）求不定方程的解； （2）判定不定方程是否有解；
（3）判定不定方程的解的个数（有限个还是无限个）。 2．解不定方程问题常用的解法：
（1）代数恒等变形：如因式分解、配方、换元等；
（2）不等式估算法：利用不等式等方法，确定出方程中某些变量的范围，进而求解；
（3）同余法：对等式两边取特殊的模（如奇偶分析），缩小变量的范围或性质，得出不定方程的整数解或判定其无解； （4）构造法：构造出符合要求的特解，或构造一个求解的递推式，证明方程有无穷多解； （5）无穷递推法。
