设a=bq+c,证明：（a,b)=(b,c)关于初等数论中最大公因数和最小公倍数的问题

Question

设a=bq+c,证明：（a,b)=(b,c)
关于初等数论中最大公因数和最小公倍数的问题

Answer 1

证明：设d=(a,b),d'=(b,c) 则d|a,d|b 由定理1可以得出 d|a+(-q)b=c
即d是b,c的共因数
所以 d≤d' 同理可得 d'≤d
即d=d'
定理1：设a,b,c≠0是三个整数,若c|a,c|b,则对任意整数s,t,有c|sa+tb.
定理1：设a,b,c≠0是三个整数,若c|a,c|b,则对任意整数s,t,有c|sa+tb.
证明：∵c|a,c|b ∴a=cq1,b=cq2 (q1,q2为整数）
∴sa+tb=s×cq1+t×cq2=c(sq1+sq2) ∵sq1+sq2为整数
∴c|sa+tb