如下方法不需要算术基本定理
首先一个结论就是,如果a,b互质的充要条件是:必有m,n为整数,使得am+bn=1.这个结论的证明是:
必要性:
辗转相除法:
设两数为a、b(b＜a),求它们最大公约数d的步骤如下：用b除a,得a＝bq1＋r1（0≤r＜b）.若r1=0,则(a,b)＝b；若r1≠0,则再用r1除b,得b＝rq2＋r2（0≤r2＜r1）.若r2＝0,则(a,b)＝r1,若r2≠0,则继续用r2除r1,……如此下去,直到能整除为止.其最后一个非零余数即为d.
根据辗转相除可以得到：
a=bq1+r1(0