次: 整式の整数論 上: 整式の整数論 前: 整数と整式の類似

• 整数の除法
• 約数・倍数
• 因数分解
• 差で閉じた部分集合
• 1次不定方程式の解の存在

整数の基礎

整数の除法

南海　 まず整数論の入り口である，除法と，除法を用いた論証の復習だ．

定理 1 (除法の原理)
$a$を整数，$b$を0でない整数とする．このとき，

$$a=qb+r\ ,\quad 0 \le r<\vert b\vert$$

となる整数 $q,\ r$ がただ１組存在する． ここに，$\vert b\vert$は整数$b$の絶対値を表す．

この証明そのものは『数論初歩』を見てほしい． 重要なので概略を示す．

まず．整数 $a$ と正整数$\vert b\vert$に対して

$$q\vert b\vert \le a <(q+1)\vert b\vert$$

となる整数 $q$ が存在することを示す． これは入試問題の解答のレベルでは， $q\vert b\vert$が$q$に関して単調増加であることによればよい． （参考『03阪大前期理系4番』，『04京都府立医大3番』）

『数論初歩』ではさらに厳密に， 自然数の部分集合には最小の要素が存在することを根拠に証明した．

そこで $r=a-q\vert b\vert$ とおく． $q\vert b\vert\le a<(q+1)\vert b\vert$ より$0 \le r<\vert b\vert$ で

$$a=q\vert b\vert+r$$

である．$b>0$なら$\vert b\vert=b$より定理が示せた． $b<0$のときは$\vert b\vert=-b$より$a=(-q)(-b)+r$とすればよい．

あとはこのような $q,\ r$ が二通りあったとして，相等しいことを示せばよかった．

約数・倍数

太郎　 このように割り算ができることから， 約数や倍数の基本性質が導かれるのですね．

南海　 どのように導かれるのか，確認しよう．

まず，整数$a$が$b$の倍数でるとは，$a=bq$となる整数が存在することと定める．

すると，割り算ができ，$a$を$b$で割った商と余りが一意に確定することによって，

$a$が$b$の倍数であることは， $a$を$b$で割った余りが0であることと同値である．

太郎　 そこで質問ですが，例えば6の約数は普通2や3ということになりますが， $-2$や$-3$も約数ではないのですか．

南海　 その通りだ．

素数は正のもので考えるので$6=(-2)(-3)$を素因数分解とはいわないのだが， 因数分解であることには変わりない．

このように，約数や倍数，$\pm 1$の自由さがあり， 整除に関することは$\pm 1$の違いを除いて決まる． これを前提にして，正の方で代表させて考えるのである．

太郎　 $\pm 1$は特別な数なのですか．

南海　 そう．整数のなかで逆数もまた整数であるのは，$\pm 1$だけだ． このような数を単数というのだが，普通の整数では単数は$\pm 1$だけだ．

太郎　 「普通の整数」でないものとは『数論初歩』に少し書かれていた二次体の整数とかですか．

南海　 そうだ．いわゆる「代数的整数」だ． この話はここではこれ以上はできないが， 実二次体の整数では単数が無数にある．

普通，整数といっているものは有理整数という．

太郎　 有理整数では単数は$\pm 1$だけなのですね． そして，割り切れるとか，因数分解とか， すべて，ある整数で成り立てば， それに$\pm 1$をかけても，成り立つのですね．

南海　 『数論初歩』でもそのことは書かれているが， 少しわかりにくかったかもしれない．

そこでいくつかの定義．

0および$\pm 1$でない整数$a$は少なくとも$\pm 1$と$\pm a$を約数を持つ． $\pm 1$および $\pm a$ 以外の約数を「真の約数」ともいう．

真の約数を持たない正の整数$a$を 素数 という．

真の約数を持つ整数を 合成数 という．

さらに，公約数，公倍数が定義される．

太郎　 『数論初歩』に次のように公倍数，公約数の定義があります．

