Divisibility by Powers of 2

For every integer n > 0 there exists an n-digit integer, with digits 1 and 2, divisible by 2ⁿ.

Proof

The proof is by induction on n. To start off, 2 is divisible by 2¹. Here's a few simple cases: 2²|12, 2³|112, 2⁴|2112.

So, assume that A is a k-digit integer, with digits 1 and 2 and divisible by 2^k. There are just two possibilities: either

1. A divisible by 2^k+1 or
2. A is not divisible by 2^k+1.

Note that the (k+1)-digit number 10^k could be factored as 10^k = 2^k5^k, and is therefore divisible by 2^k but not by 2^k+1. Moreover, 10^k / 2^k+1 = 5^k / 2, meaning that the result is a decimal, say, B.5 = B½, which implies that 2·10^k is divisible by 2^k+1.

Now, in case where A is divisible by 2^k+1, the (k+1)-digit integer (2·10^k + A) is also divisible by 2^k+1.

In case where A is not divisible by 2^k+1, the ratio is again in the form C½, so that (10^k + A) is divisible by 2^k+1.

This completes the proof.