不定方程式
最大公約数 最小公倍数(2
ISZ
除法を用いるとよい。
L=abG
A. B, Cの最大公約数である。
(1) 3007=1649×1+1358
1649=1358×1+291
1358=291×4+194
291=194×1+97
194=97×2
よって,求める最大公約数は,
まず 3007 を1649 で
って余り 1358 を求店
次に1649 を1358 -
さる って余り 291 を求
これを,余りが0
るまで繰り返す。
L6
3007=31×97, 1649=17×97
(2) (1)より,
よって,求める最小公回奴は,
31×17×97=51119
97 は素数
Te0
L6
3007 1649
I1
L=abG
(3) 234=208×1+26
208=26×8
まず 208 と 23-
公約数を求めこ
より,234 と 208 の最大公約数は, 26
ここで、26 と 325 の最大公約数を考えると, aの最大公約数
325=26×12+13
求めた26 と残
a e 13 は素数
e 13 )208 2
26=13×2
より, 13
したがって,求める最大公約数は,
また。
208=2*×13, 234=2×3°×13, 325=5°x13
したがって、
よって,求める最小公倍数は, 46800
96
13
それぞれ
2*×3°×5°×13=46800 る。
1
2つの自然数の最大公約数を求める際に、
ーAはコークリッドの互除法を