こんにちは, @the_theorierです. 昨日, 今朝とユークリッドの互除法について紹介しましたが, 書き終わってふと思い立ったのでちょっと調べてみました. 式変形は何回で終わるのか 正の整数 a, b (a>b, b>0) を任意に取ってきて, それを a = bq + r と分解する…

こんにちは, @the_theorierです. 時間が出来たので拡張ユークリッドも書いていこうと思います. 昨日の通りで, 2つの正整数 a, b を使って a = bq + r と分解する行為を繰り返すことで, a, b の最大公約数を得るのがユークリッドの互除法でした. ユークリッド…