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

数学です13x+8y=7この方程式の整数解をすべて求めよユークリ...

ユークリッド の 互 除法 やり方

おもしろ数学講座 かんたんユークリッドの互除法 さて、ユークリッドとは実在する人物の名前ですが、ユークリッドの生涯については、詳しいことはほとんど分かっていません。 紀元前330年に生まれて紀元前275年に死んだという説や、紀元前365年に生まれたという説などまちまちです。 いずれにしても紀元前約300年頃の人であろうということくらいは分かっています。 彼は当時のエジプトの王であったプトレマイオスの招きに応じてアレクサンドリアに行き、そこで教授、著作、研究に専念したそうです。 彼はそこで当時までに知られていたあらゆる数学のデータ収集をし、再検討を加えて整理しました。 これが現在の数学でも絶大なる力を持っている『原論』という大著となりました。 当時も数学の教科書として使用されていたようで、これに纏わる有名なエピソードがあります。 『原論』を教科書としてユークリッドから幾何学を学んでいたプトレマイオス王が、『幾何学をもっと簡単に学ぶ近道はないのか?』と質問したのに対して、『幾何学に王道なし』と答えたというのです。 この『原論』は、聖書に次ぐ大著として、1482年以来1000種類以上の言語に翻訳されたものが出版されたといわれています。 内容は、おおまかにいうと第1章〜第6章は「平面幾何」、第7章〜第9章は「数論」、第10章は「無理数」、第11、第12章は「立体幾何」、第13〜第15章は「正多面体」についてまとめています。 以前には何とも思わなかったような物が、興味深い物として目に映ることをご期待して、この不思議な数の世界へご招待致したいと思います。 【 公約数について】 例えば、30と45の約数は、 30の約数・・・ 1、2、 3、 5、6、10、 15、30 45の約数・・・ 1、 3、 5、9、 15、45 ですから、2つの約数のうち共通の「 1、 3、 5、 15」の4つの数字が30と45の公約数となります。 また、公約数のうち最大の約数を最大公約数 G. ともいう。 Greatest Common Measureの略)といい、この場合 15となります。 ここで、最大公約数を求めるときに、いまのように1つ1つ約数を取り上げて比べていくのではなく、もっと簡単に求める方法があります。 その方法がユークリッドの互除法なのです。 【 ユークリッドの互除法について】 これは前述の「原論」の第7章にやや異なった形で述べられていますが、それはユークリッドよりも100年ほど前にすでに発見されていたと伝えられています。 それでは、60と168の最大公約数をこの方法で求めてみましょう。 ユークリッドの互除法を使うと、いつか必ず割り切れて、そのときの割った数が最大公約数となります。 (ユークリッドの互除法はN桁の数に対して5N回以内で終了することがわかっています。 ) でも、なぜこんなにも簡単に最大公約数が求まるのか不思議ですね?それでは、互除法の原理を証明してみましょう。 高校の参考書などに載っている互除法の原理はだいたい以下のように解説されています。 (注;互いに素とはa'とb'の公約数が1以外にはないということ。 以上のことをもう少し簡単に表現すると、aをbで割ったときの余りrは、aとbの最大公約数を因数にもつ。 言いかえると 『aとbの最大公約数はbとrの最大公約数と考えてよい。 』ことがわかります。 この証明は、いわゆる「必要十分条件」という考え方から導かれる証明法で、なかなか生徒に説明して理解させるのに苦労します。 (生徒はこのような論述形式の証明をいたって嫌う傾向にあります。 )しかも、aやらbやらたくさんの文字を使用するので、読むのさえ苦労することでしょう。 さて、これで終わってしまっては、今回のテーマである「 かんたんユークリッドの互除法」とは言い難いですよね?!実は図形を利用することで、ユークリッドの互除法を小学生にも理解できるように説明できる素晴らしい方法があるのです。 【 かんたんユークリッドの互除法】 【四角形と公約数の関係】 さて、もう一度先ほどの 60と168の最大公約数を求める問題を考えてみましょう。 右の図をご覧下さい。 縦が60、横が168の横長の長方形から、短い方の辺である、60を1辺とする正方形をできるだけ多く切り取っていきます。 (図では2個の正方形が切り取れることになる。 ) すると最後に縦が60、横が48の長方形が残ることになります。 その結果、商が2、余りが48というわけですから、縦が60、横が168の横長の長方形から1辺が60の正方形が2個とれて、最後に縦が60、横が48の長方形が残るというわけです。 右の図をご用意致しました。 考え方は先ほどと同じですので、じっくりご覧いただければすぐに理解できることと思います。 以上のことをまとめてみましょう。 長方形から短い方の辺を1辺とする正方形を切り取る操作を全部で3回行った結果、1辺が12の正方形で終了ということになったわけです。 すなわち縦が60、横が168の長方形を 1辺が12の正方形で敷き詰めることができることと、 12が60と168の最大公約数となることが同じであるということが理解できたと思います。 それでは3007と1649の最大公約数をユークリッドの互除法を使って求めてみましょう。 !!とてもじゃないけれど最初にしたように2つの数のそれぞれの約数を並べて比較するなんて大変ですよね?ユークリッドの互除法(先人の知恵)のありがたさをつくづく感じてしまいます... (答えは97となります。 ) 【最後に】 ユークリッドの互除法は、最大公約数を求めるためだけのものではありません。 例えば次のような問題がユークリッドの互除法の考え方で解くことができます。 1円玉、10円玉、50円玉があわせて100枚あり、その総額は500円である。 このとき1円玉、10円玉、50円玉はそれぞれ何枚あるか。 (答えは1円玉 60枚、10円玉 39枚、50円玉 1枚となります。 ところがこれだけだと、生徒はだいたい次の2つの解答をします。 ということで、【解法1】よりは少なくて済みます。 以上のように、パソコンでもあればプログラムを組んで全部代入するということも可能でしょうが、そうでなければ面倒くさくてやる気がしませんよね?このような方程式を不定方程式といいますが、ユークリッドの互除法を使えば比較的簡単に解くことができます。 しかしながら今回は敢えて解説しないでおきます。 というのも「四角形と公約数の関係」という主題からはずれてしまうことと、自ら調べて発見する喜びというものもありますので、もし興味を持たれた方は図書館などへいって関連文献を調べて下さいね。

次の

ユークリッドの互除法

ユークリッド の 互 除法 やり方

おもしろ数学講座 かんたんユークリッドの互除法 さて、ユークリッドとは実在する人物の名前ですが、ユークリッドの生涯については、詳しいことはほとんど分かっていません。 紀元前330年に生まれて紀元前275年に死んだという説や、紀元前365年に生まれたという説などまちまちです。 いずれにしても紀元前約300年頃の人であろうということくらいは分かっています。 彼は当時のエジプトの王であったプトレマイオスの招きに応じてアレクサンドリアに行き、そこで教授、著作、研究に専念したそうです。 彼はそこで当時までに知られていたあらゆる数学のデータ収集をし、再検討を加えて整理しました。 これが現在の数学でも絶大なる力を持っている『原論』という大著となりました。 当時も数学の教科書として使用されていたようで、これに纏わる有名なエピソードがあります。 『原論』を教科書としてユークリッドから幾何学を学んでいたプトレマイオス王が、『幾何学をもっと簡単に学ぶ近道はないのか?』と質問したのに対して、『幾何学に王道なし』と答えたというのです。 この『原論』は、聖書に次ぐ大著として、1482年以来1000種類以上の言語に翻訳されたものが出版されたといわれています。 内容は、おおまかにいうと第1章〜第6章は「平面幾何」、第7章〜第9章は「数論」、第10章は「無理数」、第11、第12章は「立体幾何」、第13〜第15章は「正多面体」についてまとめています。 以前には何とも思わなかったような物が、興味深い物として目に映ることをご期待して、この不思議な数の世界へご招待致したいと思います。 【 公約数について】 例えば、30と45の約数は、 30の約数・・・ 1、2、 3、 5、6、10、 15、30 45の約数・・・ 1、 3、 5、9、 15、45 ですから、2つの約数のうち共通の「 1、 3、 5、 15」の4つの数字が30と45の公約数となります。 また、公約数のうち最大の約数を最大公約数 G. ともいう。 Greatest Common Measureの略)といい、この場合 15となります。 ここで、最大公約数を求めるときに、いまのように1つ1つ約数を取り上げて比べていくのではなく、もっと簡単に求める方法があります。 その方法がユークリッドの互除法なのです。 【 ユークリッドの互除法について】 これは前述の「原論」の第7章にやや異なった形で述べられていますが、それはユークリッドよりも100年ほど前にすでに発見されていたと伝えられています。 それでは、60と168の最大公約数をこの方法で求めてみましょう。 ユークリッドの互除法を使うと、いつか必ず割り切れて、そのときの割った数が最大公約数となります。 (ユークリッドの互除法はN桁の数に対して5N回以内で終了することがわかっています。 ) でも、なぜこんなにも簡単に最大公約数が求まるのか不思議ですね?それでは、互除法の原理を証明してみましょう。 高校の参考書などに載っている互除法の原理はだいたい以下のように解説されています。 (注;互いに素とはa'とb'の公約数が1以外にはないということ。 以上のことをもう少し簡単に表現すると、aをbで割ったときの余りrは、aとbの最大公約数を因数にもつ。 言いかえると 『aとbの最大公約数はbとrの最大公約数と考えてよい。 』ことがわかります。 この証明は、いわゆる「必要十分条件」という考え方から導かれる証明法で、なかなか生徒に説明して理解させるのに苦労します。 (生徒はこのような論述形式の証明をいたって嫌う傾向にあります。 )しかも、aやらbやらたくさんの文字を使用するので、読むのさえ苦労することでしょう。 さて、これで終わってしまっては、今回のテーマである「 かんたんユークリッドの互除法」とは言い難いですよね?!実は図形を利用することで、ユークリッドの互除法を小学生にも理解できるように説明できる素晴らしい方法があるのです。 【 かんたんユークリッドの互除法】 【四角形と公約数の関係】 さて、もう一度先ほどの 60と168の最大公約数を求める問題を考えてみましょう。 右の図をご覧下さい。 縦が60、横が168の横長の長方形から、短い方の辺である、60を1辺とする正方形をできるだけ多く切り取っていきます。 (図では2個の正方形が切り取れることになる。 ) すると最後に縦が60、横が48の長方形が残ることになります。 その結果、商が2、余りが48というわけですから、縦が60、横が168の横長の長方形から1辺が60の正方形が2個とれて、最後に縦が60、横が48の長方形が残るというわけです。 右の図をご用意致しました。 考え方は先ほどと同じですので、じっくりご覧いただければすぐに理解できることと思います。 以上のことをまとめてみましょう。 長方形から短い方の辺を1辺とする正方形を切り取る操作を全部で3回行った結果、1辺が12の正方形で終了ということになったわけです。 すなわち縦が60、横が168の長方形を 1辺が12の正方形で敷き詰めることができることと、 12が60と168の最大公約数となることが同じであるということが理解できたと思います。 それでは3007と1649の最大公約数をユークリッドの互除法を使って求めてみましょう。 !!とてもじゃないけれど最初にしたように2つの数のそれぞれの約数を並べて比較するなんて大変ですよね?ユークリッドの互除法(先人の知恵)のありがたさをつくづく感じてしまいます... (答えは97となります。 ) 【最後に】 ユークリッドの互除法は、最大公約数を求めるためだけのものではありません。 例えば次のような問題がユークリッドの互除法の考え方で解くことができます。 1円玉、10円玉、50円玉があわせて100枚あり、その総額は500円である。 このとき1円玉、10円玉、50円玉はそれぞれ何枚あるか。 (答えは1円玉 60枚、10円玉 39枚、50円玉 1枚となります。 ところがこれだけだと、生徒はだいたい次の2つの解答をします。 ということで、【解法1】よりは少なくて済みます。 以上のように、パソコンでもあればプログラムを組んで全部代入するということも可能でしょうが、そうでなければ面倒くさくてやる気がしませんよね?このような方程式を不定方程式といいますが、ユークリッドの互除法を使えば比較的簡単に解くことができます。 しかしながら今回は敢えて解説しないでおきます。 というのも「四角形と公約数の関係」という主題からはずれてしまうことと、自ら調べて発見する喜びというものもありますので、もし興味を持たれた方は図書館などへいって関連文献を調べて下さいね。

次の

不定方程式の解の求め方 ユークリッドの互除法を使った解き方はわかりにくい

ユークリッド の 互 除法 やり方

> > 最大公約数・最小公倍数・ユークリッドの互除法 最大公約数・最小公倍数・ユークリッドの互除法 関連性 RSA暗号化アルゴリズムの証明の際に、「拡張版ユークリッドの互除法」を使って秘密鍵を得るといいました。 このページで紹介するのは最終的には、最小公倍数の求め方です。 ですが、最小公倍数は最大公倍数から簡単に得ることができます。 そして、最大公約数はユークリッドの互除法によって簡単に得ることができます。 これはアルゴリズム入門講座の第1部でやった分割統治法に似ています。 最小公倍数を直接求めるのではなく、十分に解決が容易である問題に分けて、そこから復元していくという方法です。 そして、ユークリッドの互除法は最古のアルゴリズムとしても有名です。 ユークリッドの互除法 ユークリッドの互除法を簡単に言い表せば「余りで割る」ということです。 しかも繰り返し、「余りで割る」ことができなくなるまでです。 その時は、当然「余りが0」のときであり、「割り切れたとき」です。 具体的に数値でやってみます。 その場合は「偶数である」ことと「各位の和が3の倍数」であればいいのです。 15438 と 3510 はともに偶数である。 よって、2の倍数であり、3の倍数でもあるから、6の倍数である。 ユークリッドの互除法は極めて高速に最大公約数を求めることができます。 また、このアルゴリズムをソースコードとして実装することも非常に簡単です。 素因数分解で求めることもできますが、素因数分解は基本的に困難な問題です。 素因数分解が困難であることが、RSA暗号化の安全性の根拠になっているくらいです。 なお、p - 1 と q - 1 ではなく、間違えて p, q でやったら 1 が出力されます。 最大公約数が 1 というのは、互いに素であるということです。 その理由はあとで自然と分かるでしょう。 常に「m を n で割る」ことができるように、値を入れ替えています。 割り終わったら、m は不要ですが、n は次「割られる数」になりますから必要です。 まず、「割る数」である n を temp に一時保存します。 そして、「割った余り」を次の「割る数」である n にセットします。 最後に、一時保存しておいた前の「割る数」 n を次の「割られる数」である m にセットします。 ここでは、大きな数も想定して、long型を使っています。 ただし、p - 1, q - 1 などの処理はしていませんから、RSA暗号化でこれを使う場合は当然 p - 1 と q - 1 を渡す必要があります。 なお、p,q の大小関係は関係ありません。 小さな数を大きな数で割った場合、商が 0 で余りは小さな数ですから、自動的に逆転するようになっています。 ただし、おそらく1回だけ繰り返す回数は増えるでしょう。 最小公倍数 最小公倍数は最大公約数が分かっていれば極めて簡単に求めることができます。 今回は最小公倍数を求めたいので意味はありませんが。 こうすることで、実際にRSA暗号の秘密鍵を得るときには、あたかもGcd は関係ないかのように、Lcm にアクセスするだけで十分です。

次の