ユーグリッド互除法を用いた解法のコツ

【GOM Mix】初心者でも簡単な動画編集ソフト

皆さんユーグリッドの互除法を用いた解法に不慣れな方は先ずは慣れることです。練習あるのみ。これに尽きます。それでは慣れるためのコツを書いておきます。シンプルですが大切だと思うのでご覧ください。ただし, これは私はこうやって覚えましたという方法なので, 他に覚えやすい方法があればそれをご参照ください。それでは参ります。

余り＝～に変形して代入

問題： $13x+31y=1$ を満たす整数 $x, y$ の組を1組見つけよ。
手順としては左辺の $x$ , $y$ の係数を大きい方を小さい方で割って、商と余りで大きい数31を小さい数13を用いて表していきます。それが以下の $\maru1$ になります。
$31=13\cdot2+5\cdots\maru1$
次に割る数の13を余りの5で割って, 同じように, 商と余りで大きい方の数13を小さい方の数5を用いて表していきます。それが以下の $\maru2$ になります。
$13=5\cdot2+3\cdots\maru2$
次も同様に割る数5を余り3を用いて表すと, 以下の $\maru3$ になります。
$5=3\cdot1+2\cdots\maru3$
同様に最後に割る数3を余り2で表すと, 余りが1になります。それが $\maru4$ の状態です。
$3=2\cdot1+1\cdots\maru4$
この $\maru4$ の余りが1の状態に, $\maru3$ , $\maru2$ , $\maru1$ の順で式を置き換えていくのですが, このとき, ①～④の式をすべて(余り) $\textcolor{red}{=}$ ～の形に等式変形します。
$\maru1$ より $5=31-13\cdot2\cdots(a)$
$\maru2$ より $3=13-5\cdot2\cdots(b)$
$\maru3$ より $2=5-3\cdot1\cdots(c)$
$\maru4$ より $1=3-2\cdot1\cdots(d)$
このように(余り) $\textcolor{red}{=}$ ～の形に式変形して $\textcolor{red}{(c), (b), (a)}$ の順に1つずつ置き換えていくのが攻略のポイントとなります。それと掛け算したときに, 掛け算の結果を書いてしまわないことです。 $\textcolor{blue}{13\cdot2}$ はそのままで, 26としないことです。目標は13と31を用いて1という数字をつくることですから。以下見ていきましょう。
$(d)$ に $(c)$ をあてはめて,
$1=3-(5-3\cdot1)$
$1=-5+3\cdot2$
これに $(b)$ をあてはめて,
$1=-5+2(13-5\cdot2)$
$1=13\cdot2-5\cdot5$
これに $(a)$ をあてはめて,
$1=13\cdot2-5(31-13\cdot2)$
$1=13\cdot12+31\cdot(-5)$
よって、問題の $13x+31y=1$ と比較して $(x, y)=(12, -5)$ となる。

先のやり方が今一な人へ

ここまでのやり方がうまくいかない人は, 上の例題で, (余り)＝～の形に変形した後, $a=13$ , $b=31$ と文字でおいて, その都度 $a, b$ で置き換えて表していくことをお勧めします。どういうことかと申しますと,
$31=13\cdot2+5\cdots\maru1$
$13=5\cdot2+3\cdots\maru2$
$5=3\cdot1+2\cdots\maru3$
$3=2\cdot1+1\cdots\maru4$
ここまでは同じ
①～④の式をすべて(余り) $\textcolor{red}{=}$ ～の形に等式変形します。
ここで, $a=13$ , $b=31$ に置き換えるのです。
①より $5=31-13\cdot2=b-2a\cdots(a)$
②と $(a)$ より $3=13-5\cdot2=a-2(b-2a)=5a-2b\cdots(b)$
③と $(a), (b)$ より $2=5-3\cdot1=(b-2a)-(5a-2b)=-7a+3b\cdots(c)$
④と $(b), (c)$ より $1=3-2\cdot1=(5a-2b)-(-7a+3b)=12a-5b\cdots(d)$
となり, $(d)$ から
$12a-5b=1$
つまり,
$13\cdot12+31\cdot(-5)=1$
が得られるという仕組みになります。
最初のやり方がしっくりこない方はこちらを試してみてください。