独習ノート「素数と２次体の整数論」＃１：約数と倍数

前回からはじまった独習ノートシリーズです。テーマは「整数論」。今日は整数論で最も基本的な「1.2 約数と倍数」について学んでいきたいと思います。

教科書を１つ決めて、それに沿って tsujimotter が勉強した過程をまとめていく連載シリーズです。
本シリーズの教科書はこちら。

素数と2次体の整数論 (数学のかんどころ 15)

作者: 青木昇,飯高茂,中村滋,岡部恒治,桑田孝泰
出版社/メーカー: 共立出版
発売日: 2012/12/21
メディア: 単行本
購入: 2人クリック: 2回
この商品を含むブログを見る

初回（＃０）：動機・諸注意
補足回（＃１．５）：集合の包含関係
次回（＃２）：Z のイデアル (1/2)

シリーズ全記事の一覧はこちら

約数と倍数

それでは、はじめていきましょう。まずは定義から。

定義 1.1
整数 $a, b$ に対して， $b = ac$ となる整数 $c$ が存在するとき，「 $a$ は $b$ を割り切る」または「 $b$ は $a$ で割り切れる」と言い， $a \mid b$ と表す．また， $a$ を $b$ の約数と呼び， $b$ を $a$ の倍数と呼ぶ．（以下略）

重要なキーワードが目白押しです。

まず、約数の定義には、割り算を使う必要がないのですよ。ここが１つポイントだと思います。
そして、掛ける（掛けられる）側の数を「約数」と呼んで、積の側の数を「倍数」と呼ぶ訳ですね。

この辺りをしっかり理解していないと、ちょっとしたことでつまづいてしまいます。

たとえば、次の定理。

命題 1.2
(2) $1$ の約数は $\pm 1$ の二つのみである．

これ、証明できますか？
当たり前な気もしてしまいますが、いざ証明せよと言われると難しい。漠然としたイメージだけで挑むと、どこから手をつけたら良いか分かりません。そんなときは定義に戻るのが吉。
ここでは、教科書よりやや丁寧にやってみましょう。

（証明）
$a$ を $1$ の約数とする．すなわち，定義 1.1 より、 $1 = ac$ となる整数 $c$ が存在する．
ここで

さらに $c\neq 0, a\neq 0$ ，すなわち， $\left|c\right| \geq 1, \left|a\right| \geq 1$ より

よって

$\left|a\right| = 1$ ．

すなわち

$a = \pm 1$ ．

複合はどちらも可であるから， $1$ の約数は $\pm 1$ であり，その２つのみであることが示せた．

（証明終わり）

下線を引いた部分がキーポイントですね。定義大事。

もう１つ、勘違いしやすいのが以下の命題。

命題 1.2
(3) 任意の整数は $0$ の約数であり， $0$ の倍数は $0$ のみである．

「あれ？０って約数あるんだっけ？」などといろんな疑問が出てきますが、これも丁寧に定義を追っていけばわかります。

（証明）
$0$ を使った積の性質より，任意の整数 $a$ に対して，

$a\cdot 0 = 0$

が成り立つ．

よって，約数と倍数の定義（定義 1.1）より，任意の整数は $0$ の約数であり， $0$ の倍数は $0$ のみである．

（証明終わり）

最大公約数

続いて、最大公約数です。やはり定義から。

定義 1.4
$a_1, \ldots, a_n$ を整数とする．
(1) $a_1, \ldots, a_n$ のすべてを割り切る整数を $a_1, \ldots, a_n$ の公約数と呼ぶ．
　また，最大公約数 $\gcd(a_1, \ldots, a_n)$ を次で定義する．
　・ある $i$ に対して $a_i \neq 0$ であるとき，
　　 $a_1, \ldots, a_n$ の公約数の中で最大のものを $\gcd(a_1, \ldots, a_n)$ とする．
　・ $\gcd(0, \ldots, 0) = 0$ ．
　特に，整数 $a, b$ に対して $\gcd(a, b) = 1$ であるとき，
　 $a$ と $b$ は互いに素であるという．
（以下略）

最大公約数、互いに素という重要な概念が登場しました。早速、この２つの用語に関連する以下の問題を解いてみましょう。

問題 1.5
$0$ でない整数 $a, b$ の最大公約数を $d$ とするとき， $a/d$ と $b/d$ は互いに素であることを示せ．

（証明）
$e = \gcd(a/d, b/d)$ とおくと，公約数の定義より $a/d = ef, b/d = eg$ となる整数 $f, g$ が存在する．
よって， $a = (de)f, b = (de)g$ から， $de$ は $a, b$ の公約数である．
一方， $a, b$ の最大公約数が $d$ であるから，結局 $d \geq de$ でなければならない． $e$ は $1$ 以上の整数より， $e = 1$ である．

したがって， $\gcd(a/d, b/d) = 1$ ，すなわち， $a/d$ と $b/d$ は互いに素である．

（証明終わり）

さて、以下からが今回の本題です。最大公約数を使った興味深い定理があります。

定理 1.6
整数 $a, b, c$ に対して $ax + by = c$ となる整数 $x, y$ が存在するためには， $\gcd(a, b) \mid c$ であることが必要十分である．

すべて整数係数で解も整数であるような方程式を「一次不定方程式」と呼んだりします。この定理では、一次不定方程式が解けるかどうかと最大公約数に関係がある、ということを主張しています。

例を挙げると、

$10x + 12y = 17$

という方程式には解がありませんし、

$10x + 12y = 16$

には解があります。具体的には $x = -8, y = 8$ が解となります。

$10$ と $12$ の最大公約数は、

$\gcd(10, 12) = 2$

であるから、

右辺の数が $2$ で割り切れれば、解が存在するというわけです。

$17$ は $2$ で割り切れるし、 $16$ は $2$ で割り切れない。

こうやって例を挙げていくと、「じゃあどうやって方程式の解を求めるの？」という疑問が浮かんできます。
その疑問には明確な答えがあって、（今回は登場しませんが） 1.6 節で登場する「ユークリッドの互除法」により解決されます。最大公約数と $x, y$ の解のいずれも、具体的に求める事が出来るのです。

ところでこの 定理 1.6 は

ある整数 $c$ が与えられたときに、方程式を満たす整数 $x, y$ が存在する

とみることができますし、逆に

整数 $x, y$ が与えられたときに、方程式にしたがって整数 $c$ が決まる

とみることもできます。

実はこれ、「イデアル」という言葉を使うと、スッキリまとめることが出来るのです。

これがまさに「前回予告した話」だったのですが・・・。

今回は思った以上に文章が長くなってしまったので、この辺で一旦おわりにしたいと思います。

イデアルのお話は、次回のお楽しみということで。

次回予告

次回は「1.3 $\mathbb{Z}$ のイデアル」へと進みます。「イデアル」という言葉を使って 定理 1.6 を書き直します。

2014/1/9 追記：
次回記事を書きました！
<a href="http://tsujimotter.hatenablog.com/entry/prime-number-and-quadratic-field-2">独習ノート「素数と２次体の整数論」＃２：Z のイデアル (1/2) - tsujimotterのノートブック</a>

2014/1/8 追記：
次回の前に、集合についての補足回を入れました。簡単な内容ですので、何を今更と思うようなものですが、ちらっと目を通してみてください。
<a href="http://tsujimotter.hatenablog.com/entry/prime-number-and-quadratic-field-ex1">独習ノート「素数と２次体の整数論」＃１．５：集合の包含関係（補足） - tsujimotterのノートブック</a>