互除法を用いて1次不定方程式の整数解を1つ求める

・ax+by=1の整数解(1つ)例題1
・ax+by=cの整数解(1つ)例題2



ax+by=cを満たす整数x,yの組を1つ見つけるには以下の2つがよく使われます.

 [1] 適当に数字を入れてみる

 [2] 互除法を利用して解く

[1]の方法は単純ですが,a,bの値が小さいときは比較的簡単に見つけられるので便利です.ここでは[1]の方法で見つけられなかった場合を想定して,互除法を利用した方法について説明します.



【例題 1】
次の方程式の整数解を1つ求めなさい.

互除法を利用q1




STEP 1
xの係数(23)とyの係数(5)の最大公約数を互除法を使って解きます.
互除法についてはこちらを参照してください.

互除法を利用q1a1

計算の結果,最大公約数は1ということがわかりました.ただ,必要なのは式自体で最大公約数は知る必要はありません.また,余りが0の式は使わないので削除しておきます.



STEP 2
互除法で作った式は(割られる数)=(割る数)×(商)+(余り)という式になっているはずですが、これを移項することによって(余り)=(割られる数)-(割る数)×(商)という形に変えます。

互除法を利用q1a2

赤字で表示されている部分に注意してください。次のステップでは赤字になっている部分を使って式を整理していきます。



STEP 3
一番下の式からスタートして下から式を順番に代入していきます。

互除法を利用q1a3
※整理のポイント
整理するのは右辺だけです.左辺は何も変えません.
赤字の部分を計算して別の数にしてはいけません.
最終的に,いつも1 = a×m + b×nの形になるように整理します.
赤字の数字をまとめるときは共通因数をくくると考えるとよいでしょう.


一番上の式まで代入して整理したら完成です.今考えている問題は23x+5y=1という方程式のxとyにどんな整数を入れれば式が成り立つかというものでした.

最後の式はxの部分が2に,yの部分が-9になっています.よって,x=2,y=-9がこの1次不定方程式の1つの解となります.



続いて,c が1ではない場合の解き方について例を使って説明します.c=1のやり方が分かっていればこれは簡単です.



【例題 2】
次の方程式の整数解を1つ求めなさい。

   




STEP 1
まず,cの部分を1にして整数解を求めます.ax+by=1の整数解の出し方は上で説明した通りです.解き方は例題 1を見てください.ここでは結果だけ書いておきます.

   

この式をそのまま利用します.x,yの部分に括弧を付けておきましょう(これは説明の便宜のためなので,2の所には付けなくても問題ありません).



STEP 2
カッコの中と右辺をc倍(今回はc=7なので7倍)します。

   

23x+5y=7のx,yの部分がそれぞれ14,-63になっています.よって,x=14,y=-63が整数解の1つとなります.



スポンサーリンク

コメント
助かりました
最高。テスト2日前で切羽詰まってた。ありがとうございました。
2016/04/06(水) 14:21 | URL | j #-[ 編集]
No title
整理の部分が難しくてよく分からない
2016/06/12(日) 00:25 | URL | #-[ 編集]
承認待ちコメント
このコメントは管理者の承認待ちです
2017/08/29(火) 23:44 | | #[ 編集]
コメントの投稿
管理者にだけ表示を許可する
スポンサーリンク
最新記事
検索フォーム
ランキング