2022-06-08

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

最大公約数

整数の最大公約数の定義を紹介します。 最大公約数とは普通、複数の整数の公約数のうち最大の自然数ことを指しますが、ここではより広い定義で紹介します。
初等整数論

ユークリッドの互除法

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