数学A / 整数の性質
1次不定方程式の自然数解
問題
を満たす自然数 、 の組をすべて求めよ。
ヒントを見る
の形にする。右辺が『 の倍数 かつ 正』でなければ は自然数にならない。 が の倍数になる を、余りで絞ってから範囲で仕上げる。
解答・解説
方針
片方の文字について解き、それが自然数になる条件を絞る。倍数の条件(割り切れるか)と『正の整数』の範囲で、候補が有限個に決まる。
解答
⓪ 発想 — どう考え始めるか。 求めるのは自然数解。だから一般解を書く前に、範囲で絞る手が使える。
について解くと 。これが自然数になるには、 が の倍数で、しかも正でなければならない。
「 の倍数」は余りの条件、「正」は不等式の条件。この つで の候補が有限個に落ちる。
不定方程式に自然数という範囲がつくと、この絞り込みそのものが解答の本体になる。
について解く。
が自然数になるには、右辺 が『 の倍数』かつ『正』でなければならない。
の倍数の条件: を で割った余りを考える。、 なので 。これが になるのは 、つまり 。よって 。
正の条件: より 、つまり 。
合わせると 。それぞれ を求める。
- :、
- :、
- :、
発展 — 一歩先へ。 の整数解は、 つの解を見つければ が ずつ、 が ずつずれる形で無数に並ぶ。今回はそのうち自然数のものだけを取り出した。
係数が互いに素なら、右辺がどんな整数でも整数解は必ず存在する。 と が互いに素だから解があった。
と で「表せない最大の金額」は という有名な事実にもつながる。額面 円と 円の硬貨で作れない最大値を問う、フロベニウスの問題だ。
別解
別解 — つの解から一般解を作って範囲で絞る(得意な人向けの視点)。 余りで絞るかわりに、まず解を 組だけ見つけて、そこからすべてを書き出す。
を見ると、、 が で成り立つ。これを土台の解にする。
係数が と だから、 を 増やして を 減らしても和は変わらない。一般解は
自然数、つまり かつ を課す。 より 、 より 。だから 。
余りで絞る本解と同じ 組に至る。
ポイント
- 片方の文字について解き、割り切れる条件を余りで絞る
- 『正の自然数』の範囲で候補を有限にする
- 余りの条件()で一気に候補が減る
よくある間違い
- と片端から代入するだけで、解の抜けや数え間違いをする。
- かつ という自然数の範囲を外れた解( で など)を含めてしまう。
- が の倍数になる を余りで絞らず、正の条件だけで候補を広げすぎる。