Question

やさいのようせい

ユークリッド互除法の証明の意味がよく分からないのですが、

gcd(a,b)=Gとして
a=a'G、b=b'G(a'とb'は互いに素)と表し、

a=bQ+rのとき
r=a'G-b'GQより
r=G(a'-b'Q)から、rはGを約数にとる。
また、(a'-b'Q)とb'は互いに素であるから、
rとbはGを最大公約数にとる。

と自分なりに解釈したんですが、この解釈でも正しいんでしょうか？
回答よろしくお願いします！

Answer 1

✨ Best Answer ✨

gößt

「a'-b'Qとb'が互いに素」という所がきちんと証明できるかという問題はありますが、そのような解釈でもよいと思います

やさいのようせい

ありがとうございます！

gößt

いえいえ