おいしい数学ホームへのリンク

ユークリッドの互除法による1次不定方程式の特殊解の出し方

タイプ:教科書範囲 レベル:★★★ 


アイキャッチ

数Aの整数で,ほとんどの生徒を1度は悩ます問題がこれです.

ユークリッドの互除法がわからない方はこちらをご覧ください.





ユークリッドの互除法による1次不定方程式の特殊解の出し方(例題)

例題

例題

$155x+42y=1$ を満たす整数 $(x,y)$ の組を1組求めよ.


講義

勘で見つけるのが困難なタイプです.

教科書通りの正攻法で解く方法,そしてネットには素早く解く方法が色々紹介されていますが,どれも慣れが必要です.ここでは記述式を意識して正攻法で解く方法を解説します.

$155$ が $x$ 個と,$42$ が $y$ 個足して $1$ になるという問題で(当然今回は $x$ か $y$ どちらか負),ユークリッドの互除法を使って解きます.


解答と解説

ユークリッドの互除法を用いて,$155$ と $42$ の最大公約数が1(互いに素)であることを計算して確認します.


ユークリッドの互除法1

上のように,余りが最大公約数である1になったらやめます.


そして,余りが重要なので,一番下の余りに色をつけます.余りはすぐ割る数にもなるので,2段目の余りにも色をつけます.


ユークリッドの互除法2

次に,方程式の係数である $155$ と $42$ に違う色をつけます.

ユークリッドの互除法3

準備ができました.


余り=割られる数割る数×商


というブロックを,当てはめては整理してを繰り返していきます.今回ならば

$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) $85x+206y=1$ を満たす整数 $(x,y)$ の組を1組求めよ.

(2) $162x+125y=2$ を満たす整数 $(x,y)$ の組を1組求めよ.

練習の解答



ノートに戻る