为讨论简化剩余系，需要引进欧拉函数φ(m)，欧拉函数φ(m)定义为不超过m且与m互素的正整数的个数，记为φ(m)，要掌握φ(m)的计算公式，了解它的性质。这些性质最主要的是当（a ,b）=1时，φ(ab) = φ(a) φ(b)，和?(p)?p???p??1 现在在剩余类中把与m互素的集合分出来，从中可在各个集合中任取一个数即可构造模m的一个简化剩余系。另一方面，简化剩余数也可从模m的一个完全剩余系中得到简化剩余系，一组完全剩余系中与m互素的的数组成的φ(m)个不同数的集合称为m简化剩余系。同样简化剩余系也有一个判别条件。

判别一组整数是否为模m的简化剩余系的条件为 （1） 个数=φ(m) （2） 关于m两两不同余 （3） 每个数与m互素 关于m的简化剩余系也能用已知完全剩余系构造新的简化剩余系。 设（a，m）=1，x为m的简化剩余系，则ax也是m的简化剩余系。 当(m1,m2)?1时，能由m1的简化剩余系和m2的简化剩余系，构造m1m2简化剩余系。

欧拉定理、费尔马小定理是同余理论非常重要的定理之一。要注意欧拉定理和费尔马定理的条件和结论。

欧拉定理：设m为大于1的整数，（a，m）=1，则有 a?(m)?1(modm) 费尔马小定理：若p是素数，则有 ap?a(modp)

除此以外，欧拉定理的证明的思想是非常好的，在各个地方都有应用。就欧拉定理、费尔马小定理来讲，它在某些形如a数的整除问题应用起来显得非常方便。同余方法也是解决整除问题的方法之一。 另外同余方法在证明不定方程时也非常有用，即要掌握同余“三”和相等“=”的关系：相等必同余，同余未必相等，不同余肯定不相等。

对于特殊数的整除规律要求能掌握其一般定理的证明，并熟记一些特殊数的整除规律 1、 一个整数被2整除的充要条件是它的末位为偶数。 2、 一个整数被3整除的充要条件是它的各位数字之和能被3整除。 3、 一个整数被9整除的充要条件是它的各位数字之和能被9整除。 4、 一个整数被5整除的充要条件是它的末位为0或5。 5、 一个整数被4，25整除的充要条件是它的末二位能被4，25整除。 6、 一个整数被8，125整除的充要条件是它的末三位能被8，125整除。 7、 设a?an1000?an?11000nn?1n??a0，则7或11或13整除a的充要条件是7或11或13整除(a0?a2??)?(a1?a3??)

五、例子选讲

例1：求3406的末二位数。 解：∵ （3，100）=1，∴3

?(100)≡1（mod 100）

?(100)= ? (22·52)=40, ∴ 340≡1(mol 100)

∴ 3406=(340)10·36≡(3)·3≡-19×9≡-171≡29(mod 100) ∴ 末二位数为29。

22

2

例2：证明（a+b）≡a+b(mod p)

pp证：由费尔马小定理知对一切整数有：a≡a（p），b≡b(P)，

pp由同余性质知有：a+b≡a+b(p) 又由费尔马小定理有（a+b）p≡a+b (p)

pp（a+b）p≡a+b(p)

P例3：设素数p>2，则2-1的质因数一定是2pk+1形。 证：设q是2-1的质因数，由于2-1为奇数，∴ q≠2，

∴ （2·q）=1,由条件q|2-1,即2≡1（mod q），又∵ （q,2）=1，2≡1（mod q） 设i是使得2≡1（mod p）成立最小正整数 若1

又∵ q-1为偶数，2|q-1,

∴ 2p|q-1,q-1=2pk , 即q=2pk+1

例4：证明13|42n+1+3n+2

证：∵42n+1+3n+2≡4·16n+9·3n

·

≡3n (4+9)≡13×3n≡0(13)

∴ 13|42n+1+3n+2

2

例5：证明5y+3=x无解

2

证明：若5y+3=x有解，则两边关于模5同余

2

有5y+3≡x(mod 5)

2

即3≡x(mod 5)

2

而任一个平方数x≡0,1,4(mod 5)

xp

p

pppppp∴ 30,1,4(mod 5)

2

∴ 即得矛盾，即5y+3=x无解

......1被7除的余数。 例6：求11?????50......1≡11（mod 7）≡4（mod 7）解：∵111111被7整除，∴11，即余数为4。 ?????50