二つ以上の整数 $a,\ b,\ c,\ \cdots$ に共通な倍数をそれらの整数の公倍数という． 0は常に公倍数である． それを除けば公倍数の絶対値は $a,\ b,\ c,\ \cdots$ のいずれの絶対値よりも小さくはないので， 公倍数の中に正で最小のものがある． それを最小公倍数(least common multiple 略して L.C.M.)という．

二つ以上の整数 $a,\ b,\ c,\ \cdots$ に共通な約数をそれらの整数の公約数という． 1は常に公約数である． 公約数の絶対値は $a,\ b,\ c,\ \cdots$ のいずれの絶対値よりも大きくはないので， 公約数の中に最大のものがある． それを最大公約数(greatest common measure 略して G.C.M.)という．

同様の理由で，公約数，公倍数は正のもので考えるのですね．

南海　 最大公約数が1であるとき，その2数は互いに素であるという．

そこで，次の定理の(1)を示してほしい． 他はこれをもとに示される． それは『数論初歩』にある．

太郎　 はい．

定理 2

(1)

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

(2)

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

(3)

$a,\ b$ の最小公倍数を $l$ ， 最大公約数を $d$ とすれば $ab=dl$ ．

(4)

$a,\ b$ が互いに素で， 他の整数 $c$ と $b$ との積 $bc$ が $a$ で 割りきれるなら，実は $c$ が $a$ で割りきれる．

証明

$a,\ b,\ c,\ \cdots$ の最小公倍数を $l$ とし, $m$ を任意の公倍数とする． $m$ を $l$ で割った商を $q$ ，余りを $r$ とすると

$$m=ql+r,\ \quad 0 \le r<l$$

となる． $l$ も $m$ も $a$ の倍数であるから $l=al',\ m=am'$ とおくと

$$r=m-ql=a(m'-ql')$$

より, $r$は$a$の倍数である．同様に $b,\ c,\ \cdots$の倍数でもあり， $r$は $a,\ b,\ c,\ \cdots$の公倍数となる． ところが $l$ は正で最小の公倍数であったから， もし $r$ が0でないとすると, $l$ より小さい正の公倍数があることになり, $l$ の最小性に反する．

$$∴\quad r=0$$

つまり $m$ は $l$ の倍数である．

南海　 この定理の証明において， 「除法の原理」が基本定理として用いられてることがわかる． 日頃当然のように論証で使っていることが， 「除法の原理」を基礎に厳密に示される．

因数分解

南海　 次に因数分解を考えよう． 先に見たように，因数分解は

$$12=2^2\cdot 3=2\cdot(-2)\cdot(-3)$$

のように，全体として1になるように$\pm 1$を割り振ってもよい．

整数$\alpha$をこれ以上分解できないところまで分解して，

$$\alpha=\pm {p_1}^{e_1}{p_2}^{e_2}\cdots{p_m}^{e_m}$$

の形にしたものを素因数分解という．

$p_1,\ p_2,\ \cdots,\ p_m$は異なる素数， $e_1,\ e_2,\ \cdots,\ e_m$は正の整数である．

合成数は素数の積として順序を除けばただ一通りに表すことができる． これが素因数分解の一意性といわれる基本定理である．

定理 3
     合成数を素数の積に分解することができる． かつ，その分解の結果は（因数の順序をのぞけば）一意である．

南海　 この証明は『数論初歩』をみてほしい． 概略をいえば，分解できることは数学的帰納法で示す． 一意性の証明は，整数の積$ab$を素数$p$が割り切れば， $p$は$a$または$b$を割り切る，ということを用いる． これは先の定理2の(4)からわかる．

太郎　 なるほど．すべて除法が論証の根拠になっているのですね．

南海　 最近，次のような除法を用いない因数分解の一意性の証明を『数学のたのしみ』 (2006年夏号，日本評論社)の「素数・ゼータ関数・三角関数」(黒川重信)で教えられた． ツェルメロによるものであるということだ．

それを紹介しよう． これは除法を用いていない． 自然数の集合には最小のものが存在することだけを用いている．

