1
大学数学基礎解説
文献あり

初等整数論講義 - §2 - 最大公約数, 最小公倍数

53
0
$$$$

まず、用語を整理しておきます。

  • $a$$b$で割り切れるとき、「$a$$b$の倍数」、あるいは、「$b$$a$の約数」といいます。
  • $n$$a,b,c,\cdots$で割り切れるとき、「$n$$a,b,c,\cdots$の公倍数」といいます。
  • $a,b,c,\cdots$$n$で割り切れるとき、「$n$$a,b,c,\cdots$の公約数」といいます。
  • 公約数の中で最大のものを最大公約数、正の公倍数の中で最小のものを最小公倍数といいます。

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

$l$$a,b,c,\cdots$の最小公倍数、$m$$a,b,c,\cdots$の任意の公倍数とする。
$m=ql+r,\quad0\leq r< l$
と表すと、$r=m-ql$である。$m$$ql$$a$の倍数なので$r$$a$の倍数。これを$b,c,\cdots$にも適用して、$r$$a,b,c,\cdots$の公倍数であることがわかる。ここで、$0\leq r< l$だったので、$r=0$。よって、$m=ql$であり、公倍数は最小公倍数の倍数であることが分かる。

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

$m$$a,b,c,\cdots$の最大公約数、$d$$a,b,c,\cdots$の任意の公約数とする。
背理法で証明する。つまり、$m$$d$で割り切れないとする。これは$m=dq+r$と書ける($1\leq r< |d|$)。
$a=ma'=da''$
$b=mb'=db''$
$\dots$
とおく。ここで、$a',b',c',\cdots$のすべてが$\pm 1$でない$d$のある約数(これを$\alpha$と書くことにする)で割り切れるとすれば、$|m\alpha|$の方が$m$よりも大きい公約数になるので矛盾。よって$m=dq+r$$d$の倍数。ゆえに、$r$$d$の倍数であるが、$1\leq r < d$であることに矛盾。
よって背理法より、$d$$m$の約数である。

$a,b$の最小公倍数を$l$、最大公約数を$m$とすれば、
$$ab=lm$$
が成り立つ($a>0,b>0$とする)

定理1より、$ab$$l$の倍数なので$ab=dl$とかける。
$l$$a,b$の公倍数なので、$l=ax=by$とかける。$ab=dl$に代入して、$b=dx, a=dy$である。よって$d$$a,b$の公約数である。
よって定理2より$m=de$とかける。ここで、$m$$a$$b$の公約数なので、$b=dx, a=dy$より、$e$$x$$y$の公約数である。よって、$x=ex',y=ey'$として$l=ax=by$に代入すると、$l=eax'=eby'$。もしも$e>1$なら、$l/e< l$$a,b$の公倍数になるが、これは矛盾。よって$e=1$。ゆえに$ab=lm$が成り立つ。

$a,b,c,\cdots$の最大公約数を$(a,b,c,\cdots)$という記号で書き表すことにします。

$(a,b)=1$のとき、$a,b$を互いに素と言います。

$a,b$が互いに素で、かつ$bc$$a$の倍数ならば、$c$$a$の倍数である。

定理3を使うと、$(a,b)=1$より、$a,b$の最小公倍数は$ab$である。
今、$bc$$a$の倍数なので$bc$$a,b$の公倍数。よって$bc$$ab$の倍数。ゆえに$bc/ab=c/a$は整数で、$c$$a$で割り切れることが分かった。

参考文献

[1]
高木貞治, 初等整数論講義
投稿日:529
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

数学や物理にはいつも新しい刺激をいただいています。感謝!

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中