実践演習 整数系

不定方程式の整数解とその発展【ベズーの補題】【2000年度 大阪大学ほか】

例題はこちら(画像をクリックするとPDFファイルで開きます。)

\(a\) , \(b\) , \(c\) を整数として

\(ax+by=c\)

という形の不定方程式(ディオファントス方程式)の整数解を考えさせる問題は基本的なものから発展的なものまで幅広く問われます。

※不定方程式とは、方程式の数に対して未知数の方が多い方程式です。

本問は単なる整数解ではなく、非負整数解について考える内容になっています。

手を動かしてみると、何となく答えは予想出来ると思いますが、その予想をどのように記述でまとめるかが腕の見せ所です。

なお、本問は同じ年のJMO(日本数学オリンピック)でも出題されているようです。

(以下ネタバレ注意)

 

+ クリック(タップ)して続きを読む

実験してみると

実験

\(1=\)無理

\(2=\)無理

\(3=3\cdot 1 +5\cdot 0\)

\(4=\)無理

\(5=3\cdot 0+5\cdot 1\)

\(6=3\cdot 2+5\cdot 0\)

\(7=\)無理

\(8=3\cdot 1+ 5\cdot 1\)

\(9=3\cdot 3+5\cdot 0\)

\(10=3\cdot 0+5\cdot 2\)

\(11=3\cdot 2+5\cdot 1\)

\(12=3\cdot 4+5\cdot 0\)

\(13=3\cdot 1+5\cdot 2\)

\(14=3\cdot 3+5\cdot 1\)

\(15=3\cdot 5+5\cdot 0\)

\(16=3\cdot 2+5\cdot 2\)

まぁ、乱暴な言い方をすれば実験だけならサルでもできます。

ここから何を見出すかが問題でしょう。

まず、\(1\) ,  \(2\) ,  \(4\) ,  \(7\)  は無理だということが予想されます。

そしてどうやら \(8\) 以上の整数は \(3m+5n\) の形で表現できるようです。

そこで、 \(8\) 以上の整数についてよく観察してみると

\(3\cdot ○+5\cdot 1\)

\(3\cdot □+5\cdot 0\)

\(3\cdot △+5\cdot 2\)

という形で周期性をもっています。

このことから、\(3m+5n\) という形で表現しようと思ったら

\(n=0\) ,  \(1\) ,  \(2\)  で考えれば十分じゃね?

と洞察できたらしめたものです。

一般の整数で言えば

普段 \(ax+by=c\) という形で説明することが多いので、以下ではアルファベットを変更して

\(3x+5y=c\)

の整数解について考えてみます。

この負の整数でもOKということであれば、任意の整数 \(c\) に対して、

\((x \ , \ y)=(2c \ , \ -c)\)

という整数解 \((x \ , \ y)\) が存在します。

ベズーの補題

一般に、\(0\) でない整数 \(a\) ,  \(b\) の最大公約数を \(G\) としたとき

ベズーの補題

\(ax+by=c\) を満たす整数の組 \((x \ , \ y)\) が存在する\(\Leftrightarrow\) \(c\) が \(G\) の倍数

ということが言えます。

例題の【総括】のあとに【参考】として証明も載せてあります。

詳しい議論はそちらを参考にしてほしいのですが、大まかな流れだけ説明します。

step
1
\(c=1\) のときを証明する

\(ax+by=1\) を満たす整数の組 \((x \ , \ y)\) が存在する\(\Leftrightarrow\) \(a\) ,  \(b\) が互いに素

ということを示す。

step
2
その過程において

\(c=1\) のときの証明の過程で

\(a\) ,  \(b\)  が互いに素であるとき

\(a\) ,  \(2a\) ,  \(\cdots\) ,  \((b-1)a\) を \(b\) で割った余りは全て異なる

ということを示す。

※カッコつけた言い方をすると \(\{\)\(a\) ,  \(2a\) ,  \(\cdots\) ,  \((b-1)a\)\(\}\) は既約剰余系と呼ばれます。

カッコつけんなと不快に思われた方は無視してください。

ベズーの補題を証明するにあたって、上の2つの補題を利用します。

スタミナがないと、疲れるかもしれません。

類題について

類題はこちら(画像をクリックするとPDFファイルで開きます。)

例題の大阪大学の問題を部分的に一般化しています。

例題の大阪大学の問題では「この形で表せないものはなんだ?」という問いかけでしたが、本問は

「\(x \gt pq\) だったら、正の整数 \(a\) ,  \(b\) で \(x=pa+qb\) という形で書けるぜ」という主張です。

逆に言えば、\(x \lt pq\) のときについては \(x=pa+qb\) と表せる保証はないということになりますが、正であることを考えれば

\(0\) から \(pq-1\) までという有限個の範囲で考えれることになります。

そういった意味で、本問の主張は価値があるでしょう。

関連の話題

参考で扱ったベズーの補題の解説中に現れる既約剰余系の話は、余り \(0\) まで含めて言えば

\(a\) ,  \(b\)  が互いに素であるとき

\(a\) ,  \(2a\) ,  \(\cdots\) ,  \(ba\) を \(b\) で割った余りは全て異なる

ということになります。

※ 余り \(0\) まで含めたものは完全剰余系などと呼ばれたりします。

これは、「フェルマーの小定理」や、それを拡張した「オイラーの定理」とも関連しています。

関連の話題フェルマーの小定理【2項定理からのアプローチ】【2011年度 関西大学】

問題はこちら(画像をクリックするとPDFファイルで開きます。)   フェルマーの小定理 \(p\) を素数 , \(a\) を任意の自然数とするとき \(a^{p} \equiv a\)  ...

続きを見る

も併せてご活用ください。

例題の解答はコチラ

類題の解答はコチラ

-実践演習, 整数系
-

© 2022 MathClinic