867 と 357 の最大 ついて考えてみよう。
867 と 357 をそれぞれ素因数分解すると,
867=3×17°,
となるから,この2つの整数の最大公約数Gは, G=3x17=5=
最大公約数は,上のように素因数分解を利用して求めること
867 や 357 のような大きな整数を素因数分解することは簡単で
357=3×7×17
そこで,まず 867 と 357 の差に着目してみよう。
dを 867 と 357の公約数とすると,
867=md, 357=nd (m, nは正の整数)
とおける。このとき,
867-357=(m-n)d
となり, dは867-357 と 357 の公約数である。
逆に, d'を 867-357 と 357 の公約数とすると,
867-357=m'd', 357=n'd' (m', n' は正の整
とおける。 このとき, 867=m'd'+357=(m'+n')d"