初等数论总复习题及知识点总结(4)

用整除来定义即 m∣a-b 。②用等号来定义a=b+mt 。值得注意a和b关于m同余是个相对概念。即它是相对于模m来讲，二个整数a和b关于一个整数模m同余。则对于另一个整数模m1，a和b未必会同余。

从定义上看，同余和整除是同一个事情，但引进了新的符号“三”后，无论从问题的叙述上，还是解决问题的方法上都有了显著的变化，同时也带来了一些新的知识和方法。在引进了同余的代数性质和自身性质后，同余符号“三”和等号“=”相比，在形式上有几乎一致的性质，这便于我们记忆。事实上在所有等号成立的运算中，只有除法运算是个例外，即除法的消去律不成立。为此对于同余的除法运算我们有二种除法：

（i）模不改变的除法，若ak≡bk(mod m) ，(k,m)=1，则a≡b(mod m)

m??(ii)模改变的除法, 若ak≡bk(mod m) (k,m)=d,则a≡b?mod? a??这一点读者要特别注意。

完全剩余系和简化剩余系是二个全新的概念，读者只要搞清引成这些概念的过程。因为同余关系是一个等价关系，利用等价关系可以进行将全体整数进行分类，弄清来胧去脉，对于更深刻理解其本质是很有好处的。完全剩余系或简化剩余系是一个以整数为元素的集合，在每个剩余类各取一个数组成的m个不同数的集合，故一组完全剩余系包含m个整数，由于二个不同的剩余类中的数关于m两两不同余，故可得判别一组数是否为模m的一个完全剩余系的条件有二条为

（1） 个数=m （2） 关于m两两不同余 另外要能用已知完全剩余系构造新的完全剩余系。即有定理 设（a，m）=1，x为m的完全剩余系，则ax+b也是m的完全剩余系。 当(m1,m2)?1时，能由m1的完全剩余系和m2的完全剩余系，构造m1m2完全剩余系。 为讨论简化剩余系，需要引进欧拉函数φ(m)，欧拉函数φ(m)定义为不超过m且与m互素的正整数的个数，记为φ(m)，要掌握φ(m)的计算公式，了解它的性质。这些性质最主要的是当（a ,b）=1时，φ(ab) = φ(a) φ(b)，和?(p)?p

???p??1 16

现在在剩余类中把与m互素的集合分出来，从中可在各个集合中任取一个数即可构造模m的一个简化剩余系。另一方面，简化剩余数也可从模m的一个完全剩余系中得到简化剩余系，一组完全剩余系中与m互素的的数组成的φ(m)个不同数的集合称为m简化剩余系。同样简化剩余系也有一个判别条件。

判别一组整数是否为模m的简化剩余系的条件为 （2） 个数=φ(m) （3） 关于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)

除此以外，欧拉定理的证明的思想是非常好的，在各个地方都有应用。就欧拉定理、费尔马小定理来讲，它在某些形如an数的整除问题应用起来显得非常方便。同余方法也是解决整除问题的方法之一。

另外同余方法在证明不定方程时也非常有用，即要掌握同余“三”和相等“=”的关系：相等必同余，同余未必相等，不同余肯定不相等。

对于特殊数的整除规律要求能掌握其一般定理的证明，并熟记一些特殊数的整除规律 1、

一个整数被2整除的充要条件是它的末位为偶数。 17

2、 3、 4、 5、 6、 7、 一个整数被3整除的充要条件是它的各位数字之和能被3整除。 一个整数被9整除的充要条件是它的各位数字之和能被9整除。 一个整数被5整除的充要条件是它的末位为0或5。 一个整数被4，25整除的充要条件是它的末二位能被4，25整除。 一个整数被8，125整除的充要条件是它的末三位能被8，125整除。 设a?an1000n?an?11000n?1??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≡(32)2·32≡-19×9≡-171≡29(mod 100) ∴ 末二位数为29。

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

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

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

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

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

18

若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

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

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

有5y+3≡x2(mod 5) 即3≡x2(mod 5)

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

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

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

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

100000b=4263.6.3.，99000b=4263-42 b=?4221=4699900011000。

当然也可用直化分数的方法做。

19

例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这三个数

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

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

? 第四章 同余式 一、主要内容

同余方程概念及次数、解的定义，一次同余方程ax≡b(mod m)有解的充分必要条件，一次同余方程组，孙子定理，高次同余方程，素数模的同余方程，威尔逊定理。

20

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库初等数论总复习题及知识点总结(4)在线全文阅读。