数学竞赛中的数论问题(6)

a qb r qb b r1 b q 1 r1

r1 a b q 1 M

即M有r1比r更小，这与r为最小值矛盾． 故存在两个实数q,r，使a qb r 0 r b ．

定理2 设a,b,c是三个不全为0的整数，满足a qb c，其中q也为整数，则

a,b b,c ．

证明 设A ｛a,b的公约数｝， B ｛b,c的公约数｝．

任取d A

d|a d|c a bq

d B A B， d|b d|b

d|b d|b

任取d B d A B A，

d|cd|a bq c

得 A B．

有A中元素的最大值 B中元素的最大值，即

a,b b,c ．

注：这是辗转相除法求最大公约数的理论基础．

经典方法：要证明A B，只需证A B且B A． 定理3 对任意的正整数a,b，有 a,b a,b ab．

证明 因为ab是a,b的公倍数，所以a,b的最小公倍数也是ab的约数，存在q使 ab q a,b ，

有

a,b a,b a q且为整数，

b

b

故q是a的约数．同理q是b的约数，即q是a,b的公约数．下面证明，q是a,b的最大公约数．若不然，q a,b ．有

ab q a,b a,b a,b ． ①

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新工程科技数学竞赛中的数论问题(6)全文阅读和word下载服务。