ユークリッドの互除法　～さんすう・数学のお勉強～

ユークリッドの互除法

●　ユークリッド　●

　ユークリッドといったら、「ユークリッド幾何」で有名ですね。

　「ユークリッド幾何」なんて知らな～いって？
　ご心配なく！みなさんが学校で習ったふつうの幾何のことです。
　こんなに長きにわたって、それも世界中で学ばれるなんて、
きっとユークリッドも考えてもいなかったでしょうね。
　（もっとも、「ユークリッド幾何」でない「幾何」が出てくるなんて
もっと考えていなかったかもしれないけど・・・・・）

　でも、こんなことは、もっと予想してなかったでしょうね。
　やがてコンピュータの時代がきて、
「ユークリッドの互除法（ごじょほう）」が注目をあびる・・・。

　さて、その「ユークリッドの互除法」っていうのは、何でしょう。

　「除法（じょほう）」というのは、「わり算」のことです。
　ですから、「互除法」というのは、お互いにわり算していく方法のことです。

　でも、お互いにわり算していって何が出てくるの？

　それは、２つの数の最大公約数（さいだいこうやくすう）です。

●　最大公約数　●

　約数（やくすう）というのは、もう知っていますね。
（　＜お勉強＞の「素数と素因数分解」をぜひ見てください。）

　１８÷２＝９　ですから　２は１８をわりきります。
　このとき、２　を　１８　の約数というのです。
　そして、１８＝２×９　となります。

　　　　■■■■■■■■■
　　　　■■■■■■■■■　　　　

　１８÷４＝４　あまり　２　ですから、４は１８をわりきりません。
　ですから、４は１８の約数ではありません。
　そして、１８＝４×４＋２　となります。

　　　　■■■■
　　　　■■■■
　　　　■■■■
　　　　■■■■　　■■

　では、公約数（こうやくすう）というのは何でしょう。

　たとえば、１２　と　１８　の公約数というのは、
１２の約数でもあるし、１８の約数でもあるものです。

《　１　》

　１２÷１＝１２　，　１８÷１＝１８　ですから、１　は　１２と１８の公約数です。

　たてが１２、横が１８の長方形は、一辺が１の正方形のタイルでしきつめられます。

　これは、あたりまえですね。

　　　　■■■■■■■■■■■■■■■■■■
　　　　■■■■■■■■■■■■■■■■■■
　　　　■■■■■■■■■■■■■■■■■■
　　　　■■■■■■■■■■■■■■■■■■
　　　　■■■■■■■■■■■■■■■■■■
　　　　■■■■■■■■■■■■■■■■■■
　　　　■■■■■■■■■■■■■■■■■■
　　　　■■■■■■■■■■■■■■■■■■
　　　　■■■■■■■■■■■■■■■■■■
　　　　■■■■■■■■■■■■■■■■■■
　　　　■■■■■■■■■■■■■■■■■■
　　　　■■■■■■■■■■■■■■■■■■

《　２　》

　１２÷２＝６　，　１８÷２＝９　ですから、２　は　１２と１８の公約数です。

　たてが１２、横が１８の長方形は、一辺が２の正方形のタイルでしきつめられます。

《　３　》

　１２÷３＝４　，　１８÷３＝６　ですから、３　は　１２と１８の公約数です。

　たてが１２、横が１８の長方形は、一辺が３の正方形のタイルでしきつめられます。

《　６　》

　１２÷６＝２　，　１８÷６＝３　ですから、６　は　１２と１８の公約数です。

　たてが１２、横が１８の長方形は、一辺が６の正方形のタイルでしきつめられます。

　このようにして、１，２，３，６　が　１２と１８の公約数であることがわかりました。

　じつは、素因数分解をつかうとすぐにわかります。

　　　　１２＝２×２×３
　　　　１８＝　　２×３×３

　じっと見比べて、１　の他は　２，３，２×３　ですね。

　そして、公約数の中で最大のものを最大公約数といいます。

　この最大公約数を、お互いにわり算していく方法で求めるのが
「ユークリッドの互除法」です。

　えっ、素因数分解でやればいいって？
　でも素因数分解がかんたんでないことは、暗号に利用されるくらいなのですよ。

●　ユークリッドの互除法　●

　引き続き、１２と１８で話をすすめましょう。

　問題は、たてが１２、横が１８の長方形を、
一辺が最大いくらの正方形のタイルでしきつめられるか、ということです。

　そのとき使うのが、わり算のたしかめ算（？）です。

　　　１８÷１２＝１　あまり　６
　　（１８個を１２人でわけると１人１個で６個あまる）

　これのたしかめは、

　　１８＝１×１２＋６　
　　（１人１個ずつ１２人にわけると、あまった６個もあわせれば、もとの１８個だ）

　このとき、１８と１２の最大公約数が、
１２と６の最大公約数と同じだというのがポイントです。

　なぜなら、
　　１８＝１×１２＋６　から、１２と６をわりきる数（約数）は１８もわりきるし、
　　　６＝１８－１×１２　から　１８と１２をわりきる数（約数）は６もわりきる
からです。

　わかりますよね。
　だって、何人かでちょうど分けられるおかしの皿が２皿あって、
あわせて１皿にしたら分けられなくなってしまう、なんてことないですよね。

　１２と１８の最大公約数を　（１２，１８）　と書くことにすると
　　　（１２，１８）＝（１２，６）
となります。

