二、辗转相除法与裴蜀定理
4、辗转相除法与裴蜀定理
定义 对于整数a，b，若a?b, 则称a是b的约数; 而b是a的倍数. 定义 对于不全为零的整数ai(i?1,2,,n)，若a?ai对i?1,2,,n都成立, 则称a是a1,a2,数.
定义 对于非零整数ai(i?1,2,定义 整数ai(i?1,2,记作(a1,a2,an的公约
,n)，若ai?a对i?1,2,,n都成立, 则称a是a1,a2,an的公倍数.
,n)的公约数中，最大的一个，称为整数ai(i?1,2,,n)的公倍数中，最小的一个，称为整数ai(i?1,2,,n)的最大公约数， ,n)的最小公倍数，
an).
整数ai(i?1,2,记作[a1,a2,an].
定义 若(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 ? b 1 < b，如b1?0，则我们继续
b = q2?b1+ b2 , 0 ? b 2 < b1，如b2 ?0，则我们继续 b1 = q3?b2+b3 , 0 ? b 3 < b2，如b3?0，则我们继续 …
我们知道，由于小于b的自然数是有限的，因此上述过程不可能无穷下去，在有限步之后，应有余数等于零，设在第n+1步余数为零，于是
bn – 2 = qn – 1 ?bn – 1 + bn , 0 ? b n < bn – 1 bn – 1 = q n?b n + 0
上述过程称为辗转相除法，显然(a, b) = (b, b1) = (b1, b2)= (b2, b3) =… = (bn – 1 , b n ) = bn . 由于(a, b) = (a, - b )，从上述过程可以看到，辗转相除法是求两个整数最大公约数的一个很好的方法。
将上述前n个式子联立方程组，消去b1,b2, …, b n – 1 , 则可得到：
u? a + v? b = b n ，其中u, v都是只与q1, q2, … ,qn – 1 有关的整数. 设(a, b) = d，则u? a + v? b = d .于是我们有以下定理：
定理 若ab?0, 设(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 若(ai, bj) =1, i?1,2,m,j?1,2,n,则(a1a2am,bbbn)?1 12性质4 若(a, b) =1, 且n, m是非负整数， 则(an, bm) = 1； 性质5 若m?a, m?b，则m?(a, b) ；
??????性质6 设正整数a, b的质因数分解式如下a = p11?p22?pkk，b = p11?p22?pkk, 其中
1 / 6
?i、?i(i=1,2, … , k)都是非负整数，记ti=min(?i, ?i),si=max(?i, ?i), i=1,2, … , k, 则有 (a, b) = p11?p22?pk性质7 (ma,mb) =|m|(a,b)；[ma,mb]=|m|[a,b] 。 性质8 (tttk；[a, b] = p1s1?p2s2?pksk
ab,)?1 (a,b)(a,b)性质9 若p为素数，则 (p,a)???p,p|a.
?1,pa6、最小非负余数
性质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，则 x2?y2?n2； (3) 若3 xy，则 x2?y2?n2; (4) 若 x2?y2?n2,则6 | xy .
例2设a?2是给定的正整数，那么任一正整数n必可唯一表示为
n?rkak?rk?1ak?1?其中整数k?0, 0?ri?a?1,i?0,1,2,,k,rk?0
*我们称n?rkak?rk?1ak?1?
例3 设p是素数，证明： (1) p|
?ra1?r0
?ra1?r0为n的a进制表示.
Cip,i?1,2,,p?1。
pp?1 (2) 对任意正整数a, p|a?a
(3) 若(a, p) =1，则p|a
例4 设k是正整数，证明：
?1。
(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= p11?p22?pkk，其中?i(i=1,2, … , k)都是非负整数, 求n的正约数个数? (n)。
例7 设正整数n的正约数个数为?(n)，所有这样的约数的和为?(n), 所有这样的约数的积为?(n), 求证：
?(n)?(n)?(1) ?(n) = n2；(2) ?(n) ? 2n；(3)
?(n)n.
???[想一想] 设正整数n的质因数分解式为n= p11?p22?pkk，其中?i(i=1,2, … , k)都是正整数，则n的所有正因数的和为?(n)如何计算.
2 / 6
如何证明(a, b) =1，一般情况下寻找裴蜀定理中的恒等式并不容易，在实际中我们一般采用以下手法：
(Ⅰ)寻找恒等式ua+vb = r，设(a, b) = d，则d?r，由此进一步证明d = 1；
(Ⅱ)寻找适当的r, v，使a?(r – vb), 由此我们得到恒等式ua+vb = r，再采用(Ⅰ)法.
例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，求证直线l：ax+by = c上有整点(x, y)的充要条件是(a, b)?c.
定理 若a, b, c都是整数，且直线l：ax+by = c上有整点(x0, y0)，(a, b) = d, a = md, b =nd, 则直线l上的所
?x?x0?nt有整点为?(t为任意整数) .
y?y0?mt?证明：(a, b) = d, a = md, b =nd ? (m, n) = 1.
容易验证整点(x0+nt, y0 – mt)满足直线l的方程，就是说这样的点都在直线l上.
设(x1, y1)是直线l上任一整数点，则由??ax0?by0?c 得到
?ax1?by1?ca(x1 – x 0) + b(y1 – y 0) = 0 ? m(x1 – x 0) = -n(y1 – y 0) ?m?[-n(y1 – y 0)], 又(m, n) = 1， ? m?(y1 – y 0)
?可设y1 – y 0 = - m t ? y1 = y0 – m t 代入m(x1 – x 0) = -n(y1 – y 0), 得到x1 = x0 + n t 这说明直线l上所有的整点具有(x0+nt, y0 – mt)的形式. 综上所述，定理成立.
例11 设n, a都是正整数，若na不是整数，则na必是无理数.
例12、设a, b是不全为0的整数，一切形如ax+by(x,y?Z)的数中的最小正数是d，求证：d = (a, b).
例13、 设S = {1,2, 3, … , 280}，求最小的正整数n，使得S的每个有n个元素的子集都含有5个两两互质的数.
3 / 6
辗转相除法与裴蜀定理
