Classic olympiad problem · Number Theory
Prove that gcd(2^m - 1, 2^n - 1) = 2^gcd(m,n) - 1.
Prove that .
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.
Guides that use this problem
- Lifting the exponent lemma explained for competitionsThe lifting the exponent lemma in one line, the p = 2 version that catches almost everyone, and the signals that tell you a contest problem wants it.
- gcd(2^m − 1, 2^n − 1): the proof, and how to spot itWhy gcd(2^m − 1, 2^n − 1) = 2^gcd(m,n) − 1: run Euclid's algorithm on the exponents. A full proof, a second proof by orders, and where it turns up.
Train it on Lemma
This problem sits in the Olympiad Set: 89 proof problems (real IMO problems and the classics) with progressive hints, full walkthroughs and marking rubrics. 125 lessons, 1206 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and every paid plan opens with 3 free days.
Find your levelMore Number Theory problems
- IMO 1959, Problem 1IMO 1959, Problem 1 · difficulty 3/6
- IMO 1988, Problem 6IMO 1988, Problem 6 · difficulty 6/6
- EuclidClassic (Euclid) · difficulty 2/6
- All 89 problems →