# Divisibility by Powers of 2

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

Proof

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

### Proof

The proof is by induction on n. To start off, 2 is divisible by 21. Here's a few simple cases: 22|12, 23|112, 24|2112.

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

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

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

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

In case where A is not divisible by 2k+1, the ratio is again in the form C½, so that (10k + A) is divisible by 2k+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) + 10n × (2 - [A(n)/2n mod 2]),

which means exactly as described: A(n+1) ends with A(n); and, if A(n) is divisible by 2n+1 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 2n.)