神马品牌网杨利伟简介事迹:问关于"辗转相除求最大公约数"
来源：百度文库 编辑：神马品牌网 时间：2024/04/29 15:41:08
例如求155和35的最大公约数,可以用35除155如下:
155=35*4+15
35=15*2+5
15=5*3+0
则155和35的最大公约数是5
解释是设最大公约数是a,则155/a=5*3/a+15/a
各项均位正整数.
我想问的是,为什么余数里面一定就包含了两数的最大公约数
155=35*4+15
35=15*2+5
15=5*3+0
则155和35的最大公约数是5
解释是设最大公约数是a,则155/a=5*3/a+15/a
各项均位正整数.
我想问的是,为什么余数里面一定就包含了两数的最大公约数
首先,求a与b的最大公约数．可以设最大公约数为q，那么a＝nq，b＝mq（a＞b）
a＝b＊k＋x
即x＝a－bk＝q（n－bk）
因为n－bk＞0
所以余数里面一定就包含了两数的最大公约数