割り算定理(剰余の定理)の証明

本記事の内容

本記事は割り算定理を証明する記事です。

本記事を読むに当たり、論理の初歩を知っている必要があるため、以下の記事も合わせてご覧ください！

※シリーズ化しているため、一部の記事のリンクを貼っています。

「命題とは？」【論理と集合シリーズ】数学の文章を読むための論理的思考の基礎　その１

...

for-spring.com

2022.01.15

“整数”とは何者か？

(初等)整数論を学ぶにあたって、何よりもまず真っ先に浮かぶ疑問としては

があると思います。
しかし、これについて答えようとすると数学基礎論の話に入ります。
加えて、このトピックは比較的重い内容になってしまいます。

公理として自然数を導入して…などとすると、整数そのものの面白さにたどり着くまで時間がかかってしまいます。
そこで、本シリーズでは

という立場を取らせていただきます。
また、実数も知っているとします。
※実数の構成(連続性)については実数の連続性を御覧ください。

ただ、「整数とは何か」という素朴な疑問は数学を専攻している如何に依らず、面白い内容だと思いますので、別の記事で述べようと思います。

本シリーズにおける”整数”

「本シリーズにおける”整数”」という節名をつけましたが、要するによく知られている整数を本シリーズでも整数と呼びますよ、という単にそれだけのお話です。

具体的には
$$
\cdots\cdots,-3,\ -2,\ -1,\ 0,\ 1,\ 2,\ 3,\cdots\cdots
$$
です。
ここで、整数全体の集合を\(\mathbb{Z}\)で表します。
つまり
$$
\mathbb{Z}=\left\{\cdots\cdots,-3,\ -2,\ -1,\ 0,\ 1,\ 2,\ 3,\cdots\cdots\right\}
$$
です。
自然数全体の集合を\(\mathbb{N}\)と書くと、\(\mathbb{Z}\)は
$$
\mathbb{Z}=\mathbb{N}\cup \{0\}\cup \left\{-n\middle|n\in\mathbb{N}\right\}
$$
と書くこともできます。

ちなみに

自然数といえば、モノを数えるときに使う数\(1,\ 2,\ 3,\cdots\)を指すことが多いですが、流儀として\(0\)を自然数に含める場合があります。
これはあくまで流儀ですので、どちらが正しいという話ではないのですが、筆者の印象としては現代では\(0\)は自然数には含まれない流儀をとる数学者が多いです。
本ブログでも、\(0\)は自然数には含まれないという立場を取ります。
すなわち、\(0\not\in \mathbb{N}\)という立場を取ります。

整数の整除

整数の和、差、および積はまた整数です。
しかし、商は特別な場合のほかは整数ではありません。
その商が整数である場合に「割り切れる」と言います。

これによれば、\(0\)は\(0\)でない任意の整数\(b\)の倍数です。

また、\(x\in\mathbb{Z}\)に対して\(\left|x\right|\)を\(x\)の絶対値とすると、\(a,b\in\mathbb{Z}\)に対して\(\left|a\right|<\left|b\right|\)で\(a\)が\(b\)で割り切れるときは、\(a=0\)です。
実際、\(\left|a\right|<\left|b\right|\)であれば、
$$
\left|\frac{a}{b}\right|<1
$$
となり、今\(a\)が\(b\)で割り切れるから
$$
(\exists q\in\mathbb{Z})\quad q=\left|\frac{a}{b}\right|
$$
となります。
このとき、
$$
0\leq q=\left|\frac{a}{b}\right|<1
$$
であるため、\(q=0\)でなければなりません。
したがって、\(\displaystyle\frac{a}{b}=0\)となるわけです。

基本的な性質

「何をアタリマエのことを？」と思われるかもしれません。
筆者も最初「アタリマエじゃんね」と思いましたが、その「アタリマエ」はあくまで経験則から来るもので直感的に理解できているに過ぎないと気が付きました。
「そりゃそうじゃん」というアタリマエのことも実はしっかり体系付けられている、ということを肌で感じることができるということも整数論の面白さの一つだと感じています。

