アルゴリズム

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

ユークリッドの互除法

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