例7：把0.04263化为分数。 解：设b=0.04263，从而1000b=42.63,

100000b=4263.63，99000b=4263-42 b=?4221469=。 9900011000........当然也可用直化分数的方法做。

例8：设一个数为62XY427是9，11的倍数，求X，Y 解：因为9|62XY427

所以9|6+2+X+Y+4+2+7， 即9|21+X+Y

又因为11|62XY427， 有11 |（7+4+X+6-2-Y-2） 即11|（X-Y+13）

因为0?X，Y?9， 所以有21? 21+X+Y?39， 4 ? X-Y+13 ?22，由此可知 21+X+Y=27，X-Y+13=11 或21+X+Y=36，X-Y+13=22 X+Y=6，X-Y=-2

或X+Y=15，X-Y=9，解得X=2，Y=4。

例9：证明：8a+7不可能是三个整数的平方和。

证：由于每一个整数对于8，必同余于0，1，2，3，4，5，6，7这八个数之一

注意到对于模8，有

02?0,12?1,22?4,32?1, 42?0,52?1,62?4,72?1,

因而每一个整数对于模8，必同余于0，1，4这三个数

不能x,y,z如何变化，只能有x?y?z?0,1,2,3,4,5,6(mod8) 而8a?7?7mod8)，故8a?7不同余于x?y?z关于模8

2222222228a?7?x2?y2?z2，从而证明了结论。

第二章 不定方程

一、 主要内容

一次不定方程有解的条件、解数、解法、通解表示，不定方程x2+y2=z2通解公式、无穷递降法、费尔马大定理。 二、 基本要求

1、 了解不定方程的概念，理解对“解”的认识，掌握一次不定方程ax?by?c有解的条件，能熟

练求解一次不定方程的特解，正整数解及通解。了解多元一次不定方程a1x1?a2x2??anxn?c有解的条件，在有解的条件下的解法。

2、掌握不定方程x2+y2=z2在一定条件下的通解公式，并运用这个通解公式作简单的应用。 3、对费尔马大定理应有在常识性的了解，掌握无穷递降法求证不定方程x4+y4=z2无解的方法。 4、掌握证明不定方程无解的若干方法。

三、难点和重点

（1）重点为求解一次不定方程的方法 （2）掌握第二节中引证的应用。 （3） 费尔马无穷递降法。

四、自学指导

不定方程主要讲解以下几个问题 （i）给定一类不定方程，判别在什么条件下有解。 （ii）在有解的条件下，有多少解 （iii）在有解的条件下，求出所给的不定方程的所有解。 二元一次不定方程的一般形式为ax+by=c 。若(a ,b)∣c，则该二元一次不定方程一定有解，若已知一个特解，则一切解可以用公式表示出来，因此求它的通解只要求出一个特解即可。求解二元一次不定方程的一个通解有好多种方法。读者应该总结一下，各种方法都有独到之处。特别要指出用最大公因数的方法。它的根据是求（a ,b）时所得的结果。由于注意通解公式x=x0-b1t，y=y0+a1t中a1，b1的意义和位置。以免出错。

多元一次不定方程a1x1?a2x2??anxn?c也有类似的结果，但在求解的过程中将它转化二元一次不定方程组，从最后一个二元一次不定方程解起，可逐一解出x1 ,x2 ,??xn 。所用的方法一般选择最大公因数的方法。由于n元一次不定方程可转化为n-1个二元一次不定方程组，故在通解中依赖于n-1个任意常数。但不象二元一次不定方程那样有公式来表示。

x2+y2=z2的正整数解称为勾股数，在考虑这个方程时，我们对（x ,y）作了一些限制，而这些限制并不影响其一般性。在条件x>0，y>0，z>0，（x，y）=1，2∣x的条件可以给出x2+y2=z2的通解公式，x=2ab，y=a2-b2，z2=a2+b2，a>b>0 , (a ,b)=1，a ,b一奇一偶。若将2∣x限为2∣y，则也有相应的一个通解公式。

222

在证明这个通解公式的过程中，用到了引理 uv=w，u>0，v>0，（u ,v）=1，则u=a，v=b，w=ab 。a>0，b>0，（a ,b）=1 。利用这个结论可以求解某些不定方程。特别当w=1或素数p 。则由uv=1或uv=P 可将原不定方程转化为不定方程组。从而获得一些不定方程的解。上述解不定方程的方法叫因子分解法。