Competition problem — Number theory

Library / /131 of 520

Number theory Difficulty 5.7 AIME, harder Prove it

Lemma 5.1. If $d$ and $n$ are positive integers such that $d$ divides $n$ , then $2^{d}-1$ divides $2^{n}-1$

Solution

Proof. Since $d \mid n$ , there is a positive integer $t$ with $d t=n$ . By setting $x=2^{d}$ in the identity $x^{t}-1=(x-1)\left(x^{t-1}+x^{t-2}+\cdots+1\right)$ , we find that $2^{n}-1=\left(2^{d}-1\right)\left(2^{d(t-1)}+2^{d(t-2)}+\cdots+2^{d}+1\right)$ . Consequently, $\left(2^{d}-1\right) \mid\left(2^{n}-1\right)$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.