定理1.の証明

簡単です。
\begin{eqnarray}
&&\frac{a_1x_1+a_2x_2+\cdots+a_nx_n}{b}\\
&=&\frac{a_1}{b}x_1+\frac{a_2}{b}x_2+\cdots+\frac{a_n}{b}x_n
\end{eqnarray}
となります。
仮定から、\(a_i\in\mathbb{Z}\ (1\leq i\leq n)\)は\(b\in\mathbb{Z}\)の倍数、すなわち
$$
(\forall i\in \left\{1,2,\cdots,n\right\})\ (\exists q_i\in\mathbb{Z})\ {\rm s.t.}\ q_i=\frac{a_i}{b}
$$
であるため、
\begin{eqnarray}
&&\frac{a_1}{b}x_1+\frac{a_2}{b}x_2+\cdots+\frac{a_n}{b}x_n\\
&=&q_1x_1+q_2x_2+\cdots+q_nx_n\in\mathbb{Z}
\end{eqnarray}
となるから成り立ちます。

定理1.の証明終わり

割り算定理

本題です。

実は、割り算定理はすでに知っています。

「すでに知っています」というと少々語弊がありますが、何を言いたいかと言うと、大学で初めて出現する定理ではない、ということです。
実は、定理という形ではありませんが、小学生のときにすでに使っています。

小学生に戻ってみましょう。
例えば、「\(15\)個のリンゴを\(6\)人で分けました。一人あたり何個もらえて何個余るでしょう？」という問題を出されたとします。
このとき

と答えたはずです。

余談(読み飛ばしてOK)

筆者が小学生の頃、割り算の単元でこの問題を出されました。
当時の筆者は先生に「余りません」と答えました。
「どうして？」と聞かれ、当時の筆者は「3人が3個もらえて、その他の人は2個もらえるからです」と答えたようです(うろ覚えですが)。
今思うと屁理屈をこねているなあなんて思いました。おわり

このとき、(筆者の記憶では)同じ単元で

と習いました。
実は、これが割り算定理です。

割り算定理の明示とその証明

初等整数論を学ぶ上で、恐らく一番最初に学ぶ定理がこの割り算定理です。
なぜかと言うと、初等整数論の中で最も基本的で、基礎となる定理だからです。
ありとあらゆる事実がこの割り算定理から導かれます。

要するに、割り算定理というのは、どんな整数も

という形で一意的に書ける、ということなのです。

定理0.(割り算定理、剰余の定理)の証明

①\(a\geq0\)かつ\(b>0\)のとき

\(b>0\)であるので、\(bq\leq a\)を満たすような自然数\(q\)は高々有限個しか存在しません。
これはアルキメデスの公理というもので、本ブログでは認めます。

さて、\(bq\leq a\)を満たすような自然数\(q\)は高々有限個しか存在しないため、\(q\)を新たに、その中で最大のものとします。
\(r=a-bq\)としましょう。
もし、\(r\geq b\)であったのなら、\(r-b\geq0\)であるから、
$$
r-b=a-bq-b=a-b(q+1)\geq0
$$
が成り立ちます。
しかし、\(q\)は\(bq\leq a\)、すなわち\(a-bq\geq0\)を満たす最大のものだったはずですので、矛盾です。
したがって、\(r<b\)ということになります。
このとき、\(a\geq bq\)のため、\(r\geq0\)です。

②\(a,b\)が必ずしも正とは限らないとき

\(a,b\)が必ずしも正とは限らない場合でも、\(\left|a\right|\)および\(\left|b\right|\)を考えれば、①から
$$
(\exists q,r\in\mathbb{Z})\ {\rm s.t.}\ \left|a\right|=\left|b\right|q+r\quad 0\leq r\leq \left|b\right|
$$
となります。

• ②-1. \(a\geq0\)かつ\(b<0\)の場合
  $$
  \left|a\right|=\left|b\right|q+r\Longleftrightarrow a=-bq+r\Longleftrightarrow a=b(-q)+r
  $$
  となります。
  このとき、\(-q\)および\(r\)は主張の性質を満たすため、\(q\)として新たに\(-q\)を取り直せばOKです。
