初等整数論講義/第1章/最大公約数,最小公倍数

提供: Wikisource
ナビゲーションに移動 検索に移動

§2. 最大公約数,最小公倍数[編集]

1. 二つ以上の整数 に共通なる倍数(例えば積 など)をそれらの整数の公倍数という. は公倍数ではあるが,それを除けば,公倍数の中に最も小(絶対値に於いて)なるものがある. それを最小公倍数という.

二つ以上の整数 に共通なる約数(例えば など)をそれらの整数の公約数という.公約数は絶対値に於いて よりも大なることを得ないから( がすべて なる場合を除けば),その中に最も大なるものがある.それを最大公約数という.

本節では最大公約数及び最小公倍数に関する基本的の定理を述べる.事実としては周知であろうが,往々無証明で受け入れられているようでもあるから,この際反省をして見るのも無用ではあるまい.理論上では,最小公倍数を先にする方が簡明である.


定理 1.3.

二つ以上の整数の公倍数は最小公倍数の倍数である.

[証]

の最小公倍数を とし( ), を任意の公倍数とする.さて

とすれば

で, の倍数であるから, の倍数である(定理 1.1).同様に の倍数である.即ち の公倍数である. の公倍数の中で, を除いて最小絶対値のもので, であるから, [1] 即ち


定理 1.4.

二つ以上の整数の公約数は最大公約数の約数である.

[証]

の最大公約数を とし, を任意の公約数とする.然らば の約数であるというのは, との最小公倍数が であるというに同じい.今 との最小公倍数とする.さて仮定に由って の倍数であり又 の倍数であるから, の公倍数,従って の倍数である(定理 1.3).同様に の倍数である.故に の公約数である.故に ,然るに の倍数であるから ,故に [2]


次の定理は二つの整数 に関するものである.

定理 1.5.

の最小公倍数を ,最大公約数を とすれば,

(ただし とする.)

[証]

の公倍数であるから

(1)

とする.さて は勿論 の公倍数であるから, の倍数である(定理 1.3).由って

(2)

とする.(1)から に代入して

(3)

を得る.故に の公約数である.

由って とする(定理 1.4 ).然るに で割り切れるから,(3)に於いて で割り切れる. 由って として (1)に代入すれば

若しも ならば, の公倍数になる.これ不合理である. 故に ,従って . 故に(2)から


の最大公約数を なる記号で表わすことにする.

以外の公約数を有せぬときには, 略して は公約数を有せぬという. この場合には

特に二つの整数 が公約数を有せぬときには, 互いに素ともいう.

次の定理はしばしば引用されるものであるから特に大切である.

定理 1.6.

で,かつ で割り切れるならば, で割り切れる.

[証]

仮定に由って であるから, の最小公倍数は である(定理 1.5).

然るに仮定に由って の倍数,従って の公倍数であるから の倍数である(定理 1.3).

故に は整数,即ち で割り切れる.

実際に,与えられたる(正の)整数の最大公約数,又は最小公倍数を求める方法は周知であるが, この際,念の為にその理論的の根拠を叩いておくのも無用であるまい.

命題 1.

[証]

の最大公約数[3] とすれば, の約数,従って の公約数, 従って の約数である(定理 1.4).

また とすれば, であるから,同様に の約数である.

このように とは,各が他方の約数であるから,相等しい.

特に で割った剰余を とすれば, . 又 で割った剰余を とすれば, . このように進んで行けば であるから, ついには[4]剰余が になる. 今 で割り切れるとすれば, ,即ち .これが ユークリッド の互除法である.

三つ以上の整数 の最大公約数を求めるにも 互除法を応用することが出来る. 今これらの数の中 が最も小さいときは, を割って,剰余を とする. 然らば問題 1と同様に

剰余の中に があれば,それを()の中から省いてよい. さて に同様の操作を行う. そのとき除数にする最小数は の中の数で, それは よりも小である. この操作を継続すれば,毎回()内の最大数が減少するから,次第に剰余 が出てきて, ついには括弧内に唯一つの数が残る. それが即ち である. 剰余は絶対的最小剰余を取るがよい.

[例]


命題 2.

三つ以上の整数の最小公倍数を求めるとき,それらの整数の一部分をその最小公倍数でおき換えてよい. 例えば の最小公倍数は, の最小公倍数 との最小公倍数に等しい.

[証]

の最小公倍数を とし, の最小公倍数を とすれば, の公倍数であるから の倍数である(定理 1.3). は固より の倍数であるから の公倍数, 従って の倍数である. 又 の倍数,従って の倍数, 従って の公倍数, 従って の倍数である. このように の倍数, の倍数であるから . 二つの整数の最小公倍数は定理 1.5に由って最大公約数から求められる. 由って上記問題の定理を応用して任意数の整数の最小公倍数が求められる.


  1. officious: 前節, は任意の整数 の倍数.
  2. officious: の最小公倍数を とすると当然 ,特に,. 一方, の公約数であることが示された.公約数の中で最大のものが というのだから,. 両者より .
  3. officious: ここを単に「公約数」に読み替えても議論は正しい、すなわち「 の公約数全体の集合と、 の公約数全体の集合は相等しく、特に最大公約数も一致する。」
  4. 原文「竟には」