第五章 数论导引 1 素数和数的互素 除数(因子)的概念： 设z为有全体整数而构成的集合，若 b≠0且 使得a=mb,此时称b整除a.记为b∣a,还称b为a的除数(因子). 注:若a=mb+r且0<r<b,此时b不整除a,记为b┼a 素数(质数)的概念: 整数p>1被称为素数是指p的因子仅有1,-1,p,-p。

§算术基本定理： 任何一个不等于0的正整数a都可以写成唯一的表达式a＝P1α1P2α2…Ptαt，这里P1>P2>P3…>Pt是素数，其中αi>0 §最大公约数： 若a,b,c∈z，如果c∣a，c∣b，称c是a和b的公约数。正 整数d称为a和b的最大公约数，如果它满足 d是a和b的公约数。 对a和b的任何一个公约数c有c∣d。 注：1*. 等价的定义形式是： gcd（a,b）＝max{k∣ k∣a，k∣b} 2*．若gcd（a,b）=1，称a与b是互素的。

模 算术 全体整数而构成的集合对整数的加法和乘法的两种运算 是封闭的且满足算术运算的所有定律，此时我们称整数 模 算术 全体整数而构成的集合对整数的加法和乘法的两种运算 是封闭的且满足算术运算的所有定律，此时我们称整数 集合z为整数环。整数环z对除法运算不封闭。 带余除法： a∈z,>0，可找出两个唯一确定的整数q和r, 使a=qm+r, 0<=r< m,q和r这两个数分别称为以m去除a所得到的商数和余数。 (若r=0则m∣a） 整数同余式和同余方程： 定义（同余）称整数a模正整数m同余于整数b，并写a≡b（mod m）是指m∣a－b, m称为模数。 注：1*.m∣a-ba=q1m+r,b=q2m+r即a和b分别 除以m有相同的余数。“同余”二字的来源就在于此。

2*.相对于某个固定模数m的同余关系，是整数间的一种等价关系。具有等价关系的三点基本性质： 自反性：对任意整数a有a≡a（modm） 对称性：如果a≡b(modm)则b≡a（modm） 传递性：如果a≡b (modm）b≡c（modm）则a≡c(modm) 于是，全体整数集合z可按模m（m>1）分成一些两两不交的等价类。 3*.整数模m同余类共有m个，他们分别为mk+0,mk+1, mk+2,…mk+(m-1); k∈z，每一个算一类，每一类都可以选一个代表元，一般选这一类中的最小的非负整数。于是称[0],[1],[2],…[m-1]为标准完全剩余系。Z模12的标准剩余系为：[0],[1],[2],[3],[4],[5],[6],[7],[8],[9],[10],[11]

4*. 对于某个固定模m的同余式可以象普通的等式那样相加相减和相乘： (1)a(mod m)±b(mod m)=(a±b)(mod m) (2)a(mod m)*b(mod m)=a*b(mod m) 例子.通过同余式演算证明560－1是56的倍数，223－1是47的倍数。 解： 注意53=125≡13(mod56) 于是有56≡169≡1(mod56) 对同余式的两边同时升到10次幂， 即有56∣560-1。 其次, 注意26=64≡-30(mod47), 于是

223=(26)3·25=(26 · 26)26 · 25 ≡900*(-30)*(32) mod(47) ≡(7)(-30)*(32) (mod47) ≡1(mod47) 于是有 47∣223-1 定理：(消去率)对于ab≡ac（mod m）来说，若(a,m)＝1则b≡c(mod m) 5*.一次同余方程ax≡b(mod m)这个方程有没有解，相当于问有没有那样一个整数x，使得对于某个整数y来说，有ax+my=b 定理：如记(a,m)=d,则同余方程ax≡b(mod m)有解的充分必要条件是d∣b。当这个条件满足时，恰有d个模m同余类中的整数是上述方程的解。 证明：略。（从ax+my=b入手）

6*.整数环z模正整数m得到的剩余类集合可以记为zm(或z/(m)) zm={[0],[1],…,[m-1]} 说明，zm中的元素可分为两类，一类是零因子，即若α∈zm,α≠[0]存在β∈zm且β≠[0]，有α*β=[0]，称α，β都为zm中的零因子。另一类是可逆元，即若α∈zm，存在β∈zm使α*β=[1]，此时α,β互为各自的逆元，记α-1=β；β-1=α

定理：剩余类环zm中元素α=[a]为zm的可逆元(a,m)=1 要证明这个定理，只需证明下列引理： 引理：任意两个整数a和b都有一个最大公约数，这样一个最大公约数d可以表示成a,b二数关于整系数的线性组合，即有s,t∈z，使d＝sa＋tb。 证明：不妨设b>0，用辗转相除法，先用b去除a，得 a=q1b+r1,0<=r1<b; (1) 如果r1=0，停止，否则再用r1去除b，得 b=q2r1+r2,0<=r2<r1; (2) 如果r2=0，停止，否则再用r2去除r1，得 r1=q3r2+r3;0<=r3<r2; (3) 等等，这样一直进行下去，可得一系列关系式： rk-3=qk-1rk-2+rk-1,0<=rk-1<rk-2; (k-1) rk-2=qkrk-1+rk,0<=rk<rk-1; (k)

由于历次所得的余数 r1> r2 >r3 >r4 >…rk>…>=0 是严格递降的一串非负整数，故最后总会 出现余数为0的情形： rk-1=qk+1rk (k+1) 所以，进行有限步必停止，此时d=rk=(a,b)定成立，这是因为 1*. 可见rk为a和b的公约数，只要按倒序分析自然有此结论。 2*. a和b的任何一个公约数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

3 Format定理和Euler定理 § Format定理：如果p是素数并且a是正整数,p┼a，那 么，ap-1≡1(mod p) 证明： z*p≡{α∈zp∣(α,p)=1} 易见，z*p={1,2,3,…,(p-1)}且因为（a,p）＝1知 a z*p={[a],[2a],[3a],…,[(p-1)a]}= z*p，原因是a z*p内的元素两两不同。他们刚好为1，2，3…，（p－1）的一个排列。所以 [a]*[2a]*[3a]*…[(p-1)a]≡1*2*3*…(p-1)(modp) 由 （(p－1)！，p）＝1， 所以 ap-1≡1(modp) 注：易见对（a，p）＝1 有ap≡a(modp)

§ Euler φ函数 定义(Eulerφ函数φ(n))： φ(n)是这样来定义的，当n＝1 时，φ(1)＝1；当n>1时，它的值φ(n)等于比n小而与n互素的正整数的个数。 以n＝24为例，比24小而与24 互素的正整数为：1，5，7，11，13，17，19，23 因此，我们有φ(24)＝8。易见，若p为素数，则φ(p)＝p－1。 注：1*.若p，q都为素数且p≠q，此时有 φ(pq)＝φ(p)φ(q)=（p－1）（q－1） 证明：考虑zpq剩余类的集合是{0，1，2，…，（pq-1）}集合中与pq不互素的元素子集为{p,2p,…,(p-1)q}和子集 {q,2q,…(p-1)q}以及0，于是若设n＝pq，有 φ(n)=pq-[(q-1)+(p-1)+1] =(p-1)(q-1)=φ(p)φ(q)

例：φ(21)=φ(3*7)=φ(3)φ(7)=2*6=12. 2*.设n= p1e1p2e2…prer，其中p1,p2,…,pr为互异素数，则φ(n)= p1e1-1p2e2-1…prer-1(p1-1)(p2-2)…(pr-1) =n(1-1/p1) (1-1/p2) (1-1/p3)… (1-1/pr) 3*.Euler公式 证明：考虑1/n,2/n,…n/n，然后化简成既约分数，分母为d的一类分数有φ(d)个，于是 §欧拉定理（Euler）： 若整数a于整数n互素，则aφ(n)≡1(mod n) 证明：设小于n而和n互素的个正整数为 r1,r2,r3…,rφ(n) (1)

他们是模n两两互不同余的。对每一个定数i来说，由于a和ri都与n互素，所以(ari,n)=1， 所以ari同余于（1）中的某个ri’即 ari≡ri’(mod n)，1<=i<=φ(n) 并且当i≠j时有ari /≡arj(mod n).于是, 为 的置换.所以有 由(ri,n)=1, 所以 注：1*. n＝p时，有ap-1≡1(mod p)为Format定理！ 2*.易见aφ(n)+1≡a(mod n) 3*.若n=pq，p与q为相异素数，取0<m<n，若（m,n）＝1，有mφ(n)+1≡m(mod n)，也即m(p-1)(q-1)+1≡m(mod n).

4. 对于3中，若(m，n)＝p，或q，书中P220－P221给出了详细讨论。也同样有mφ(n)+1≡m(mod n) 5 4*.对于3中，若(m，n)＝p，或q，书中P220－P221给出了详细讨论。也同样有mφ(n)+1≡m(mod n) 5*.由 (mφ(n))k≡1k(mod n) 知 mkφ(n)≡1(modn)， 进一步 mkφ(n)+1≡m(mod n) mk(p-1)(q-1)+1≡m(mod n)

4 中国剩余定理 例子：（孙子算经）今有物不知其数。三三数之余二；五五数之余三；七七数之余二。问物几何？ 答曰：二十三。 23≡2*70+3*21+2*15(mod 105) （口诀：三人同行七十稀，五树梅花廿一枝， 七子团圆月正半，除百零五便得知。） 问，70，21，15如何得到的？ 原问题为： 求解同余方程组

注意：若x0为上述同余方程组的解，则x0=x0+105 注意：若x0为上述同余方程组的解，则x0=x0+105*k(k∈z) 也为上述同余方程组的解。有意义的是，解题口诀提示我们先解下面三个特殊的同余方程组 (1) (2) (3) 的特殊解 =? =? =? 以方程（1）为对象，相当于解一个这样的同余方程 35y≡1(mod 3)，为什么呢？ 原因是，从（1）的模数及条件知，x应是35的倍数，于 是可以假设x＝35y有

35y≡1(mod 3)相当于2y≡1(mod)3 解出y=2（mod3） 于是x35*2 70(mod105) 类似地得到（2）、（3）方程的模105的解21、15。 于是有 得

中国剩余定理：设自然数m1,m2,…mr两两互素，并记N=m1m2…mr，则同余方程组

证明：考虑方程组， (1<=i<=r) 由于诸mi(1<=i<=r)两两互素，这个方程组作变量替换，令x=(N/mi)*y，方程组等价于解同余方程： (N/mi)y≡1(mod mi)

若要得到特解yi,只要令 xi=(N/mi)yi 则方程组的解为 x0=b1x1+ b2x2+ …+ brxr (mod N) 模N意义下唯一。