このディレクトリの索引
#  
#  最大公約数をユークリッドの互除法で求める。
#  
#  証明 (Wikipediaより)
#  
#  a, b は自然数で a ≠ 0 とする。 b を a で割った商を q、剰余を r とすると
#  b = qa + r
#  今、d0 を a と r の両方を割り切る自然数とする。
#  
#  このとき d0 は積 qa を割り切るから、和 qa + r も割り切るが、qa + r は b に等しい。
#  したがって、d0 は a とb を割り切る。すなわち a と r の公約数はすべてb と aの公約数である。
#  逆に、d1 を b と a の両方を割り切る自然数とする。
#  d1 は qa を割り切るから差 b - qa を割り切るが、b - qa は r に等しい。
#  したがって、d1 は a とrを割り切る。言い換えると b と a の公約数はすべてa と r の公約数である。
#  したがって、b と a の公約数全体の集合は a と r の公約数全体の集合に等しく、
#  特に b と a の最大公約数は a と r の最大公約数でなければならない。
#  


最大公約数をユークリッドの互除法で求める(M,N,_最大公約数) :-
ユークリッドの互除法は割り切れるまで除数だった数を被除数に剰余だった数を除数として割ることを繰り返す(M,N,_最大公約数).

ユークリッドの互除法は割り切れるまで除数だった数を被除数に剰余だった数を除数として割ることを繰り返す(_被除数,_除数,_最大公約数) :-
_剰余 is _被除数 mod _除数,
割り切れるまで除数だった数を被除数に剰余だった数を除数として割ることを繰り返す(_除数,_剰余,_最大公約数).

割り切れるまで除数だった数を被除数に剰余だった数を除数として割ることを繰り返す(_除数,0,_最大公約数) :-
割り切れたらその時の除数が最大公約数だ(_除数,_最大公約数),!.
割り切れるまで除数だった数を被除数に剰余だった数を除数として割ることを繰り返す(_除数,_剰余,_最大公約数) :-
'割り切れなかったら除数を被除数、剰余を除数に置き換えて計算を続ける'(_除数,_剰余,_最大公約数).

割り切れたらその時の除数が最大公約数だ(_除数,_最大公約数) :-
_除数 = _最大公約数.

'割り切れなかったら除数を被除数、剰余を除数に置き換えて計算を続ける'(_除数,_剰余,_最大公約数) :-
ユークリッドの互除法は割り切れるまで除数だった数を被除数に剰余だった数を除数として割ることを繰り返す(_除数,_剰余,_最大公約数).