２つの自然数、ａ、ｂの最大公約数（g.c.d.）を求める方法としては、
ａ、ｂをそれぞれ素因数分解して、共通の因子を取り出す、
という方法があるが、ａ、ｂが小さい数ならともかく、ひじょうに大きい数、
例えば100桁以上になると、素因数分解自体が困難となる。
100桁と云わないまでも、例えば、851と437の最大公約数といった場合、
それぞれの素因数を暗算で見つけられる人は少ないと思う。
素因数分解を行わず、一般の数に適用可能なアルゴリズムとして、ユークリッドの互除法がある。
例．851と437の最大公約数を求める。
最大公約数をｄとする。もちろん、１かもしれない。
851を437で割ってみる。
851＝１・437＋414
この時点で、851と437の最大公約数はわからない。
しかし、公約数である以上、＝の両方の値を割り切るはずである。
すなわち、
左辺：851
右辺：437と414
を割り切るはずである。つまり、
(851, 437)＝(437, 414)
である。
（ここで、何をやろうとしているのかピンとくるかもしれないが、とにかくこのまま進める。）
次に、437と414について、437を414で割ってみる。
437＝１・414＋23
上と同じ理由で、
(437, 414)＝(414, 23)
となる。
次に、414と23について、414を23で割ってみる。
414＝18・23
割り切れた。
すなわち、414と23の最大公約数は23である。
これまでの等式を逆に辿っていくと、
23＝(414, 23)＝(437, 414)＝(851, 437)
となり、851と437の最大公約数は23となる。
実際に割ってみると、
851＝37・23
437＝19・23
であるから、たしかに23は851と437の最大公約数である。
このように、
２数を割って余りを取っていき、余りが０になった時、
その時の割り切った数が最大公約数である。
というアルゴリズムをユークリッドの互除法と呼ぶ。
このアルゴリズムのポイントは、
ある数を素因数分解するのは一般に困難であるが、
２つの数の割り算を行うのは簡単である。
という点にある。
ちなみに、ユークリッドというと幾何学というイメージが強いが、
『原論』では１巻まるごと、整数論を扱っている巻があり、
その中で、このユークリッドの互除法の他に、
等について、触れている。
プログラムは以下のとおり。
fnGcd(A,B) local D if A<B then swap (A,B) D=A@B while (D<>0) A=B:B=D:D=A@B wend return(B)
UBASICでは、gcd(n)という組み込み関数となっている。
これを利用して、
等が可能となる。これについて特にプログラムは示さない。
与えられた数ａ、ｂ、ｃについて、ａｘ＋ｂｙ＝ｃをみたす整数ｘ、ｙを求める。
ａ、ｂの最大公約数をｄをしたとき、ｄ｜ｃなら解が存在する。
アルゴリズムは以下のとおり。
(1) S＝a, T＝bとする
(2) S＝Q・T＋U（余り）
・U＝0 なら、T＝gcd(a，b)
・U≠0 なら、
S＝T, T＝Uとして、(2) へ
(1) Sa＝1, Ta＝0
Sb＝0, Tb＝1
とする（初期値）
(2) Ua＝Sa−Q＊Ta
Ub＝Sb−Q＊Tb
Sa＝Ta, Sb＝Tb
Ta＝Ua, Tb＝Ub
(3) gcd(a, b)＝T（下のプログラムではS）が求まったとき、
x＝Sa×c／T
y＝Sb×c／T
が解。
gcd(a, b) が c を割り切らないときは、解なし
10 input "A, B, C=";A,B,C 20 S=A:Sa=1:Sb=0 30 T=B:Ta=0:Tb=1 40 while T<>0 50 Q=S\T 60 U=S-Q*T:Ua=Sa-Q*Ta:Ub=Sb-Q*Tb 70 S=T:Sa=Ta:Sb=Tb 80 T=U:Ta=Ua:Tb=Ub 90 wend 100 G=S 110 if C@G<>0 then print "解なし。":end 120 Sa*=C\G:Sb*=C\G 130 print "一般解は x=";Sa;"+";B\G;"t , y=";Sb;"-";A\G;"t" 140 end
(a, m)＝1 のとき、ab≡1 (mod m) となる、ｂが存在する。ｂを求める。
前の式、ａｘ＋ｂｙ＝ｃにおいて、
b → m
c → 1
とおいたときのｘ が解となる。
ｘ だけ求めればよいので、前のプログラムで、
Ub＝Sb−Q*Tb
の部分は不要。よって、Sb、Tbも不要。
10 input "A, M =";A,M 20 B=fnModinv(A,M) 30 if B=0 then print "解なし。":end 40 print B 50 end 60 ' 70 fnModinv(A,M) 80 local Ta,U,Ua,Q 90 Sa=1:Ta=0 100 while M<>0 110 Q=A\M:U=A-Q*M:Ua=Sa-Q*Ta 120 A=M:Sa=Ta 130 M=U:Ta=Ua 140 wend 150 if A<>1 then return(0) 160 return(Sa)
UBASICでは、modinv(a,m)という組み込み関数になっている。
２数、ａ、ｂについて、まず、２で割れるだけ割っておき、それをｃに格納する。
２で割る操作は、ａ、ｂを２進数で表した場合、右にシフトしていけばよい（これは、２の割算よりも速い）。
そうすると、(1)両方とも奇数、(2)片方が奇数、片方は偶数、の状態になるはずである。
ここで、後者の場合、偶数が両者の共通因子になることはありえないので、
両者奇数になるまで、２で割る。
大きい方から小さい方を引く。奇数と奇数の差なので、必ず偶数となる。
かつ偶数の共通因子はないから、この答えを奇数になるまで、２で割る。
この答えと、小さい方について、同じ処理を繰り返す。
（互除法では、ここで割算を行った）。
上記処理を行っていくと、どこかで、ａ−ｂ＝０となる。
この０となったときのａ、ｂの値が、奇数の最大共通素因数となる。
この値と、ｃ（２のべきの最大共通素因数）を掛け合わせたものが、求める最大公約数となる。
割算ではなく、引算にしているため、ループの回数は互除法に比べて多くなる。
しかし、右へのシフト及び引算等は、割算に比べて圧倒的に速いため、
全体としての処理時間は、かなり短縮される。
特に、大きい数の最大公約数を求めるときは、効果が大きい。
| 前 | この章の目次 | 次 |
|---|