问关于"辗转相除求最大公约数"

题目

问关于"辗转相除求最大公约数"
例如求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
各项均位正整数.
我想问的是,为什么余数里面一定就包含了两数的最大公约数

答案

首先,求a与b的最大公约数．可以设最大公约数为q,那么a＝nq,b＝mq（a＞b）
a＝b＊k＋x
即x＝a－bk＝q（n－bk）
因为n－bk＞0
所以余数里面一定就包含了两数的最大公约数