　図でいうと、
　　　たてが１２、横が１８の長方形をしきつめる問題が
　　　たてが１２、横が６の長方形をしきつめる問題になったのです。

　今度は
　　　１２÷６＝２　あまり　０
となり、（１２，６）＝（０，６）　となります。
　もちろん、０　と　６　の最大公約数は　６　です。

　けっきょく、（１２，１８）＝（１２，６）＝（０，６）＝６

となり、１２と１８の最大公約数は　６　とわかりました。

　（注意）ふつうは、（１２，１８）＝（１２，６）＝６　と書きます。

●　互いに素　●

　今度は　８　と　５　の最大公約数をみてみましょう。

　　　　■■■■■■■■
　　　　■■■■■■■■
　　　　■■■■■■■■
　　　　■■■■■■■■
　　　　■■■■■■■■

　　　８÷５＝１　あまり　３

　ですから、（８，５）＝（３，５）

　　　　■■■■■■■■
　　　　■■■■■■■■
　　　　■■■■■■■■
　　　　■■■■■■■■
　　　　■■■■■■■■

　　　５÷３＝１　あまり　２

　ですから、（３，５）＝（３，２）

　　　　■■■■■■■■
　　　　■■■■■■■■
　　　　■■■■■■■■
　　　　■■■■■■■■
　　　　■■■■■■■■

　　　３÷２＝１　あまり　１

　ですから、（３，２）＝（１，２）

　　　　■■■■■■■■
　　　　■■■■■■■■
　　　　■■■■■■■■
　　　　■■■■■■■■
　　　　■■■■■■■■

　　　２÷１＝２　あまり　０

　ですから、（１，２）＝（１，０）

　　　　■■■■■■■■
　　　　■■■■■■■■
　　　　■■■■■■■■
　　　　■■■■■■■■
　　　　■■■■■■■■

　けっきょく、（８，５）＝（３，５）＝（３，２）＝（１，２）＝（１，０）＝１

となり、８と５の最大公約数は　１　とわかりました。

　（注意）ふつうは、（８，５）＝（３，５）＝（３，２）＝（１，２）＝１　と書きます。

　　　　■■■■■■■■
　　　　■■■■■■■■
　　　　■■■■■■■■
　　　　■■■■■■■■
　　　　■■■■■■■■

　８　と　５　のように、その最大公約数が１であるとき、
つまり素因数分解すると

　　　８＝２×２×２
　　　５＝５

のように、まったく共通の素因数をもたないとき、
８　と　５　は互いに素（たがいにそ）といいます。

●　１次不定方程式　●

　さて、ユークリッドの互除法をもちいて、

　　１２Ｘ　＋　１８Ｙ　＝　６　　や

　　　８Ｘ　＋　５Ｙ　＝　１

の　Ｘ　や　Ｙ　にあてはまる数の（無限にたくさんあるうちの）ひとつを求めてみましょう。

《　１２Ｘ　＋　１８Ｙ　＝　６　》

　さいしょに、両辺を最大公約数の６でわってしまって、

　　２Ｘ　＋　３Ｙ　＝　１　

にするのがふつうでしょうが、（そうすれば、２と３は互いに素です）
今回はせっかくですからそのままやりましょう。

　　　１８÷１２＝１　あまり　６　，　これから　１８＝１×１２＋６
　　　　　　　　　　　　　　　　　　　　つまり　　－１×１２＋１８＝６
　　　　　　　　　　　　　　　　　　　　　　　（－１）×１２＋１×１８＝６

　Ｘ＝－１，Ｙ＝１　とすればいいですね。

　えっ、あたりまえすぎて気にいらないって？
　そういう人は

　　　１２＝６×２　　　　　　だから　１２×３＝６×２×３
　　　１８＝６×　　３　　　　だから　１８×２＝６×２×３

であることを頭において

　Ｘ＝－１＋３　，Ｙ＝１－２　とすれば、
　　＝２　　　　　　　＝－１

　　　（－１＋３）×１２　＋　（１－２）×１８
　　＝（－１）×１２　＋　３×１２　＋　１×１８　－２×１８
　　＝（－１）×１２　＋　１×１８
　　＝　６

　ほかにどんな数がＸとＹにあてはまるか、やってみてね。

《　８Ｘ　＋　５Ｙ　＝　１　》

　　　８÷５＝１　あまり　３　，　これから　８＝１×５＋３　　・・・　（１）

　　　５÷３＝１　あまり　２　，　これから　５＝１×３＋２　　・・・　（２）

　　　３÷２＝１　あまり　１　，　これから　３＝１×２＋１　　・・・　（３）

　まず、（３）から　　３　－　１×２　＝　１　　・・・　（４）

　次に、（２）から　　５　－　１×３　＝　２　・・・　（５）

　（５）を（４）に代入すると

　　　　　　　　３　－　１×（５－１×３）　＝　１
　　　　　　　　２×３　－１×５　＝　１　・・・　（６）

　次に、（１）から　　８　－　１×５　＝　３　・・・　（７）

　（７）を（６）に代入すると

　　　　　　　　２×（８－１×５）　－　１×５　＝　１
　　　　　　　　２×８　＋（－３）×５　＝　１

　Ｘ＝２　，　Ｙ＝－３　があてはまる数のひとつです。

　ほかにどんな数がＸとＹにあてはまるか、やってみてね。

HOME（もどる）