题目

数论:给定x和y,且m=ax+by,n=cx+dy,ad-bc=±1,求证(m,n)=(x,y)

提问时间：2020-10-29

答案

(x,y)|x,(x,y)|y,而m=ax+by,n=cx+dy,于是 (x,y)|m,(x,y)|n ==> (x,y)|(m,n)
另一方面：
dm=adx+bdy
bn=cbx+bd y
相减 得：
dm-bn =±x
cm=acx+bcy
an=acx+ad y
相减 得：
-cm+an =±y
于是,类似最上面的推理,可得：(m,n) | (x,y)
都是正数,于是 (m,n) = (x,y)