因数分解の可能性は同様なので，一意性のみ別証明をおこなう．

因数分解の一意性の別証明

異なる因数分解をもつ自然数の集合を考える． この集合に属する最小の自然数を$n$とする． $n$は相異なる2つの因数分解をもつ．それを

$$\begin{eqnarray*} n=p_1p_2\cdots p_r&&(p_1\le p_2\le \cdots \le p_r)\\ n=q_1q_2\cdots q_s&&(q_1\le q_2\le \cdots \le q_s) \end{eqnarray*}$$

とする．ここに $p_1,\ \cdots,\ p_r,\ q_1,\ \cdots,\ q_s$ は素数である．これが異なる因数分解ということは $r\ne s$か，または$r=s$で$p_i\ne q_j$となる$i,\ j$が存在するか， のいずれかである．

また， $p_1,\ \cdots,\ p_r$のいずれも $q_1,\ \cdots,\ q_s$のいずれとも異なる． なぜなら，もし$p_i=q_j$なら， これを約せば$n$より小さい数で，異なる因数分解をもつ自然数が得られ， $n$がそのような数のなかで最小であることに反する．

$p_1<q_1$とする． ここで自然数$m$を

$$\begin{eqnarray*} m&=&n-p_1q_2\cdots q_s\\ &=&(q_1-p_1)q_2 \cdots q_s \end{eqnarray*}$$

で定める．$m<n$である．

この$m$の因数分解における因数$q_1-p_1$は$p_1$の倍数ではない． なぜならもし$p_1$の倍数なら$q_1$が$p_1$の倍数となり互いに異なる素数であることに反する． よってこの因数分解に$p_1$は現れない．

一方$m$は

$$\begin{eqnarray*} m&=&n-p_1q_2 \cdots q_s\\ &=&p_1(p_2 \cdots p_r-q_2 \cdots q_s) \end{eqnarray*}$$

でもある． この$m$の因数分解には，因数$p_1$が現れている．

よって$m$の2つの因数分解は相異なる因数分解である．

$m<n$なので， $n$が異なる2つの因数分解をもつ最小の自然数であることと矛盾した．

したがって異なる2つの因数分解をもつ自然数は存在しない．□

太郎　 わかりました．

除法の原理自身，除法が一意に出来ることを示すためには 自然数の集合には最小のものが存在することを用いるのでした．

だから，除法を使うか使わないかにかかわらず，自然数の性質が土台になっています．

南海　 そうなのだ． だから，このツェルメロの証明は， 自然数の集合には最小のものが存在することをいったん除法の原理にまとめることをせず， 自然数の性質から直接示す，ともいえる．

これを参考にして， 後で整式の因数分解の一意性の証明もおこないたい．

差で閉じた部分集合

南海　 もう一つ，証明に除法が使われる基本定理を紹介しよう．

定理 4
     整数からなる，空でなく$\{0\}$のみでもない集合$A$が次の性質をもつとする．

$$a,\ b\in A\quad \Rightarrow \quad a-b\in A$$

このとき集合$A$はある整数$d$の倍数の全体と一致する．つまり

$$A=\{\ dn\ \vert\ n :整数 \}$$

証明

条件から$0=a-a\in A$である． その結果，$a\in A$なら $-a=0-a\in A$である．

また，自然数$n$に対して$na\in A$のとき

$$(n+1)a=na-(-a)\in A$$

となるので，数学的帰納法によって$a\in A$なら$na\in A$である．

そこで$A$の要素のうち，正の要素からなる部分集合に属する最小の要素を$d$とする． 自然数の集合には最小の要素が存在するので，$d$はつねに存在する．

$A$の任意の要素$a$をとり，それを$d$で割る．

$$a=dq+r\quad 0\le r <d$$

とおく．$d\in A$より$dq \in A$である．よって

$$r=a-dq \in A$$

ここでもし$r>0$なら$d$が正で最小の要素であることに反する． よって$r=0$，つまり$A$の任意の要素$a$は$d$の倍数である．

