コンテンツへスキップ
Topos Uranos
日本語

最大公約数と最小公倍数

要約

この課では、二つの自然数の最大公約数と最小公倍数を定義し、それらを二通りの方法で求めることを学ぶ。素因数分解による方法と、素因数分解を必要としないユークリッドの互除法による方法である。互除法からはベズーの等式、すなわち最大公約数が二つの数の整数係数の一次結合であるという事実が導かれ、さらにそこから、二つの概念の関係、互いに素な数の特徴づけ、分数の約分と加法、そして一次不定方程式の完全な解法が導かれる。一次不定方程式は、硬貨の問題や計量の問題に応用される。

学習目標

  1. 素因数分解によって最大公約数と最小公倍数を求め、両者の関係を説明する。
  2. ユークリッドの互除法とその拡張版を用いて、最大公約数とベズーの等式の係数を求める。
  3. 互いに素な数を見分け、最大公約数と最小公倍数を用いて分数を約分し、足し合わせる。
  4. 一次不定方程式が解をもつかどうかを判定し、そのすべての解を記述し、自然な制約のある問題に応用する。

最大公約数と最小公倍数

整除と余りのある割り算の課では、二つの自然数の間の関係 d∣ad \mid a を学んだ。二つの数を同時に考えるときには、それらが共通にもつ約数と、共通にもつ倍数に関心が向く。自然数の組 aa と bb はどれも、少なくとも一つの公約数、すなわち 11 をもち、公約数は高々有限個である。aa のどの約数も aa を超えないからである。さらに、公倍数は無数にあり、その中には積 abab が含まれる。そうであるならば、次の定義には意味がある。

定義（最大公約数と最小公倍数）。二つの自然数 aa と bb の最大公約数（gcd⁡(a,b)\operatorname{gcd}(a, b) と書く）とは、両方を割り切る最大の自然数である。最小公倍数（lcm⁡(a,b)\operatorname{lcm}(a, b) と書く）とは、両方の倍数である最小の自然数である。

後者は自然数からなる空でない集合の最小元であり、整列原理によって存在する。前者は公約数の集合の最大元であり、この集合は空でなく、aa で上から押さえられている。上に有界な空でない自然数の集合が最大元をもつことも、整列性から導かれる。その上界の集合は空でなく、最小元 MM をもつ。そして MM はもとの集合に属する。そうでなければ、どの元も MM より小さく、M−1M - 1 と MM の間には自然数がないので、どの元も M−1M - 1 以下となり、これは MM より小さい上界になってしまうからである（M=1M = 1 のときは、集合は {1}\{1\} であって MM を含む）。たとえば、1212 と 1818 の公約数は 11、22、33、66 であり、公倍数は 3636、7272、108108 と続いていく。

gcd⁡(12,18)=6,lcm⁡(12,18)=36\operatorname{gcd}(12, 18) = 6, \qquad \operatorname{lcm}(12, 18) = 36

定義からただちにいくつかの特別な場合が得られる。gcd⁡(a,1)=1\operatorname{gcd}(a, 1) = 1 かつ lcm⁡(a,1)=a\operatorname{lcm}(a, 1) = a。gcd⁡(a,a)=lcm⁡(a,a)=a\operatorname{gcd}(a, a) = \operatorname{lcm}(a, a) = a。そして、aa が bb を割り切るならば、gcd⁡(a,b)=a\operatorname{gcd}(a, b) = a かつ lcm⁡(a,b)=b\operatorname{lcm}(a, b) = b。さらに、二つの演算はどちらも対称である。数の順序は結果を変えない。

素因数分解による計算

算術の基本定理により、11 より大きいすべての自然数は、ただ一通りに素因数分解される。aa と bb を同じ素数 p1,…,pkp_1, \ldots, p_k を用いて表しておくと都合がよい。その際、一方にしか現れない素数については指数 0 を認める。

a=p1α1p2α2⋯pkαk,b=p1β1p2β2⋯pkβka = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}, \qquad b = p_1^{\beta_1} p_2^{\beta_2} \cdots p_k^{\beta_k}

自然数 dd が aa を割り切るのは、その素因数分解に aa の素因数以外の素数が現れず、しかも各素数の指数が aa におけるその指数以下であるとき、かつそのときに限る。このことから、dd が aa と bb を同時に割り切るのは、dd における各素数の指数が二つの指数のどちらも超えないときである。したがって、最大の公約数は、各素数について二つの指数のうち小さい方をとれば得られる。同様に、mm が公倍数であるのは、mm における各素数の指数が二つの指数のどちらにも達するときであり、最小の公倍数は各素数について二つの指数のうち大きい方をとる。たとえば、

360=23⋅32⋅51⋅70,84=22⋅31⋅50⋅71360 = 2^3 \cdot 3^2 \cdot 5^1 \cdot 7^0, \qquad 84 = 2^2 \cdot 3^1 \cdot 5^0 \cdot 7^1
gcd⁡(360,84)=22⋅31⋅50⋅70=12,lcm⁡(360,84)=23⋅32⋅51⋅71=2520\operatorname{gcd}(360, 84) = 2^2 \cdot 3^1 \cdot 5^0 \cdot 7^0 = 12, \qquad \operatorname{lcm}(360, 84) = 2^3 \cdot 3^2 \cdot 5^1 \cdot 7^1 = 2520

この方法はわかりやすいが、素因数分解ができることが前提であり、大きな数の素因数分解には非常に手間がかかる。それを速く行う方法は一つも知られていない。次の節の互除法は、素因数分解をせずに、割り算だけで最大公約数を求める。