1、第五章 数论导引1 素数和数的互素除数 (因子 )的概念 ：设 z为有全体整数而构成的集合，若 b0且 使得 a=mb,此时称 b整除 a.记为 ba,还称 b为 a的 除数 (因子 ).注 :若 a=mb+r且 01被称为 素数 是指 p的因子仅有 1,-1,p,-p。算术基本定理 ：任何一个不等于 0的正整数 a都可以写成唯一的表达式 a P11P22P tt， 这里 P1P2P3P t是素数，其中 i0最大公约数：若 a,b,c z， 如果 ca， cb， 称 c是 a和 b的公约数。正整数 d称为 a和 b的 最大公约数 ，如果它满足 d是 a和 b的公约数。 对 a和 b的任何一个公
2、约数 c有 cd。注 ： 1*. 等价的定义形式是：gcd（ a,b） maxk ka， kb2* 若 gcd（ a,b） =1， 称 a与 b是 互素 的 。 模 算术 全体整数而构成的集合对整数的加法和乘法的两种运算是封闭的且满足算术运算的所有定律，此时我们称整数集合 z为 整数环 。整数环 z对除法运算不封闭。 带余除法：a z,0， 可找出两个唯一确定的整数 q和 r,使 a=qm+r, 01） 分成一些两两不交的等价类。3*.整数模 m同余类共有 m个，他们分别为 mk+0,mk+1, mk+2, mk+(m-1); k z， 每一个算一类，每一类都可以选一个代表元，一般选这一类中的
3、最小的非负整数。于是称 0,1,2, m-1为 标准完全剩余系 。 Z模12的标准剩余系为：0,1,2,3,4,5,6,7,8,9,10,114*. 对于某个固定模 m的同余式可以象普通的等式那样相加相减和相乘：(1)a(mod m)b(mod m)=(ab)(mod m)(2)a(mod m)*b(mod m)=a*b(mod m)例子 .通过同余式演算证明 560 1是 56的倍数， 223 1是 47的倍数。解：注意 53=12513(mod56)于是有 561691(mod56)对同余式的两边同时升到 10次幂，即有 56560-1。其次 , 注意 26=64-30(mod47),于是
4、223=(26)325=(26 26)26 25900*(-30)*(32) mod(47)(7)(-30)*(32) (mod47)1(mod47)于是有 47223-1定理 ： (消去率 )对于 abac（ mod m） 来说，若 (a,m) 1则 bc(mod m)5*.一次同余方程 axb(mod m)这个方程有没有解，相当于问有没有那样一个整数 x， 使得对于某个整数 y来说，有 ax+my=b定理 ：如记 (a,m)=d,则同余方程 axb(mod m)有解的充分必要条件是 db。 当这个条件满足时，恰有 d个模 m同余类中的整数是上述方程的解。 证明：略。（从 ax+my=b入手
5、）6*.整数环 z模正整数 m得到的剩余类集合可以记为 zm(或z/(m) zm=0,1,m-1在 4中已说明 zm对剩余类的加法，乘法是封闭的，可列出它们的加乘表。（见书 214页）。我们称为 zm为 剩余类环 （或 同余类环 ）7*.在整数环 z中是没有零因子的，即两个非零整数的乘积一定不等于 0，但是剩余环则不然。例 z12中： 3*4=12=0说明， zm中的元素可分为两类， 一类是零因子 ，即若 zm,0存在 zm且 0， 有 *=0， 称 ， 都为 zm中的零因子。 另一类是可逆元 ，即若 zm， 存在 zm使 *=1， 此时 ,互为各自的逆元，记 -1=； -1=定理 ：剩余类环
6、 zm中元素 =a为 zm的可逆元 (a,m)=1要证明这个定理，只需证明下列引理：引理 ：任意两个整数 a和 b都有一个最大公约数，这样一个最大公约数 d可以表示成 a,b二数关于整系数的线性组合，即有 s,t z， 使 d sa tb。证明：不妨设 b0， 用辗转相除法，先用 b去除 a， 得a=q1b+r1,0 r2 r3 r4 rk=0是严格递降的一串非负整数，故最后总会出现余数为 0的情形：rk-1=qk+1rk (k+1)所以，进行有限步必停止，此时 d=rk=(a,b)定成立，这是因为1*. 可见 rk为 a和 b的公约数，只要按倒序分析自然有此结论。2*. a和 b的任何一个公
7、约数 c都是 rk的约数，只要按正序分析，自然可知。为证定理的后一部分，将式 (1)做移项有r1=s1a+t1b（ 其中 s1=1,t1= -q1）再将式 (2)右端通过移项变为 r2=s2a+t2b这样一直下去，最后得 d=rk=s*a+t*b, s,t z例子：求 (180， 252)，并将他表示为 180和 252这两个数的一个带整系数的线性组合。解： 252=1*180+72 (1)180=2*72+36 (2)72=2*36 (3)得 (180,252)=36，同时有72=252-1*180 (1 )由 (2)得36=180-2*72 (2 )将 (1)代入 (2 )，即得36=180-2*(250-180) =3*180-2*252
