Track / Stage 4 / 287 of 340 #1027 of 2444

Problem 1027

AMC 12 late, AIME early

Number theory Difficulty 4.9 Prove it South-Afrika · South Africa · 2011

Does there exist a natural number $N$ which is a power of $2$ such that the digits of $N$ can be permuted to form a power of $2$ different from $N$ ?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Suppose that the digits of $2^a$ can be rearranged to form $2^b$ , with $a > b$ . Then, since the two numbers have the same digit set, it follows that they're congruent modulo $9$ . Hence $9 \mid 2^a - 2^b = 2^b(2^{a-b} - 1)$ and so $2^{a-b} \equiv_9 1$ . However, the smallest positive power of $2$ with this property is $2^6$ , so $a-b \ge 6$ . But in that case, $2^a \ge 2^{b+6} = 64 \cdot 2^b > 10 \cdot 2^b$ , which means that $2^a$ and $2^b$ can't have the same number of digits, a contradiction. So no such pair exists.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.