thetheorier https://blog.hatena.ne.jp/thetheorier/ もう一人のY君 https://blog.thetheorier.com/ 数学 こんにちは, @the_theorierです. 今回はユークリッドの互除法の焼き直しです. 準備 アルゴリズムを紹介するためにその仕組み自体を証明することから始めます. 一般的には, 整数a, b, cによる次のような2変数1次不定方程式を指します. ax+by = c … (※) 但し基本的には a, bは正整数としても「一般性を失いません」. 例えば a<0, b>0 であるとすると, 仮に(※)が解を持つならば ax + by = c ⇔ a'x' + by = c (但し a' := -a) として一旦 a'x' + by = c を解き, その解 を使って とすれば良いからです, b… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.thetheorier.com%2Fentry%2F2015%2F05%2F16%2F180748" title="ユークリッドの互除法 - もう一人のY君" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://c1.staticflickr.com/3/2888/9586369901_eae1453458_o.png Hatena Blog https://hatena.blog 2015-05-16 18:07:48 rich https://blog.thetheorier.com/entry/2015/05/16/180748 1.0 100%