Lemma › Problems › Prove that gcd(2^m - 1,; 2^n - 1) = 2^gcd(m,n) - 1.
Classic olympiad problem · Number Theory

Prove that gcd(2^m - 1,; 2^n - 1) = 2^gcd(m,n) - 1.

Prove that gcd⁡(2m−1,;2n−1)=2gcd⁡(m,n)−1\gcd(2^m - 1,; 2^n - 1) = 2^{\gcd(m,n)} - 1.
Topic: Number Theory Difficulty: 5/6 Expected time: ~40 min Progressive hints on Lemma: 3

This is a proof problem — the answer is an argument, not a number. The solution is deliberately not posted here: reading a solution you didn't fight for teaches almost nothing. On Lemma you attempt it cold, take one of the 3 progressive hints only when genuinely stuck, then compare your proof against a full walkthrough and mark yourself with the same rubric a competition coordinator would use.

Train it on Lemma

This problem sits in the Olympiad Set — 81 real competition problems with progressive hints, full walkthroughs and marking rubrics. 78 lessons, 624 curated problems and unlimited generated practice at six difficulties. Free to start — no card, no trial clock.

Find your level

More Number Theory problems