ユークリッドの互除法を利用するより応用的なタイプはこちら。
本項の重要さが一目瞭然でわかるツイート^^
共通テスト(旧センター試験)数IA整数の出題内容㊙️
— 受験の月φ(．． ) (@examoonist) January 5, 2022
2015本 ax+by=1
2015追 ax+by=1
2016本 ax+by=1
2016追 ax+by=1
2017追 ax+by=1
2018本 ax+by=1
2018追 ax+by=1
2019本 ax+by=1
2019追 ax+by=1
2020本 ax+by=1
2020追 ax+by=1
2021(1) ax+by=1
2022 ❓
3x-5y=1\ の整数解を求めよ.$ \\[.8zh]
\hspace{.5zw}$(2)\ \ 49x+24y=19\ の整数解を求めよ.$ \\[.8zh]
\hspace{.5zw}$(3)\ \ 3x+2y=10\ の整数解を求めよ.$ \\
ax+by=c型の不定方程式}}$}} \\\\
$ax+by=c$型の不定方程式は整数分野の最重要テーマの1つである. \\[.2zh]
本項では,\ 単なる不定方程式の1種として理屈抜きで解を求める手順を示すに留める. \\[.2zh]
整数カテゴリでは,\ 関連事項をかなり深く掘り下げて取り扱う. \\\\
$ax+by=c$の前に,\ 基本となる「\,$\bm{\textcolor{blue}{aX=bY型\ (a,\ b:互いに素)}}$\,」の解法を確認する. \\[.2zh]
$\bm{\textcolor[named]{ForestGreen}{aとbが互いに素\ (\pm\,1以外の共通の約数を持たない)}}がこの型の重要ポイントである.$ \\[1zh]
最も簡単な例として,\ $\bm{\textcolor{magenta}{2X=3Y}}の整数解を考えてみてほしい.$ \\[.2zh]
右辺$3Y$は3の倍数なので,\ この等式が成立するには左辺も3の倍数でなければならない. \\[.2zh]
\textcolor{magenta}{2と3は互いに素}であるから,\ 左辺$2X$が3の倍数となるとき$X$が3の倍数となる. \\[.2zh]
\textcolor{cyan}{$X=3k\ (k:整数)$}とおくことができ,\ このとき$2\cdot3k=3Y$より$Y=2k$となる. \\[.2zh]
つまり,\ $2X=3Y$の整数解は$\bm{\textcolor{magenta}{(X,\ Y)=(3k,\ 2k)\ (k:整数)}}$である. \\[.2zh]
$(X,\ Y)=(3,\ 2),\ (6,\ 4),\ (-\,3,\ -\,2)$など,\ \textcolor{magenta}{無数の整数解が存在する}ことに注意してほしい. \\[1zh]
同様に,\ $\bm{\textcolor{red}{aX=bY\ (a,\ b:互いに素)}}$の整数解は$\bm{\textcolor{red}{(X,\ Y)=(bk,\ ak)\ (k:整数)}}$となる. \\[.2zh]
これを基本として$ax+by=c$型の不定方程式を解くことになる. \\\\
加えて,\ 以下に示す整数分野の最重要定理を知っていると問題の見通しがよくなる. \\[.2zh]
$a,\ b,\ x,\ yを整数とする.$ \\[.5zh]
\centerline{{\large $\bm{「\,\textcolor{red}{a,\ bが互いに素のとき,\ ax+by=1を満たすx,\ yが無数に存在する}\,」}$}} \\[.5zh]
証明は整数カテゴリで示すので,\ 本項ではとりあえず認めて欲しい. \\[.2zh]
この定理は,\ (1)のような不定方程式が必ず整数解をもつことを主張している. \\[.2zh]
さらに,\ $\bm{\textcolor{cyan}{ax+by=1の両辺をc倍}}することにより,\ \bm{\textcolor{cyan}{a(cx)+b(cy)=c}}とできる.$ \\[.2zh]
よって,\ $\bm{\textcolor{red}{aX+bY=c型も,\ 必ず整数解(X,\ Y)=(cx,\ cy)をもつ}}といえる.$ \\[.2zh]
なお,\ $a,\ bが互いに素ではない場合には整数解が存在するとは限らない.$ \\[.2zh]
例えば,\ $4x+6y=1は2(2x+3y)=1とできるが,\ (偶数)=1より整数解は存在しない.$ \\\\\\
以上を踏まえて,\ $\bm{\textcolor{blue}{ax+by=c型\ (a,\ b:互いに素)の解法}}$を示す. \\[1zh]
$aX=bY$型に帰着させることが解法の肝である. \\[.2zh]
そのためには,\ まずは\textbf{\textcolor{red}{何とかして整数解$\bm{(x,\ y)}$を1組見つける}}必要がある. \\[.2zh]
上で示した定理により存在は保証されている. \\[.2zh]
(1)の$3x-5y=1$程度ならば,\ ちょっと考えればすぐに見つけられるだろう. \\[.2zh]
ただし,\ 以下の事実を知っていると確信を持って見つけることができるようになる. \\[.5zh]
\centerline{$\bm{\textcolor{magenta}{0\leqq x\leqq b-1または0\leqq y\leqq a-1を調べると,\ 必ず解が1組見つかる.}}$} \\[.5zh]
よって,\ $a,\ bの値の小さい方に着目して1つずつ調べていけばよい.$ \\[.2zh]
例えば,\ $3x-5y=1ならば,\ 0\leqq y\leqq2よりy=0,\ 1,\ 2を代入してみると1組見つかる.$ \\[.2zh]
$0\leqq x\leqq4よりx=0,\ 1,\ 2,\ 3,\ 4を代入しても1組見つかるが,\ 面倒である.$ \\[.2zh]
こうして整数解を1組見つけることさえできれば,\ 後は以下の機械的な作業で解が求まる. \\\\
$ax+by=cの1組の整数解を\textcolor{cyan}{(\alpha,\ \beta)}とする.$ \\[.2zh]
次のように,\ $\bm{\textcolor{red}{元の式から(x,\ y)に(\alpha,\ \beta)を代入した式を引く.}}$ \\[.5zh]
特殊解型漸化式(数\text B)の解法と同様の手法であり,\ この(\alpha,\ \beta)を\textbf{特殊解}という. \\[.2zh]
筆算を答案に書く必要はなく,\ 慣れれば直ちに\ a(x-\alpha)=-\,b(y-\beta)\ と記述すればよい. \\[1zh]
-\,a(x-\alpha)=b(y-\beta)より,\ x-\alpha=bk,\ y-\beta=-\,akとしてもよい.
y=0,\ 1,\ 2を代入するだけであるから,\ 特殊解はすぐに見つかる. \\[.2zh]
どのようにして特殊解を見つけたかを答案に記述する必要はない. \\[.2zh]
後は,\ 基本手順に従ってaX=bY型に帰着させるだけである. \\[1zh]
仮に特殊解として(7,\ 4)を用いると,\ 解はx=5k+7,\ y=3k+4\ (k:整数)となる. \\[.2zh]
特殊解として何を用いるかで解答の見かけ上の形は変わるが,\ 以下の集合を表すことに変わりはない. \\[.2zh]
5k+2も5k+7=5(k+1)+2も5で割って2余る数を表しており,\ 一致するのは当然なのである.
49x+24y=19は,\ 係数の値が大きく,\ 特殊解を見つけることが容易ではない. \\[.2zh]
もちろん,\ x=0\,～\,23を代入すると必ず見つかるはずではあるが,\ 相当面倒である. \\[.2zh]
結果を見る限り,\ (19,\ -\,38),\ (-\,5,\ 11),\ (-\,29,\ 60)等を代入して初めて特殊解が見つかる. \\[1zh]
このようにax+by=cのcの値が大きい場合,\ まず\bm{ax+by=1の特殊解を見つける}とよい. \\[.2zh]
49x+24y=1の特殊解ならば,\ 少し勘を働かせると見つけることができるだろう. \\[.2zh]
その後,\ \bm{両辺をc倍}することにより,\ ax+by=cの特殊解を作り出すことができる. \\[.2zh]
ax+by=1ですら特殊解を見つけることが難しい場合の対処法については整数カテゴリで紹介する.
ax+by=cにおいて\bm{aとcまたはbとcが共通因数をもつならば,\ 単純にくくり出せば済む.} \\[.2zh]
いちいち特殊解を求めずとも,\ aX=bY型に帰着させることができる.
\hspace{.5zw}$(2)\ \ 49x+24y=19\ の整数解を求めよ.$ \\[.8zh]
\hspace{.5zw}$(3)\ \ 3x+2y=10\ の整数解を求めよ.$ \\
ax+by=c型の不定方程式}}$}} \\\\
$ax+by=c$型の不定方程式は整数分野の最重要テーマの1つである. \\[.2zh]
本項では,\ 単なる不定方程式の1種として理屈抜きで解を求める手順を示すに留める. \\[.2zh]
整数カテゴリでは,\ 関連事項をかなり深く掘り下げて取り扱う. \\\\
$ax+by=c$の前に,\ 基本となる「\,$\bm{\textcolor{blue}{aX=bY型\ (a,\ b:互いに素)}}$\,」の解法を確認する. \\[.2zh]
$\bm{\textcolor[named]{ForestGreen}{aとbが互いに素\ (\pm\,1以外の共通の約数を持たない)}}がこの型の重要ポイントである.$ \\[1zh]
最も簡単な例として,\ $\bm{\textcolor{magenta}{2X=3Y}}の整数解を考えてみてほしい.$ \\[.2zh]
右辺$3Y$は3の倍数なので,\ この等式が成立するには左辺も3の倍数でなければならない. \\[.2zh]
\textcolor{magenta}{2と3は互いに素}であるから,\ 左辺$2X$が3の倍数となるとき$X$が3の倍数となる. \\[.2zh]
\textcolor{cyan}{$X=3k\ (k:整数)$}とおくことができ,\ このとき$2\cdot3k=3Y$より$Y=2k$となる. \\[.2zh]
つまり,\ $2X=3Y$の整数解は$\bm{\textcolor{magenta}{(X,\ Y)=(3k,\ 2k)\ (k:整数)}}$である. \\[.2zh]
$(X,\ Y)=(3,\ 2),\ (6,\ 4),\ (-\,3,\ -\,2)$など,\ \textcolor{magenta}{無数の整数解が存在する}ことに注意してほしい. \\[1zh]
同様に,\ $\bm{\textcolor{red}{aX=bY\ (a,\ b:互いに素)}}$の整数解は$\bm{\textcolor{red}{(X,\ Y)=(bk,\ ak)\ (k:整数)}}$となる. \\[.2zh]
これを基本として$ax+by=c$型の不定方程式を解くことになる. \\\\
加えて,\ 以下に示す整数分野の最重要定理を知っていると問題の見通しがよくなる. \\[.2zh]
$a,\ b,\ x,\ yを整数とする.$ \\[.5zh]
\centerline{{\large $\bm{「\,\textcolor{red}{a,\ bが互いに素のとき,\ ax+by=1を満たすx,\ yが無数に存在する}\,」}$}} \\[.5zh]
証明は整数カテゴリで示すので,\ 本項ではとりあえず認めて欲しい. \\[.2zh]
この定理は,\ (1)のような不定方程式が必ず整数解をもつことを主張している. \\[.2zh]
さらに,\ $\bm{\textcolor{cyan}{ax+by=1の両辺をc倍}}することにより,\ \bm{\textcolor{cyan}{a(cx)+b(cy)=c}}とできる.$ \\[.2zh]
よって,\ $\bm{\textcolor{red}{aX+bY=c型も,\ 必ず整数解(X,\ Y)=(cx,\ cy)をもつ}}といえる.$ \\[.2zh]
なお,\ $a,\ bが互いに素ではない場合には整数解が存在するとは限らない.$ \\[.2zh]
例えば,\ $4x+6y=1は2(2x+3y)=1とできるが,\ (偶数)=1より整数解は存在しない.$ \\\\\\
以上を踏まえて,\ $\bm{\textcolor{blue}{ax+by=c型\ (a,\ b:互いに素)の解法}}$を示す. \\[1zh]
$aX=bY$型に帰着させることが解法の肝である. \\[.2zh]
そのためには,\ まずは\textbf{\textcolor{red}{何とかして整数解$\bm{(x,\ y)}$を1組見つける}}必要がある. \\[.2zh]
上で示した定理により存在は保証されている. \\[.2zh]
(1)の$3x-5y=1$程度ならば,\ ちょっと考えればすぐに見つけられるだろう. \\[.2zh]
ただし,\ 以下の事実を知っていると確信を持って見つけることができるようになる. \\[.5zh]
\centerline{$\bm{\textcolor{magenta}{0\leqq x\leqq b-1または0\leqq y\leqq a-1を調べると,\ 必ず解が1組見つかる.}}$} \\[.5zh]
よって,\ $a,\ bの値の小さい方に着目して1つずつ調べていけばよい.$ \\[.2zh]
例えば,\ $3x-5y=1ならば,\ 0\leqq y\leqq2よりy=0,\ 1,\ 2を代入してみると1組見つかる.$ \\[.2zh]
$0\leqq x\leqq4よりx=0,\ 1,\ 2,\ 3,\ 4を代入しても1組見つかるが,\ 面倒である.$ \\[.2zh]
こうして整数解を1組見つけることさえできれば,\ 後は以下の機械的な作業で解が求まる. \\\\
$ax+by=cの1組の整数解を\textcolor{cyan}{(\alpha,\ \beta)}とする.$ \\[.2zh]
次のように,\ $\bm{\textcolor{red}{元の式から(x,\ y)に(\alpha,\ \beta)を代入した式を引く.}}$ \\[.5zh]
特殊解型漸化式(数\text B)の解法と同様の手法であり,\ この(\alpha,\ \beta)を\textbf{特殊解}という. \\[.2zh]
筆算を答案に書く必要はなく,\ 慣れれば直ちに\ a(x-\alpha)=-\,b(y-\beta)\ と記述すればよい. \\[1zh]
-\,a(x-\alpha)=b(y-\beta)より,\ x-\alpha=bk,\ y-\beta=-\,akとしてもよい.
y=0,\ 1,\ 2を代入するだけであるから,\ 特殊解はすぐに見つかる. \\[.2zh]
どのようにして特殊解を見つけたかを答案に記述する必要はない. \\[.2zh]
後は,\ 基本手順に従ってaX=bY型に帰着させるだけである. \\[1zh]
仮に特殊解として(7,\ 4)を用いると,\ 解はx=5k+7,\ y=3k+4\ (k:整数)となる. \\[.2zh]
特殊解として何を用いるかで解答の見かけ上の形は変わるが,\ 以下の集合を表すことに変わりはない. \\[.2zh]
5k+2も5k+7=5(k+1)+2も5で割って2余る数を表しており,\ 一致するのは当然なのである.
49x+24y=19は,\ 係数の値が大きく,\ 特殊解を見つけることが容易ではない. \\[.2zh]
もちろん,\ x=0\,～\,23を代入すると必ず見つかるはずではあるが,\ 相当面倒である. \\[.2zh]
結果を見る限り,\ (19,\ -\,38),\ (-\,5,\ 11),\ (-\,29,\ 60)等を代入して初めて特殊解が見つかる. \\[1zh]
このようにax+by=cのcの値が大きい場合,\ まず\bm{ax+by=1の特殊解を見つける}とよい. \\[.2zh]
49x+24y=1の特殊解ならば,\ 少し勘を働かせると見つけることができるだろう. \\[.2zh]
その後,\ \bm{両辺をc倍}することにより,\ ax+by=cの特殊解を作り出すことができる. \\[.2zh]
ax+by=1ですら特殊解を見つけることが難しい場合の対処法については整数カテゴリで紹介する.
ax+by=cにおいて\bm{aとcまたはbとcが共通因数をもつならば,\ 単純にくくり出せば済む.} \\[.2zh]
いちいち特殊解を求めずとも,\ aX=bY型に帰着させることができる.
