例題はこちら（画像をクリックすると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 \(ax+by=1\) を満たす整数の組 \((x \ , \ y)\) が存在する\(\Leftrightarrow\) \(a\) , \(b\) が互いに素 ということを示す。 step \(c=1\) のときの証明の過程で \(a\) , \(b\) が互いに素であるとき \(a\) , \(2a\) , \(\cdots\) , \((b-1)a\) を \(b\) で割った余りは全て異なる ということを示す。 ※カッコつけた言い方をすると \(\{\)\(a\) , \(2a\) , \(\cdots\) , \((b-1)a\)\(\}\) は既約剰余系と呼ばれます。 カッコつけんなと不快に思われた方は無視してください。 ベズーの補題を証明するにあたって、上の２つの補題を利用します。 スタミナがないと、疲れるかもしれません。 例題の大阪大学の問題を部分的に一般化しています。 例題の大阪大学の問題では「この形で表せないものはなんだ？」という問いかけでしたが、本問は 「\(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\) まで含めたものは完全剰余系などと呼ばれたりします。 これは、「フェルマーの小定理」や、それを拡張した「オイラーの定理」とも関連しています。 問題はこちら（画像をクリックするとPDFファイルで開きます。） フェルマーの小定理 \(p\) を素数 , \(a\) を任意の自然数とするとき \(a^{p} \equiv a\) ... 続きを見る も併せてご活用ください。実験してみると
一般の整数で言えば
ベズーの補題
1\(c=1\) のときを証明する
2その過程において類題について
類題はこちら（画像をクリックするとPDFファイルで開きます。）
関連の話題
関連の話題フェルマーの小定理【２項定理からのアプローチ】【2011年度 関西大学】