• ②-2. \(a<0\)かつ\(b>0\)の場合
  もしこのとき\(r>0\)であれば、
  $$
  a=-bq-r=b(-q-1)+b-r
  $$
  です。
  さらに、\(b>0\)かつ\(0\leq r<b\)であるから、\(0\leq b-r<b\)です。
  実際、\(0\leq r<b\)から\(b-r> 0\)であり、\(b>b-r\)だから\(0\leq b-r<b\)となります。
  次に\(r=0\)であれば、\(a=-bq\)です。
• ②-3. \(a<0\)かつ\(b<0\)の場合
  \(0<r\)であれば、
  $$
  a=bq-r=b(q+1)-b-r=b(q+1)+\left|b\right|-r
  $$
  です。
  さらに、②-2.と同様にして\(0\geq \left|b\right|-r<\left|b\right|\)です。
  \(r=0\)のときは、\(a=bq\)です。

したがって、すべての場合で\(q,r\)の存在が示されました。

③一意性

もし、\(a\)が2種類の\(q,r\)で\(a=bq+r\)と書けたとしましょう。
つまり、
\begin{eqnarray}
a&=&bq+r\quad 0\leq r\leq \left|b\right|\\
a&=&bq^\prime+r^\prime\quad 0\leq r^\prime\leq \left|b\right|
\end{eqnarray}
としましょう。
これを辺々で引き算すると、
$$
b(q-q^\prime)=r^\prime-r
$$
となります。
これはまさに\(r^\prime-r\)は\(b\)で割り切れることを表しています。
ここで、\(\left|r^\prime-r\right|<\left|b\right|\)です。
実際、\(r\geq0\)により\(r^\prime-r\leq r^\prime<\left|b\right|\)です。
また、\(r^\prime\geq0\)により
$$
r^\prime-r\geq0\geq -r>-\left|b\right|
$$
です。
故に、\(r^\prime-r\geq-r>\left|b\right|\)です。
以上により、
$$
-\left|b\right|<-r\leq r^\prime-r\leq r^\prime<\left|b\right|
$$
となるから、\(\left|r^\prime-r\right|<\left|b\right|\)です。

さて、\(q-q^\prime\neq0\)だったとすると、\(\left|q-q^\prime\right|\geq0\)により
$$
\left|b\right|\cdot \left|q-q^\prime\right|\geq \left|b\right|
$$
となります。
しかしながら、これは
$$
\left|b\right|\cdot \left|q-q^\prime\right|=\left|b(q-q^\prime)\right|=\left|r^\prime-r\right|<\left|b\right|
$$
に矛盾です。
したがって、\(q-q^\prime=0\)でなければなりません。
故に、\(r^\prime-r=0\)となるため、\(q=q^\prime\)かつ\(r=r^\prime\)です。

定理0.(割り算定理、剰余の定理)の証明終わり

皆様のコメントを下さい！

割り算定理は、意味自体はすでに小学校で出現しますが、いざ証明仕様となると割と骨が折れます。
「今までアタリマエだと思っていたことが実は証明ができる」ということが筆者の整数論の面白いと思う要素の1つです。

皆様はそういう経験がありますか？
「これって証明できるんだ…」と思ったものを是非コメントで教えて下さい！

結

今回は、割り算定理(または剰余の定理とも)の証明をしました。
概念自体は小学校で既出でしたし、暗に使っていたのではないでしょうか。
実は、整数論でしっかり証明される事実なのです。
この割り算定理から整数論の諸事実が導かれます(あとは素因数分解定理)。

次回は最大公約数、最小公倍数についてお話します。

乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければ全てお答えします！
お問い合わせの内容にもよりますが、ご質問はおおよそ１週間以内にお答えします。
(難しかったらもう少しかかるかもしれませんが…)

初等整数論について、以下の書籍をオススメします！