逆に，$d$の倍数が$A$に属することはすでに示した．

したがって $A=\{\ dn\ \vert\ n :整数 \}$が示せた．□

南海　 この$A$ように， 差と整数倍が再び$A$に属するような部分集合をイデアルというのだが， 有理整数のイデアルは，ある整数の倍数全体になる，ことを意味している．

1次不定方程式の解の存在

南海　 これを用いると次のことが示される．

定理 5
     $p$と$q$を互いに素な整数とする．このとき方程式

$$px+qy=1$$

は整数の解をもつ．

太郎　 この事実は知っていますが，証明は部屋割り論法を用いるものです．

部屋割り論法による証明

南海　 まづそれを復習しよう． 次の演習問題を解いてみてほしい．

演習 3   $a,\ b$ は互いに素な整数とする．

(1)

$k$ を整数とするとき， $ak$ を $b$ で割った余りを $r(k)$で表す． $k,\ l$ を $b-1$ 以下の正の整数とするとき， $k\ne l$ ならば $r(k)\ne r(l)$ であることを示せ．

(2)

$am+bn=1$ を満たす整数 $m,\ n$ が存在することを示せ．

太郎　 (1) 対偶を示す．

$$\begin{eqnarray*} r(k)= r(l)&\iff &ak-al=a(k-l) が b の倍数\\ &&(a と b は互い.. ...k-l 、ャ b 、ホヌワソ・\ &&-(b-2)\le k-l\le b-2 なので\\ &\iff &k-l=0 \end{eqnarray*}$$

よって $k\ne l$ ならば $r(k)\ne r(l)$であることが示された．

(2) $a$ と $b$ が互いに素なので， $1\le k \le b-1$ に対して $ak$ は$b$ の倍数とはならない． ゆえにこのとき $1\le r(k) \le b-1$ である．

一方 $k\ne l$ ならば $r(k)\ne r(l)$ なので $r(1),\ r(2),\ \cdots ,\ r(b-1)$ はすべて異なる $b-1$ 個の整数で， すべて $1\le r(k) \le b-1$ をみたす．

ゆえに鳩の巣原理により $r(1),\ r(2),\ \cdots ,\ r(b-1)$は $1,\ 2,\ \cdots,\ b-1$ の各値を一つずつとる． ゆえに$r(m)=1$ となる $m\ (1 \le m \le b-1)$ が存在する． つまり$am-1$ が $b$ の倍数である．これを $bn$ とおくと

$$am-1=bn \quad$$

すなわち，$am+bn=1$ を満たす整数 $m,\ n$ が存在することが示された．

南海　 この演習問題も，入試問題の改題だが， 高校数学ではこのように(1)を用いていわゆる部屋割り論法で 証明するのが普通だ．

実は定理4を用いる次の証明法の方が一般的だ．

なぜなら，変数を増やして$p,\ q,\ r$の最大公約数が1なら

$$px+qy+rz=1$$

は整数の解をもつことなども，まったく同様に示せる． 変数の数が多くなってもよい．

さて，定理4を用いる定理5の証明だ．

$$A=\{\ px+qy \ \vert\ xとyは整数\ \}$$

とおく．

$a=px_1+qy_1$，$b=px_2+qy_2$が$A$に属せば

$$a-b=p(x_1-x_2)+q(y_1-y_2)\in A$$

である．

したがって定理4より $A$は，$A$に属するある整数$d$の倍数の全体である． $d=px_0+qy_0$とする．

一方

$$p=p\cdot 1+q\cdot 0 \in A,\ q=p\cdot 0+q\cdot 1 \in A$$

なので，$p$も$q$も$d$の倍数である． つまり$d$は$p$と$q$の公約数である． $p$と$q$は互いに素なので，$d=1$である． つまり

$$px_0+qy_0=d=1$$

より方程式$px+qy=1$には解$(x_0,\ y_0)$が存在した．□

次: 整式の整数論 上: 整式の整数論 前: 整数と整式の類似