数学A / 整数の性質
1次不定方程式の整数解
問題
次の方程式を満たす整数 、 の組をすべて求めよ。
ヒントを見る
まず、当てはまる整数の組を1つ、代入して探す(小さい数で試す)。1つ見つかれば、 を ずつ・ を ずつずらしても等式が保たれる — その形で全部の解を書ける。
解答・解説
方針
まず、成り立つ整数解を1組『見つける』。次に、その解を基準にして、すべての解を文字 で表す。
解答
⓪ 発想 — どう考え始めるか。 を満たす整数の組は、 つではなく無限にある。だから「すべて求めよ」と言われている。
手順は 段階だ。
第 段: 解を つ、なんとかして見つける(特殊解)。 小さい数を代入して探せばよい。 とすると から 。
第 段: そこから、他のすべての解を作る。 見つけた解からどうずらせば、また解になるかを考える。
を 増やすと左辺は 増える。 を 減らすと 減る。プラマイちょうど — だからまた解になる。
は の係数()だけ、 は の係数()だけずらす。 ここが取り違えやすい急所である。
まず1組見つける。 小さい数を試すと、、 が当てはまる()。
全部の解を表す。 見つけた解を基準にする。 から、 を辺々引くと
左辺は の倍数だから、右辺 も の倍数。 と は互いに素なので、 のほうが の倍数でなければならない。( は整数)とおくと 。これを戻して 、つまり 、。
( の係数 と の係数 が、そっくり入れかわって『ずれ幅』になっているのがおもしろい。 で、最初に見つけた解に戻る。)
発展 — 一歩先へ。 の解を座標平面に打つと、直線 の上に、等間隔に並ぶ格子点になる。
方向に 、 方向に ずつ、規則正しく並んでいる。 「不定方程式を解く」とは、直線上の格子点をすべて捕まえることだったのだ。
そして、この構造は現実の問題を解く。
「 円切手と 円切手を組み合わせて、ちょうど 円ぶんにしたい。何枚ずつ買えばよいか」
今度は 「非負整数解」だけが意味を持つ。無限にある解のうち、 かつ のものだけを拾う — 範囲で絞るわけだ。
さらに面白い問いがある。「 円と 円の切手で、どうやっても作れない金額は何か?」
— 調べると、 円が最大の作れない金額で、 円以上はすべて作れる。この最大値には公式があって
フロベニウスの硬貨問題と呼ばれる有名な結果だ(、 が互いに素なときに成り立つ)。
「解が無限にある」不定方程式に、「範囲」という条件を足すと、有限で味わい深い問題に変わる。 入試の整数問題は、たいていこの形をしている。
、( は整数)
別解
特殊解を「勘で探す」のが不安なら、合同式で機械的に絞り込める。 係数が大きい問題では、こちらのほうが確実だ。
両辺を で割った余りで見る()。
は の倍数なので、 では消える。 だから
「 を で割ると 余る」と分かった。 つまり
は、元の式に代入して出す。
答え: 、( は整数)。
あれ、本解と形が違う。 本解は 、 だった。どちらが正しいのか?
どちらも正しい。同じ解の集合を、違う"番地"で書いているだけである。
確かめよう。本解の に を代入すると
ぴったり一致した。 のふり方(どの解を「」と呼ぶか)が つずれているだけなのだ。
実際に解をいくつか並べてみれば、同じ集合だと分かる。
どちらの式も、この同じ列を生み出す。 出発点(特殊解)をどこに取るかで、式の見た目は変わる — しかし解の集合は つである。
だから、答えが教科書と違って見えても、あわてないこと。 をずらして一致するか確かめればよい。
合同式ルートの利点。 特殊解を勘で探さなくてよいので、係数が大きいときに強い。たとえば のような問題では、代入で解を探すのは苦しいが、 で を絞り込めば機械的に進める(もっと大きな係数なら、互除法を逆にたどる方法もある)。
この方程式が解けるのは、 と が互いに素だからである。もし なら、左辺は必ず の倍数なのに右辺は — 解は つも存在しない。
解く前に、まず解があるかを確かめる — これが不定方程式の作法である。
ポイント
- まず特別な解(特殊解)を1組見つける
- 『 の係数と の係数を入れかえた分』ずつずらすと全解が出る
- 互いに素であることが、解の形を決めるカギ
よくある間違い
- 特殊解を1組見つけただけで答えとしてしまう(全解を で表す)
- ずれ幅の と を取り違える( は の係数分、 は の係数分ずれる)
- 答えの見た目が解答と違うだけで間違いだと思ってしまう( のずらし方が違うだけで同じ解集合のことがある)