 | aとbの最大公約数をgとしてa=Ag,b=Bgとする。AとBは互いに素。
as[1]=xt[1], bs[2]=xt[2]から
Ags[1]=xt[1], Bgs[2]=xt[2]であり
条件からt[1]とt[2]は互いに素なので、xはgで割り切れる。
x=zgとおくと、yはxの倍数なのでy=kzgとおける。
as[1]=xt[1], as[3]=yt[3]から
Ags[1]=zgt[1], Ags[3]=kzgt[3]すなわち
As[1]=zt[1], As[3]=kzt[3]
条件からs[1]とs[3]は互いに素なので、Aはzで割り切れる。
同様に
bs[2]=xt[2], bs[4]=yt[4]から
Bgs[2]=zgt[2], Bgs[4]=kzgt[4]すなわち
Bs[2]=zt[2], Bs[4]=kzt[4]
条件からs[2]とs[4]は互いに素なので、Bはzで割り切れる。
AとBは互いに素なので、z=1。従ってx=gすなわちxはaとbの最大公約数。
第1式×第4式-第2式×第3式から
ab(s[1]s[4]-s[2]s[3])=xy(t[1]t[4]-t[2]t[3])
a,b,x,yは正なので ab=xy
となるから、y=ab/g=(aとbの最小公倍数)
従って答えは
xはaとbの最大公約数
yはaとbの最小公倍数
|