１次不定方程式とは？
$ax+by=c$の形をした方程式の整数解を求める問題を、１次不定方程式といいます。
ただし、$a, b, c$は整数です。
例えば、$3x-5y=0, 22x+5y=3, 2x+y=1$などの整数解を求めていくことになります。
$22x+5y=3$に着目してください。
$x, y$の二つの文字があるにもかかわらず、式は一つしかありません。
つまり、１次不定方程式の解は沢山ありえます。（ただ一組には定まらないのです）
これ結構重要なことなので覚えておいてください。（ちなみに解がない場合もあります）
１次不定方程式を解いていくにあたって、必要となる知識が２つほどあるので、まずその確認をします。
互いに素
互いに素という言葉があります。
２つの整数に対して使う言葉です。
あえて定義は与えません。
今から、２つの整数を互いに素なグループと、そうでないグループに分けるので、互いに素とはどういうときにつかう言葉であるのか予想してみてください
互いに素なグループ
$2と3$, $4と9$, $12と17$, $19と21$, $125と81$, $5と8$など
互いに素でないグループ
$4と8$, $55と22$, $6と10$, $12と123$, $54と20$, $34と17$など
どうですか？ 規則性は見つかりましたか？
２つの整数$a, b$について、その最大公約数が１であるとき、互いに素と言います。（定義）
ちなみに、$4と5$や$121と122$など、連続する２つの数は必ず互いに素になります。
この性質はた入試でもたまに使う知識なので、受験的にも覚えておいて損はないでしょう。
倍数の表し方
例えば３の倍数について考えましょう。
$\cdots, -6, -3, 0, 3, 6, 9, 12, 15, 18, \cdots$
これを掛け算で表してみます。
$\cdots, 3×(-2), 3×(-1), 3×0, 3×2, 3×3, 3×4, 3×5, 3×6, \cdots$
３の倍数は沢山ありますが、どれも３×（整数）という形をしています。
そこで、３の倍数を$3k (k は整数)$と表します。
１次不定方程式では、この表記をめっちゃ使うので、慣れておいてください。
では、実際に１次不定方程式を解いていきましょう
$(1) 3x-5y=0 の整数解を全て求めよ$
$(2) 7x-2y=1の整数解を１つ求めよ$
$(3) 41x-14y=1の整数解を１つ求めよ$
$(4) 41x-14y=1の整数解を全て求めよ$
$(5) 41x-14y=5の整数解を全て求めよ$
(1) $3x-5y=0$ の整数解を 全て求めよ
１次不定方程式を解くときには、問題文を読んだ段階で注目しなければならないポイントが２つあります。
１つ目は、$ax+by=c$の$c$の値です。
$c=0$か、$c=1$か、$c=0, 1以外か$で対応が変わるので、まずは$c$の値に注目です。
２つ目は、文末の表現です。
「整数解を１つ求めよ」なのか、「整数解を全て求めよ」なのかも重大な違いなので、そこも押さえておきます。
見出しの問題は、$c=0$で、「整数解を全て求めよ」です。
早速やっていきましょう。
まず、今回は$c=0$のケースです。
これの何が嬉しいかというと、するっと移項できる点です。
解答
$3x-5y=0$より、$3x=5y$
$3x=5y$の左辺に着目すると、$3x$は$3$の倍数である。
左辺が$3$の倍数なので、右辺も$3$の倍数でなければならない。
よって、$5y$は$3$の倍数である。
$5y$について、$3$と$5$は互いに素なので、$5$は$3$の倍数にはなりえない。
よって、$y$が$3$の倍数でなければならない。
同様に考えると、$x$は$5$の倍数でなければならない。
したがって、$x=5k, y=3k(kは整数)$となる。
解答終了
(2) $7x-2y=1$ の整数解を1つ求めよ
今回は、「整数解を１つ求めよ」パターンです。
とにかく解を見つけることが重要なので、手あたり次第試してみます。
試しに$x=1, y=1$を代入してみましょう。
$7×1-2×1=5$
ふむ。
右辺が$1$にならないので、$x=1, y=1$は解になりません。
では$x=1, y=3$はどうでしょう。
$7×1-2×3=1$
よさそうです。
解答
$x=1, y=3が、求める整数解の一組となる$
解答終了
「整数解を１つ求めよ」パターンは、まずは手あたり次第あてずっぽう作戦で頑張ります。
(3) $41x-14y=1$ の整数解を１つ求めよ
今回も「整数解を１つ求めよ」パターンです。
が、(2)と違ってあてずっぽう作戦はやる気がおきません。
あてずっぽう作戦をやるには、数が大きくて計算が面倒すぎます。
このように、あてずっぽう作戦を断念したら、次はシステマチックな作戦でいきます。
具体的には、ユークリッドの互除法を使います。
$41$と$14$は互いに素なので、余りが$1$になったら終了です。
$41=14×2+13\cdots ①$
$14=13×1+1\cdots ②$
ここで、①と②の式を、あまり＝の形に変形します。
$41=14×2+13→ 13=41-14×2\cdots ①’$
$14=13×1+1→ 1=14-13\cdots ②’$
ここで、元の式に戻ってみましょう。
$41x-14y=1$
要するに、４１が何個で、１４が何個だと１が作れるか、ということを知りたいわけです。
ゴールとしては、$41×〇-14×△=1$の形を作れればよいことになります。
ここで、②’に着目してください。
$1=14-13$
すでに左辺に１がいます。ゴールの式のうち、すでに半分できあがっています。
あとは、右辺を１４と１３ではなく、４１と１４で表すことができればフィニッシュです。
そこで、②’の１３に①’を代入します。
$1=14-(41-14×2)$
ここで、１４×２を計算して２８にしてはいけません。
なぜか。
今回は、あくまでも４１が何個で、１４が何個だと１が作れるか、ということを考えています。
１４の個数が数えやすい形を維持した方が得なのです。
$1=14-(41-14×2)$
$1=14-41+14×2$
左辺には１４が合計３個います。
$1=14×3-41$
よって$-41+14×3=1$
あとは元の式$41x-14y=1$と見比べて微調整です。
解答
$41×(-1)-14×(-3)=1$
よって、$x=-1, y=-3$は$41x-14y=1$の整数解の一組となる。
解答終了
(4) $41x-14y=1$の整数解を全て求めよ
はい、今回は$c=1$でしかも「整数解を全て求めよ」パターンです。
これは少しだけ難しいです。
まず、基本的に「整数解を全て求めよ」パターンは、$c=0$の時しか解けません。
なので、$41x-14y=1$をどうにか変形して$41〇-14△=0$の形にする必要があります。
どうするか。
ここで天才的な発想を使います。
$1-1=0$を使います。
この発想マジで天才です。
思いついた人すごいと思います。
何がどう天才なのか伝わっていないと思うので、具体例で考えていきます。
手順としては、こうです
１．まずは$41x-14y=1$の整数解を$1$つ求める
２．引き算して$41〇-14△=0$の形を作る
３．互いに素と利用して答えを記述する
順にみていきましょう。
まず、$41x-14y=1$の整数解ですが、すでに（３）で$x=-1, y=-3$を求めているので、これを流用します。
解答
$41x-14y=1\cdots ③$
$41×(-1)-14×(-3)=1 \cdots ④$とする。
ここで、$③-④$より、
$(41x-14y)-\lbrace 41×(-1)-14×(-3)\rbrace=1-1$
これを$41$と$14$でまとめる。
$41x-14y-41×(-1)+14×(-3)=0$
$41(x+1)-14(y+3)=0$
$41(x+1)-14(y+3)=0$より、
$41(x+1)=14(y+3)$
$41, 14$は互いに素より、$x+1$は$14$の倍数であり、$y+3$は$41$の倍数となる。
よって、$x+1=14k, y+3=41k(kは整数)$
求める整数解は、$x=14-1, y=41k-3(kは整数)$。
解答終了
(5) $41x-14y=5$ の整数解を全て求めよ
今回は$c=5$で、しかも「整数解を全て求めよ」です。
この問題ができたら、１次不定方程式に関しては免許皆伝といっていいでしょう。
基本的に（４）と同じ手順で進行していきます。
まずは$41x-14y=1$の整数解を$1$つ求めます。
(3)の$x=-1, y=-3$を今回も流用します。
ここで、え？$=5$じゃなくて$=1$でいいの？と思ったあなた！
するどい！！
でもとりあえず$=1$でいいんです。
今回は$5-5=0$を使いことになりますが、
$5$は$1×5$でつくるので！
解答
いま、$41×(-1)-14×(-3)=1$である。
これの両辺に右から$5$をかけると、
$\lbrace 41×(-1)-14×(-3)\rbrace ×5=1×5$
左辺について、分配法則より、
$41×(-1)×5-14×(-3)×5=5$
$41×(-5)-14×(-15)=5$
ここで、
$41x-14y=5\cdots ⑤$
$41×(-5)-14×(-15)=5\cdots ⑥$
$⑤-⑥$より、
$(41x-14y)-\lbrace 41×(-5)-14×(-15)\rbrace=5-5$
これを$41$と$14$でまとめる。
$41x-14y-41×(-5)+14×(-15)=0$
$41(x+5)-14(y+15)=0$
$41(x+5)-14(y+15)=0$より、
$41(x+5)=14(y+15)$
$41, 14$は互いに素より、$x+5$は$14$の倍数であり、$y+15$は$41$の倍数となる。
よって、$x+5=14k, y+15=41k(kは整数)$
求める整数解は、$x=14k-5, y=41k-15(kは整数)$
解答終了
お疲れさまでした！
補足
エキストラステージです。
$5x+10y=3$の整数解を全て求めよ
解く前にちょっと考えてみてください。
この問題は、(1)~(5)のどのパターンにもあてはまりません。
数学的な違いがあります。
どこが数学的に違うでしょうか？
→$xの係数5と、yの係数10が$互いに素ではないのです。
解答
$5(x+2y)=3$である。
よって左辺は$5$の倍数である。
$5$の倍数は$3$になりえない。
よって、$5x+10y=3$には整数解が存在しない。
解答終了
まとめ
今度こそお疲れさまでした！
・整数$a, b$の最大公約数が$1$のとき、互いに素という
・$ax+by=c$の整数解をもとめることを１次不定方程式という
・$1-1=0$
・$ax+by=c$は、$a, b$が互いに素ではない場合は整数解をもたない
これらのことがぼんやり頭に入っていれば十分です！
あとは問題演習で定着させましょう！
コメント