初等整数論 最大公約数と最小公倍数の関係
最大公約数と最小公倍数の関係を紹介します。
２つの整数の最大公約数と最小公倍数には、きれいな関係式があります。
最大公約数
初等整数論 初等整数論 互いに素な整数
整数同士の関係を考える上で基本となる互いに素という概念を紹介します。
最大公約数や最小公倍数をなどと関連が深いです。
整数 \(a_1, a_2, \ldots, a_n\) が互いに素(coprime)であるとは
\[\mathrm{gcd}(a_1, a_2, \ldots, a_n)=1\] が成り立っていることをいう.
初等整数論 ベズーの等式
複数の整数とその最大公約数の関係を表すベズーの等式を紹介します。
ベズーの等式(Bézout's identity)
整数 \(a_1, a_2, \ldots, a_n\) に対して \(g=\mathrm{gcd}(a_1, a_2, \ldots, a_n)\) とおくと, \[g=a_1x_1+a_2x_2+\cdots+a_nx_n\] となる整数 \(x_1, x_2, \ldots, x_n\) が存在する.
初等整数論 最大公約数の性質
最大公約数の性質について紹介します。
初等整数論 最大公約数
整数の最大公約数の定義を紹介します。
最大公約数とは普通、複数の整数の公約数のうち最大の自然数ことを指しますが、ここではより広い定義で紹介します。
初等整数論 ユークリッドの互除法
２つの整数 \(m, n\) に対して, 以下の手続きを行う事で最大公約数を得られる.
1.\(n=0\) ならば \(m\) を最大公約数として終了する.
2.\(m\) を \(n\) で割り, その余りを \(r\ (0\leq r<|n|)\) とする.
3.\(n\) を新たな \(m\), \(r\) を新たな \(n\) とみなし, 1. に戻る.