二、辗转相除法与裴蜀定理4、辗转相除法与裴蜀定理定义 对于整数a, b,若a|b,则称a是b的约数；而b是a的倍数.定义 对于不全为零的整数a (i = 1,2, , n)，若a| a对i = 1,2, , n都成立，则称a是a , a , a的公约i i 1 2 n数.定义 对于非零整数a (i = 1,2, ,n)，若a |a对i = 1,2, ,n都成立，则称a是a ,a , a的公倍数.i i 1 2 n定义 整数a (i = 1,2, ,n)的公约数中，最大的一个，称为整数a (i = 1,2, ,n)的最大公约数，i ••• • • • i •••记作(a ,a , a ).1 2 n ... ...整数a (i = 1,2, ,n)的公倍数中，最小的一个，称为整数a (i = 1,2, ,n)的最小公倍数，• i • i记作[a ,a , a ].1 2 n ••• •••定义 若(a, b) =1,则称a, b互质或互素.显然有下列性质：性质 1 (a, b) = (b,a) = (a, -b) = (-a, -b) ； 性质 2 |a-b | = (a, b) - [a, b],特别地当 a>0, b>0 时，a-b = (a, b) - [a, b].面我们介绍辗转相除法与裴蜀定理 定理若 a = qb+r，则(a, b) = (b, r).注：本定理也可写成：(a, b) = (a - bq , b),就是说，在计算(a, b)时，可用b的任意整数倍数bq去减a.下面我们介绍辗转相除法，对于给定的整数a, b (b>0)，我们反复运用带余除法就有： a = q1-b + b1,0 < b1< b，如b产0，则我们继续 b = q2-b]+ b2,0 < b2< 耳，如 b2 H0，则我们继续 b1 = q3-b2+b3,0 < b3< b2，如 b3H0，则我们继续…我们知道，由于小于b的自然数是有限的，因此上述过程不可能无穷下去，在有限步之后，应有余数 等于零，设在第 n+1 步余数为零，于是bn- 2= qn- 1 -bn- 1 + S , 0 < bn< S- 1bn 1 = qn-b n + 0 上述过程称为辗转相除法，显然(a, b) = (b, b1) = (b1, b2)= (b2, b3) =... = (b 1 , b ) = b .由于(a, b) = (a,- b )，从上述过程可以看到，辗转相除法是求两个整数最大公约数的一个很好的方法。
将上述前n个式子联立方程组，消去b1,b2,…,b ]，则可得到：u- a + v- b = bn，其中u, v都是只与q1, q2, ... ,qn_ 1有关的整数.设(a, b) = d，则u- a + v- b = d .于是我们有以下定理：定理 若abH0,设(a, b) = d，则存在整数u, v，使得u- a + v- b = d .[注]定理中的u, v不唯一.裴蜀定理(a, b) = 1的充要条件是存在整数u, v使得u- a + v- b =1.并且若ab>0，则可以选择u>0，v< 0 或 u<0，而 v>0 .证明：必要性显然，下面证明充分性.对于整数a, b，存在整数u, v使得u- a + v- b =1，我们设(a, b) = d，则d | a, d | b， 于是d | 1，又d>1， 所以 d = 1，即(a, b) = 1.若ab>0，则a,b同号，所以要使u- a + v- b =1成立，u, v必须异号，所以u>0，v< 0或u<0，而v>0. 综上所述，裴蜀定理成立.5．最大公约数与最小公倍数的性质性质 1 若(a, b) =1,且 a | bc，则 a | c；性质 2 若(a, b) =1,则(a, bc) = (a, c)；性质 3 若(a., b.) =1, i = 1,2, m, j = 1,2, n，则(aa a ,bb b ) = 1i j 1 2 m 1 2 n性质4若(a, b) =1,且n, m是非负整数，则(an, bm) = 1；性质5若m|a, m|b，则m|(a, b)； … … …性质6设正整数a, b的质因数分解式如下a = pfi - p2" 2…pk a k ,b = p1卩1 - p 2卩2…pk卩k ,其中吟 卩2=1,2, , k)都是非负整数，记 ti=min(ai, Pi),si=max(ai,卩J, i=l,2, ... , k,则有(a, b) = p1ti - p212 …pjk ； [a, b] = p1 si - p2s2 …pksk性质 7性质 8(ma,mb) =|m|(a,b)；(命侖)=1[ma,mb]=|m|[a,b] 。
p, p I a性质9若p为素数，则(p,a) = .1, p a ”6、最小非负余数 "性质1两个4k+3形式的数的乘积一定是4k+1形式的数；性质 2 一个平方数被4除，所得的最小非负余数只可能是0， 1； 性质 3 一个平方数被8除，所得的最小非负余数只可能是0， 4； 性质4 一个平方数被3除，所得的最小非负余数只可能是0， 1； 性质5 一个平方数被9除，所得的最小非负余数只可能是0， 1， 8从上述性质我们容易知道：对任意整数x, y，有x2 + y2丰4k + 3；x2 + y2丰8k + 3,8k + 6,8k + 7 ；x3 + y3 主 9k + 3,9k + 4,9k + 5,9k + 6.例1对任意整数x, y,证明：(1) 8] x2 -y2 -2; (2)若 2*xy,贝U x2 + y2 主 n2；(3)若 3[ xy,贝I」x2 + y2 主 n2; (4)若 x2 + y2 = n2，则 6 | xy .例2设a>2是给定的正整数，那么任一正整数n必可唯一表示为n = r ak + r ak-1 + + ra + rk k -1 1 0其中整数 k>0, 0 < r < a -1,i = 0,1,2, ,k, r 丰 0i k ・・・*我们称n = rak + r ak-1 + + ra + r为n的a进制表示.k k-1 1 ・0・例3设p是素数，证明：•…(1) p | C i, i = 1,2, , p -1。
p(2) 对任意正整数a,.p | ap 一a(3) 若(a, p) =1,则 p I ap-1 -1例4设k是正整数，证明：(1) (ak, bk) = (a, b)k;(2) 设 a, b 是正整数，(a, b) =1, ab = ck 则 a = (a, c)k, b = (b, k)k .例5设p是素数，(a, b) = p,求(a2, b), (a3,b), (a2, b3)所可能取的值.例6设正整数n的质因数分解式为n= p1a 1 - p2a2…pk以k，其中％(i=1,2, , k)都是非负整数，求n的正约数个数t (n)例7设正整数n的正约数个数为T(n),所有这样的约数的和为c(n),所有这样的约数的积为兀(n),求证:(1)兀(n) = n 2Q(n)、 ■—⑵ T(n) < 2i.；n ； (3) > *n.t (n)［想一想］设正整数n的质因数分解式为n= p1a1 - p2a2…pkak，其中％(i=1,2,…,k)都是正整数，则n 的所有正因数的和为Q(n)如何计算.如何证明(a, b) =1, 一般情况下寻找裴蜀定理中的恒等式并不容易，在实际中我们一般采用以下手法：(I) 寻找恒等式ua+vb = r,设(a, b) = d,则d | r，由此进一步证明d = 1；(II) 寻找适当的r, v,使a | (r - vb),由此我们得到恒等式ua+vb = r,再采用(I )法.例 8 证明(1)(n!+1, (n+1)!+1) = 1; (2)(21n+4, 14n+3)=1;(3) m>0, n>0,且 m 为奇数，则(2m —1,2n +1)二 1.例 9 设 m, n, a 都是正整数，且 a>2,求证：(am — 1 , an - 1 ) = a(m，n) - 1 . 注：更一般地有：设 a>b, (a, b)=1,则(am — bm , an - bn ) = a(m ‘ n) - b(m,n).例10已知a, b, c都是整数,a2+b2工0,求证直线1： ax+by = c上有整点(x, y)的充要条件是(a, b) | c.定理 若a, b, c都是整数，且直线1： ax+by = c上有整点(x。
y0), (a, b) = d, a = md, b =nd,则直线1上的所I x =兀门+ nt有整点为< 0 (t为任意整数).Iy — y 0—mt证明：(a, b) = d, a = md, b =nd n (m, n) = 1.容易验证整点(x0+nt, y0 - mt)满足直线1的方程，就是说这样的点都在直线1上.设(X], y1)是直线1上任一整数点,a(X] — x °) + b(y1 - y 0) = 0 n m(X] — x 0) = -n(y1 - y0)•••m | [-n(y1 — y 0)],又(m, n) = 1, /. m| (y1 — y 0)•••可设 y1 - y 0 = - m t n y1 = y0 - m t 代入 m(x1 - x 0) = -n(y1 - y0),得到 x1 = x n t 这说明直线1上所有的整点具有(x0+nt, y0 - mt)的形式.综上所述,定理成立.例11设n, a都是正整数，若不是整数，则拓必是无理数.例12、设a, b是不全为0的整数，一切形如ax+by(x,yeZ)的数中的最小正数是d求证：d = (a, b).例13、设S = {1,2, 3, ... , 280},求最小的正整数n,使得S的每个有n个元素的子集都含有5个两两互质 的数.参考答案1、略；2、略；3、证明：(1)P!i!(p -i)!(P -1)!i!(p - i)!P，i 二 1,2,,p -1C c Z,i = 1,2, , p —1,「. i!(p - i)!l[ p - (p — 1)!]p又-p 是素数，••• (p,i!(p -i)!) = 1 i = 1,2, , p — 1i!(p-i)!l(p-1)!,即.伫)：c Z,i = 1,2, ,p-1• • •p I Ci, i = 1,2, , p -1p⑵ 对a用数学归纳•法证明结合(1)容易证明；(3) 由(2)及性质1 容易证明.4、证明：(1) (ak,bk) =(a,b)k(a, b)'(a, b)丿=1,.仃 、aI (a,b)丿 仃 、 a I (a, b) ?'b.(a, b)丿丿‘丄](a,b)丿丿、k=1 .(ak ,bk )= (a(2) a = a(ak-i,b) = (ak,ck) = (a,c)k ； b = b(bk-i,a) = (b,c) = (b,c)k5、解：*・'(a, b) = p .可设 a = pa],b = pb]且(什,£)=则(a2, b) = (p2a 2, pb ) = p(pa ,b ) = p(p,b ) = p 或 p21 1 1 1 1(a3,b)= (p3a 3,pb )。