本項の内容は、以下の基本的な型を習得済みであることを前提とする。
また、前項の正攻法を習得済みであることも前提とする。
1次不定方程式$ax+by=c$を解くには,\ まず解を1組見つける必要があるのであった.
前項で述べたように,\ ユークリッドの互除法を利用すると確実に見つけることができる.
しかし,\ 処理や記述が多くなりがちで,\ 時間制限のある試験では,\ できれば避けたい.
そこで合同式を利用する(裏技).\ この手法を使いこなせると素早く解を見つけ出せる.
問題で誘導される可能性もあるので,\ 互除法を習得しなくてもよくなるわけではない.
まず,\ 合同式の性質のうち,\ $ax+by=c$の解を見つける上で必要となるもののみ再確認する.
$[1]$\ \ $a ≡ b ±od m,\ c ≡ d ±od mのとき$（$a,\ b,\ c,\ d:整数,\ m:自然数$）
\ $和・差} a± c ≡ b± d ±od m} [\,法が同じ2式の両辺は足せる(引ける)}\,]}$
$[2]$\ \ $除法$（$x,\ y:整数,\ a,\ m:自然数$）
次に,\ 合同式を利用した1組の解のおおまかな求め方を示すと以下となる.
$a>b$のとき $ax+by=c$より $ax+by≡ c±od b$ (必要条件)
$by≡0±od b$より $ax≡ c±od b$
後は,\ 合同式の性質を用いて,\ \uwave{\.{気}\.{付}\.{き}を得ながらうまいこと}$x}$の係数を$±\,1}$にする.
こうして,\ $±\,x≡α±od b}$の形にできれば,\ 特殊解$x=±\,α$が求まったことになる. \\
$\left[l}
[2]\ 除法①は,\ aと法mが互いに素のとき,\ 両辺にaを掛けたり割ったりしてよい}ことを意味する.
\rei\ \ 3x≡6±od5\ ⇔\ \ x≡2±od5\ \ (3と5は互いに素)
aと法mが互いに素でないとき,\ 法も変化する([2]②). \rei\ \ 2x≡4±od6\ ⇔\ \ x≡2±od3
ax+by=cの解を見つけるとき,\ 最終的に± x≡α±od bにしたいので途中で法が変わると困る.
よって,\ 本項では,\ 法mと互いに素でない数を両辺に掛けたり割ったりすることはしない.
さて,\ 合同式を利用して特殊解を求めるときの最大のポイントは波線部である.
互除法の処理手順は1つだったが,\ 合同式では長いものから短いものまで無限の処理手順が存在する.
そのため,\ 短い処理手順の\dot{気}\dot{付}\dot{き}があって初めて合同式が真価を発揮する.}
それが具体的にどういうことかは,\ 以下の実際の問題で確認してほしい.
概ね難易度順に並んでおり,\ 後半になるほどより高度な気付きが必要になる.
(1)\ \ $63x+31y=5$ & (2)\ \ $65x+31y=6$
(3)\ \ $56x+31y=5$ & (4)\ \ $96x+59y=13$
より,\ 31を法とする.\ \ 31より大きな値は,\ 31で割った余りに変換して31より小さくする.
63=31･2+1より63≡1±od{31}であるから,\ 直ちに1x≡5が導かれる.
x≡5±od{31}を満たすx\ (31で割ると5余る数)は,\ ･･･,\ -\,26,\ 5,\ 36,\ ･･･\ と無数に存在する.
そのうちの1つを答えればよいので,\ 普通はそのまま答えれば済む.
yの値は,\ 求まったxの値を元の式に代入して求める. y=(5-63･5)÷31=-\,10
仮にx≡36±od{31}と求まった場合,\ 36≡5±od{31}と変換するとyが求めやすくなる.
文字通りの瞬殺であり,\ 合同式の絶大な効力に感服したかもしれない.
しかし,\ 実は一発で1xとなるように作問しただけであり,\ 一般にはこんな簡単にはいかない.
そもそも63=31･2+1\ (余り1})となるのならば,\ 5倍して63･5}+31･(-\,10})=5を導ける.
それゆえ,\ 合同式の優位性は低く,\ yの値を求めることも考慮すると互除法のほうが早いまである.
3と31は互いに素なので両辺を3で割れることに\.{気}\.{付}\.{い}\.{た\,]
3で割ると1xになることに気付く必要があるが,\ さすがにこれに気付かない学生はいまい.
ただし,\ 合同式の両辺を割るとき,\ 割る数が法と互いに素でなければ法が変わってしまう}のであった.
そういう意味では,\ 本問のように法が素数の場合は安心して割ることができる.
本問もほぼ瞬殺だが,\ もちろんそのように作問しただけである.
そもそも65=31･2+3\ (余り3})となるのならば,\ 2倍して65･2}+31･(-\,4})=6を導ける.
$x≡-\,6±od{31}$ & [\,5と31は互いに素なので両辺を5で割れる}\,]
xの係数は,\ 絶対値を小さくすることを優先するとより早く1xにできる}ことが多い.
そこで本解では,\ 56≡25ではなく,\ 負の剰余}を利用して56≡-\,6とした.
後は,\ 何とかして右辺を6の倍数にできれば,\ 特殊解が求まる.
31を法として5と合同な数の中で6の倍数を探ると,\ 5+31=36におそらく\dot{気}\dot{付}\dot{く}ことができる.
31を法として5と合同な数は,\ 5±31,\ 5±31･2,\ 5±31･3,\ ･･････\ と無限にある.
その中からすぐに見つかったのは,\ 残念ながらそう作問したからであり,\ 常にはこうはならない.
本解は早いが,\ そこまで難しくないとはいえ,\ 2つの\dot{気}\dot{付}\dot{き}が必要である.
本解の気付きが得られなかった場合を想定した別解を3つ示した.
別解1と別解2は1段階目で-6に気付かなかった場合の例である.\ 本問では,\ \dot{た}\dot{ま}\dot{た}\dot{ま}\,5で割れる.
よって,\ 後は右辺を5の倍数にすればよく,\ 別解1では負の剰余}を利用して1-31=-\,30とした.
本解も別解1も結局は負の剰余を利用しており,\ 慣れていないと少し気付きにくいかもしれない.
そこで,\ 負の剰余を利用しない例も示した(別解2).
別解2では,\ 1+31nが5の倍数になる自然数nを探し続け,\ 1+31･4=125に気付いている.
闇雲すぎる方法故に実戦では難しいと思ったかもしれないが,\ 実は次が知られている(後に学習).
完全剰余系の基本定理}
自然数n\ (≧2)と整数aが互いに素のとき,\ 1a,\ 2a,\ ･･･,\ na\ をnで割った余りはすべて異なる.
今はこれ自体の理解は必要ない.\ 本問に沿った内容にわかりやすく言い換えると以下となる.
5と31が互いに素より,\,31nやそれに1を足した1+31nを5で割ったときの余り(0\,～\,4)は,}
周期5で循環し,\ 1周期の中にただ1つずつ存在する.}
また,\ 次のように言い換えることができる.
5と31が互いに素より,\ 1+31n\ (n:連続5整数)を求めると5の倍数がただ1つ見つかる.}
以上の知識により,\ 確信をもって1+31･4=125を見つけられたというわけである.
連続5整数ならばn=0,\ ±\,1,\ ±\,2でもよく,実際n=-\,1のとき1+31n=-\,30であった(別解1).
余りは周期5で循環するので,\ n=･･･,\ -\,6,\ -\,1,\ 4,\ 9,\ ･･･\,のとき,\ 1+31nが5の倍数となる.
結局,\ xの係数を5程度にまで小さくできれば,\ 後は1周期をしらみつぶしする戦略も悪くはない.}
なお,\ 1+31nが5の倍数となるnを求めるとき,\mod5で考えるのもよい.
本問の場合,\ 1+31n≡1+1･ n≡0±od5となるのはn=-\,1やn=4のときである.
最後,\ x=25としてyを求めたが,\ x≡25≡-\,6よりx=-\,6とできればyが求めやすくなる.
別解3は,\ 両辺を何倍かしてxの係数を(法)±1にする}ものである.
法を31とした最初の時点で「\,xの係数を32や30\ (31を法として±1と合同)に･･･」と考えておく.
すると,\ -\,6xができた瞬間に両辺を5倍すればよいことに気付くことができる.
もちろん,\ 31で割って±1余る数ならば何でもよいので,\ 63や61などを想定しておくのもよい.
しかし,\ 31±1以外の数はそれを求めること自体に時間がかかるのであまり実戦的とはいえない.
互除法を利用して求める正攻法は以下であり,\ \dot{気}\dot{付}\dot{き}さえあれば合同式が圧倒的に優位である. 結局,\ 本問程度ならば,\ 次の2点さえ意識しておけば10秒ほどで嫌でもx≡-\,6に到達できる.
「(右辺)±(法)でxの係数の倍数にならないか」}
「両辺を何倍かしてxの係数を(法)±1にできないか」}
とりあえず37x≡13\ (負の剰余を利用すると-22x≡13)となるが,\ この後が問題である.
13+59nが37や22の倍数になるような整数nを求めるのは難しい.
n=±\,1のときは37や22の倍数ではないし,\ n=±\,2,\ ･･･\,を考えるのは闇雲すぎて実戦的ではない.
同様に,\ 37や22を何倍かして法59で割って±1余る数にするのも難しく,\ 運頼みが過ぎる.
結局,\ 前問で述べた2点以外の視点が必要になるのだが,\ 幸いなことに全く難しくない.
まず,\ すでにできた2式①,\ ②のxの係数96と37に着目する.
96>37より96÷37をすると96=37･2+22,\ つまりは96-37･2=22}となる.
よって,\ ②を2倍した式を①から引けば,\ xの係数を22にできる}とわかる.
これにより④となるが,\ 当然掛ける数と法が互いに素でなければならない}ことに注意する.
また,\ 最初に確認しておいたように,\ 法が同じ2つの合同式の両辺は足し引きしてよい}のであった.
なお,\ 負の剰余を利用していれば,\ 1段階目でこの22x≡-13に到達できた.
④までの処理の重要性が理解できただろうか.
余りは必ず割る数より小さくなるから,\ これを繰り返せば確実にxの係数が小さくなる}わけである.
つまり,\ \dot{気}\dot{付}\dot{き}は必要なく,\ 機械的に繰り返していけば済む.}
次は,\ xの係数の小さい②と④に着目すると,\ 37-22･1=15より,\ ②-④をすればよいとわかる.
さらに,\ 22-15･1=7\ (④-⑤),\ 15-7･2=1\ (⑤-⑥×2)により,\ \dot{必}\dot{然}\dot{的}に1xとなる.
最後,\ yの値を求めやすいようにxの絶対値を小さくした.
要するに,\ 本解は本質的には互除法と同じである.
ただし,\ 合同式は,\ 互除法よりも少ない記述量で済み,\ もし途中で\dot{気}\dot{付}\dot{き}があれば利用できる.}
例えば,\ 15xになった時点で(法59)+1にできることに気付けば,\ 4倍して即終了である.
⑤×4より\ \ 60x≡104 60≡1より\ \ x≡104±od{59}
別解は,\,とりあえず既存の式を何倍かしてみる}ものである.
このとき,\ 考えすぎる必要はないが,\ xの係数が法59の倍数に近くなるのが好ましい.}
例えば,\ 2倍によってxの係数は74x≡15xとなるし,\ 3倍によって111x≡-\,7xとなる.
うまい気付きを得ようと変に考えている暇があれば,\ 適当に何倍かしてまず式を増やすのがよい.
式が多くなるほど,\ うまい式の組合せの\dot{気}\dot{付}\dot{き}が得られやすくなる.
別解では,\ 適当に2倍してみたところ15xができた.
上に74があり,\ 15を5倍すると74との差が1になるという\dot{気}\dot{付}\dot{き}を得たので③×5-②とした.
気付きがあればどうにでもできるし,\ 気付きがなければ本解のように確実に1xに近づけていく.
(4)までの手法を理解できていれば,\ 後は自分で手を動かして慣れるだけである.
是非自分で様々な問題を作って試してみてもらいたいが,\ 問題作成する上で1つ重大な注意点がある.
注意！ ax+by=cを作るとき,\ aとbが互いに素な整数となるようにする.}
a,\ bが互いに素でなかった場合,\ 解が存在しなくなったりなど話がややこしくなる(後に詳しく学習).
不定方程式$67x-60y=1$の整数解を求めよ. 小さい60を法としたいが,\ 60=2^2･3･5なので2,\ 3,\ 5の倍数を掛けたり割ったりできなくなる.
後が面倒になるので,\ 絶対値にそれほど差がない素数の67を法とした(本解).
yの係数が法67に近くなるように10倍し,\ その後7=3･2+1より,\ ①-②×2とした.
もちろん,\ (法67)-1となるように22倍し,\ 66y≡220より-y≡220≡19としてもよい.
法を60とした別解も示した.\ 2,\ 3,\ 5の倍数を掛けることができないので,\ とりあえず7倍してみる.
後は2式の足し引きだけで1xを導くことを目指した.
途中,\ うっかり-4x≡8を-x≡2とするなどしてしまわないように注意！}
別解2では,\ 7と60が互いに素なので,\ 右辺を7の倍数にすることを目指した.
1+60n≡1+4n≡0±od7を満たすnの1つは,\ n=-\,2である. 1+60･(-\,2)=-\,119
合同式の利用は裏技扱いとなるため,\ 記述試験で使用してよいかが気になる学生も多いだろう.
しかし,\ そもそも括弧内は記述する必要がなく,\ 答案用紙には\maru{ A}の行から書き始めれば十分である.
ax+by≡ cは必要条件にすぎない}ので,\ 中途半端に合同式を書くと論理不足と見なされかねない.
