ユークリッドの互除法

質問

早急に解答求めています、
ご協力よろしくお願いします(>_<)

1.自分では簡単に素因数分解できない2つの整数(どちらとも9桁以上の整数)を決めてその最大公約数をeuclidの互除法で求め よ。

2.1で求めた数が最大公約数であることを示せ。

できれば途中式も省かないで書いていただきたいです。
よろしくお願い申し上げます。

回答No.8

alice_44

最大公約数が１になる例を挙げてしまうと、
前に書いた「2つの整数を最大公約数で割った
商に互除法を使って、素であることを示す」
方法すら使えなくなる。
検算が、一回目の互除法と全く同じ計算に
なってしまうから。

最初の「２つの整数」が互に素ではない例を
挙げておいて、互除法を二回やって見せるのが
無難なような気はする。
(それが、本当に検算をしたことになるのか
どうかは、前述のように、微妙なのだが…)

回答No.7

adachirusan

1.
被序数 5704927793
序数 716823829
（適当に作った数）

ひたすら序数をあまりで割っていきます。
5704927793 = 716823829 × 7 + 687160990
716823829 = 687160990 × 1 + 29662839
687160990 = 29662839 × 23 + 4915693
29662839 = 4915693 × 6 + 168681
4915693 = 168681 × 29 + 23944
168681 = 23944 × 7 + 1073
23944 = 1073 × 22 + 338
1073 = 338 × 3 + 59
338 = 59 × 5 + 43
59 = 43 × 1 + 16
43 = 16 × 2 + 11
16 = 11 × 1 + 5
11 = 5 × 2 + 1
5 = 1 × 5 （割り切れる）

5704927793 と 716823829 は互いに素である。
よって最大公約数は1

2.
（自信ありませんがやるだけやってみました）

1.で求めた数の約数は 1

また、1 は 5704927793 と 716823829 の公約数

公約数と、最大公約数の約数全体は一致するので、1 は最大公約数

（←誰かがもっとちゃんとしたのを書いてくれると思っている）

回答No.6

alice_44

それは、互除法を知ってる人なら、必ず理解していることだが、
課題が要求しているのは、そういうことなんだろうか？

普通に読むと、互除法の原理を説明せよということじゃなく、
一例実行してみて、結果を検証せよ と言ってるように思える。

その検証の方法として、何が使えるかが問題だなあと感じている訳。

回答No.5

sunflower-san

>alice_44さん。
回答No.3の者です。

No.3に書いた回答で、ユークリッドの互除法で求まった最後の余りが最大公約数になっているということの証明になっていると思うのですが、いかがでしょうか。

要は、N[0]をN[1]で割り算をした余りをN[2]とするとき、
N[0]とN[1]の最大公約数が、N[1]とN[2]の最大公約数に等しい、ということと、
次々にN[k]をN[k+1]で割り算をして余りN[k+2]を求めるプロセスが必ず有限回で終了する(有限回目で割り切れる)、という二点が肝心です。

これを示せば、
ある自然数mについて、N[m-1]がN[m]で割り切れるので、N[m+1]=0 すなわち、
gcd(N[0], N[1])=gcd(N[1], N[2])=・・=gcd(N[m], 0)=N[m]
となって、gcd(N[0], N[1])が求まるということです。

回答No.4

alice_44

2.
これは、難しいね。何をすりゃいいんだろう？

回答No.3

sunflower-san

1. 2つの自然数N[0],N[1](N[0]>N[1])を与えられた、として、ユークリッド互除法によって最大公約数が計算出来る仕組みを説明します。「9桁以上の」という条件は、単に「ユークリッドの互除法が非常に大きな整数に対しても効率よく最大公約数を求められる方法だから、実践してみなさい」という意味です。

まず、N[0]をN[1]で割り、商と余りを求める。商をQ[1], 余りをN[2]とおくと、

N[0]=Q[1]・N[1]＋N[2]
となっている。

ここで、次の点(a), (a'), (b)に注目する：

(a) N[0]とN[1]を割り切る数は、N[2]=N[0]-Q[1]・N[1]も割り切り、
(a') N[1]とN[2]を割り切る数は、N[0]=Q[1]・N[1]＋N[2]も割り切る。

(b) N[1]>N[2]である。

いま、
N[0]とN[1]の最大公約数をD[0](←求めたい数)、
N[1]とN[2]の最大公約数をD[1]
とおくと、

性質(a)より、D[0]はN[1]とN[2]の公約数でもある。よって、D[1]はD[0]の倍数。
また、性質(a')より、D[1]はN[0]とN[1]の公約数でもある。よって、D[0]はD[1]の倍数。

したがって、D[1]=D[0]である。

こうして、
2つの数 N[0]>N[1]の最大公約数D[0]を求める問題が
より小さな2つの数 N[1]>N[2]の最大公約数D[1]を求める問題に帰着されたことが分かる。

いま、もしN[2]=0なら、D[1]=N[1]であり、(D[0]=D[1]だったので)D[0]を求める計算は完了する(D[0]=N[1])。

もし、N[2]>0なら引き続き割り算を行い、
N[1]をN[2]で割った余りをN[3]とおく。

N[2]とN[3]の最大公約数をD[2]とおくと、D[2]=D[1]=D[0]である。

いま、もしN[3]=0なら、D[2]=N[2]であり、(D[0]=D[2]だったので)D[0]を求める計算は完了する(D[0]=N[2])。

以下、N[k]をN[k+1]で割って余りを計算する操作を余りN[k+2]が0になるまで帰納的に繰り返す。もしm回目の割り算で、N[m-1]がN[m]で割り切れた(余りN[m+1]=0)とすると、N[m-1]とN[m]の最大公約数D[m]=N[m]であり、
D[m]=D[m-1]=・・=D[0]だから、D[0]を求める計算は完了する(D[0]=N[m])。

気をつけないといけないのは、この割り算がちゃんと有限回で終了する(割り切れる)か？という点だが、

それは、
N[k]>0である限り、割り算N[k-1]÷N[k]が出来ること、および性質(b)のため
N[1]>N[2]>N[3]>・・≧0
つまり、N[1], N[2], N[3],...が単調な減少列であること、から明らかである。

こうして、有限回の割り算(余りを求める計算)でN[0]とN[1]の最大公約数D[0]を計算することが出来る。

回答No.2

alice_44

1.
何かテキトーな方法で、２つの整数を決める。２０面ダイスを持っていると便利かもしれないし、
厚めの本を開いて、ページ数を桁に並べてもよいかもしれない。統計学の本の巻末には
乱数表がついていることもある。円周率の高精度表などを持っていると、乱数表の代わりになる。
選び出した数は、比較的小さい素数で割ってみて、割りきれたら１足すとか、調整は必要かも。

２つの整数を決めたら、言われたとおりにEuclidの互除法で、最大公約数を求める。
Euclidの互除法を知らない？ そりゃ、論外。教科書か講義ノートを再読しよう。

2.
これは、難しいね。何をすりゃいいんだろう？
求めた数で最初の２つの整数を割ってみれば、公約数であることは確認できるが…
最大公約数であることを示すには、その２つの商が互いに素であることを言わなきゃならない。
Euclidの互除法で最大公約数が１であることを示す？ それで検算したことになるかどうか。
他に方法は…　はて？

回答No.1

Tacosan

で質問は何?