アルゴリズム

スポンサーリンク
初等整数論

ユークリッドの互除法

2つの整数 \(m, n\) に対して, 以下の手続きを行う事で最大公約数を得られる.1.\(n=0\) ならば \(m\) を最大公約数として終了する.2.\(m\) を \(n\) で割り, その余りを \(r\ (0\leq r<|n|)\) とする.3.\(n\) を新たな \(m\), \(r\) を新たな \(n\) とみなし, 1. に戻る.
スポンサーリンク