Divisibility by Powers of 2

For every integer n > 0 there exists an n-digit integer, with digits 1 and 2, divisible by 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

A divisible by 2^k+1 or
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.

If we denote A(n) the n-digit number obtained in the manner implied by the proof, there is a simple formula:

A(n+1) = A(n) + 10ⁿ × (2 - [A(n)/2ⁿ mod 2]),

which means exactly as described: A(n+1) ends with A(n); and, if A(n) is divisible by 2ⁿ⁺¹ then A(n+1) term begins with a 2, if not then A(n+1) begins with a 1.

(Curiously, n-digit numbers written with digits 1 and 2 all have different residues modulo 2ⁿ.)

72347949