ユークリッドの互除法(応用)特殊解を見つける方法を解説

ユークリッドの互除法応用編/不定方程式第3回

・「ユークリッドの互除法を使って最大公約数を求める方法」に続いて、

一次不定方程式の一般解を求めるときに必要な、”特殊解を互除法で探す方法”を解説していきます。

・これまでの不定方程式は、以下にまとめています。

→「不定方程式の解き方(1)：因数分解利用型」

→「不定方程式の解き方(2):絞り込み利用型」

ユークリッドの互除法と不定方程式とは

冒頭でも紹介した「不定方程式」ですが、簡単に復習すると、

（未知数の数が式の数より多いため）解がひとつに定まらない（＝不定）方程式のことを言います。

詳しくは第1回・第2回をご覧ください。

そして、今回学ぶ”一次不定方程式”は、3x+5y=1,(x,yは整数）のような式の(x,y)の値を求めるものです。

一般解の求め方のSTEP

実際に、3x+5y=1・・・（※） の整数解を探してみると、(-3,2)や(2,-1)など無数に解の組みが見つかります。

当然、解を無数に書くことはできないので、適当な文字を使って『一般解』を表します。

ex：x=5n-3、y=-3n+2 (ただし、nは整数）←これが一般解と呼ばれるものです。

試しにn=0,1・・・と代入してみると(-3,2),(2,-1)をはじめ、すべての（※）の解が表せることを確認できます。

では、このように大変便利な『一般解』はどのようにして求めるのか、『3x+5y=1』を例題として、STEP by STEPで解説していきます。

1-1:特殊解を見つける

一般解に対して”特殊解”と呼ばれるものがあります。

これは、(２,-1)のように『3x+5y=1』を満たすもののうちの特定の一つの解の事をいいます。

一次不定方程式では、まずこの”特殊解”を見つけることが最初にして最大の問題です。

1-2:式を連立して引く

さて、無数にある解の中からどれか一つでも特殊解を見つけたら、問題の（※）の式の下に特殊解を代入した式（※※)を書きます。

3・x+5・y＝1・・・（※）

3・2+5・(-1)=1・・・（※※)

ここで右辺を0にするために、連立した（※)ー（※※)を行います。

引き算して整理すると、3(x-2)+5(y+1)=0となります。

1-3:互いに素を利用する

この式を移項して、5(y+1)=-3(x-2)・・・(★)

ここで5と3は互いに素、かつ(左辺)=(右辺)なので、(x-2)は5の倍数であるはずです。・・・(★★)

同じく、(y+1)も(-3)の倍数です。・・・（★★★)

1-4:一般解を文字を使って表す

ここまで来ると、あとは数式に変換するだけで答えが作れます。

（★★）より、n(nは整数)を使って(x-2)＝5n。

⇔x＝5n＋2

（★★★)より、(y+1)=-3n

⇔y＝ー3nー1

よって、x,yの一般解は、(x= 5n +2、y=-3n-1)・・・（答）

特殊解が見つけにくい場合の対策

ここまでは、特殊解が簡単に求まるような場合でした。しかし、例えば『313x+79y=1』のようにx,yの係数が非常に大きい場合はどうでしょう。

一つ一つ数を代入して実験していくことで、いずれは特殊解を見つけることはできるでしょうが、時間がかかる上に、ミスをしたら一発でアウトです。

ユークリッドの互除法の利用

このように、特殊解を見つけるのが困難なときには、”カンタンな問題をどのようにして解いてきたか”を振り返ってみます。

・特殊解の発見→式の連立→互いに素の利用

という流れで解いてきました。313x+79y=1の場合も同じように解くことになります。

ところで、「互いに素」という言葉は「最大公約数が1」と同義でした。

さらに、「大きな数」、そして「最大公約数」とくれば『ユークリッドの互除法』が浮かびます！

(浮かばない、、という人は→「ユークリッドの互除法と最大公約数」をご覧下さい。)

では、一次不定方程式にどのようにしてユークリッドの互除法を応用するのか、

先ほど挙げた『313x+79y=1』を使って、実際に問題形式で解説します。

2-1:互除法で最大公約数1を目指す

ユークリッドの互除法で最大公約数を探すときに用いた手順を使って、どんどん計算を進めていきます。

313÷79=3...76

79÷76=1...3

76÷3=25...1・・・（☆）

商が１になったところで計算を止めます。

ここで、（☆）の割る数”3”と余りの”１”の最大公約数は”１”であることから、

313と79の最大公約数も”１”、すなわち互いに素であることがわかりました。

2-2:余りが1から式を組み立てる

次に、今我々は313×○＋79×△＝１となる特殊解を探していたので、

（☆）の式を１＝のカタチに変形します。

1=76-25×3

以下同様に、割り算を繰り返した式をすべて(余り)＝　のカタチにします。

3=79-76×1

76=313-79×3

まだ何をしているのかわからないと思いますが、もう少しでこの操作の意味がわかります。

1=76-25×3 の3に、 3=79-76×1を代入します。

1=76ー25×(79-76×1)

⇔1=76×26-79×25さらに、この"76"に76＝313-79×3を代入

1=(313-79×3)×26ー79×25

⇔1=313×26ー79×103

⇔313×26＋79×(-103)・・・（☆☆）

ここで、☆☆の式をみると、はじめに探していた

313×○＋79×△＝１の形になっています！

2-3:特殊解の発見

すなわち、『ユークリッドの互除法を使い→余り１＝の形にどんどん変形した式を代入→目的の式へ』という操作をすることで、”○=26”,”△=-103 ”という”特殊解”を見つける作業をしていたのです。

2-4:以降は手順1-2と同じ

かなり面倒でしたが、特殊解（の１組）が見つかってしまえば、残りのすることは同じです。

313・x＋79・y＝１

313・26+79・(-103)=1

連立して上の式ー下の式を行うと、

313(x-26)+79(y+103)=0 ここで、313と-79は互いに素だったので、

n(nは整数）を用いて、(x-26)=-79n ,313n=(y+103)

よって、x＝-79n+26、y=313n-103 が一般解（答）

不定方程式のまとめと関連記事一覧

・一次不定方程式の問題で、係数部分が大きい場合や、中々特殊解が見つからない場合は『ユークリッドの互除法』の利用を考える。

・一般解は無数にあるので、○n+△（nは整数）の形で解答する

このタイプは計算量が多く、慣れがないとミスをしやすいので類題を問題集などで探してどんどん解いていきましょう。

不定方程式シリーズ

１：「因数分解を使って解を求めるタイプ」

２：「条件から絞り込んで解を求めるタイプ」

３：「今ここです」

ユークリッドの互除法

１：「ユークリッドの互除法がこの記事でわかる！仕組み解説」

２：「今ここです」

その他の整数問題の解放解説記事は以下でまとめています。

「整数分野の問題をセンスなしで解くための解説記事総まとめ」

最後までご覧いただきまして、ありがとうございました。

いいね！やB!、シェア、Twitterのフォローをしていただけると助かります！

その他のお問い合わせ・ご依頼などに付きましては、お問い合わせページよりお願い致します。