ユークリッドの互除法による1次不定方程式の特殊解の出し方
整数(教科書範囲) ★★★
数学Aの整数で，ほとんどの生徒を1度は悩ます問題がこれです．1次不定方程式で特殊解が暗算で見つからない場合の対処法を扱います．
ユークリッドの互除法が既習である前提です．
例題
例題
$155x+42y=1$ を満たす整数 $(x,y)$ の組を1組求めよ．
講義
勘で見つけるのが困難なタイプです．教科書通りの正攻法で解く方法を解説します．
$155$ が $x$ 個と，$42$ が $y$ 個足して $1$ になるという問題で(当然今回は $x$ か $y$ どちらか負)，ユークリッドの互除法を使って解きます．
解答と解説
ユークリッドの互除法を用いて，$155$ と $42$ の最大公約数が1(互いに素)であることを計算して確認します．
上のように，余りが最大公約数である1になったらやめます．
そして，余りが重要なので，一番下の余りに色をつけます．余りはすぐ割る数にもなるので，2段目の余りにも色をつけます．
次に，方程式の係数である $155$ と $42$ に違う色をつけます．
準備ができました．
余り=割られる数ー割る数×商
というブロックを，当てはめては整理してを繰り返していきます．今回ならば
$1$ = $13$ ー $3$ $\times 4$
$3$ = $29$ ー $13$ $\times 2$
$13$ = $42$ ー $29$ $\times 1$
$29$ = $155$ ー $42$ $\times 3$
4本のブロックを材料として用意します．
1番上のブロックから始めて，右辺の色がついた数字をまるで文字かのように破壊しないように扱い，色がついた数字の小さい方をブロックを使って代入しては整理してを繰り返します．
最後の行を見ると，$\boldsymbol{155}$ が $\boldsymbol{(-13)}$ 個と $\boldsymbol{42}$ が $\boldsymbol{48}$ 個で $\boldsymbol{1}$ になることがわかりますので求める答えは
$(x,y)=\boldsymbol{(-13,48)}$
式変形の心構え
右辺は常に，色がついた数字は2種類になるようにし，ブロックを使って小さい色を式変形をします．変形したらその都度整理するようにします．
上の色付けでいうと，しばらく赤が続きますが，だんだん青くなっていき，最後に真っ青になればOKです．そのときの係数が特殊解です．
余りと方程式の係数を大切に扱い，式変形していきましょう．
練習問題
練習
(1) $133x-30y=1$ を満たす整数 $(x,y)$ の組を1組求めよ．
(2) $85x+206y=2$ を満たす整数 $(x,y)$ の組を1組求めよ．
解答
(1)
$\begin{align}\color{red}{1}&=\color{red}{13}-\color{red}{4}\times 3 \\ & =\color{red}{13}-(\color{blue}{30}-\color{red}{13}\times2)\times3 \\ & =\color{red}{13}\times7-\color{blue}{30}\times3 \\ & =(\color{blue}{133}-\color{blue}{30}\times4)\times7-\color{blue}{30}\times3 \\ & =\color{blue}{133}\times7-\color{blue}{30}\times31\end{align}$
よって整数解の1組は $(x,y)=\boldsymbol{(7,31)}$
(2)
$\begin{align}\color{red}{1}&=\color{red}{10}-\color{red}{3}\times 3 \\ & =\color{red}{10}-(\color{red}{13}-\color{red}{10}\times1)\times3 \\ & =\color{red}{10}\times4-\color{red}{13}\times3 \\ & =(\color{red}{36}-\color{red}{13}\times2)\times4-\color{red}{13}\times3 \\ & =\color{red}{36}\times4-\color{red}{13}\times11 \\ &=\color{red}{36}\times4-(\color{blue}{85}-\color{red}{36}\times2)\times11 \\ & =\color{red}{36}\times26-\color{blue}{85}\times11 \\& =(\color{blue}{206}-\color{blue}{85}\times2)\times26-\color{blue}{85}\times11 \\ & =\color{blue}{85}\times(-63)+\color{blue}{206}\times26\end{align}$
よって整数解の1組は上の解を2倍して $(x,y)=\boldsymbol{(-126,52)}$