thetheorier https://blog.hatena.ne.jp/thetheorier/ もう一人のY君 https://blog.thetheorier.com/ 数学 こんにちは, @the_theorierです. 昨日, 今朝とユークリッドの互除法について紹介しましたが, 書き終わってふと思い立ったのでちょっと調べてみました. 式変形は何回で終わるのか 正の整数 a, b (a>b, b>0) を任意に取ってきて, それを a = bq + r と分解する操作を繰り返すことで a, b の最大公約数を得るのがユークリッドの互除法ですが, この式変形は a, b の値によって何回で済むでしょう？ 昨日書いた互除法の説明では「高々 b 番目」と書きましたが, 実際にはそれよりももっと少なく, 多くても [b/2] 回を下回ると思われます([・]はガウス記号).… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.thetheorier.com%2Fentry%2F2015%2F05%2F17%2F134217" 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/9/8882/17569769788_8b5e251f67_z.jpg Hatena Blog https://hatena.blog 2015-05-17 13:42:17 rich https://blog.thetheorier.com/entry/2015/05/17/134217 1.0 100%