# Divisibility by Powers of 2

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

|Contact| |Front page| |Contents| |Algebra| |Induction|

Copyright © 1996-2018 Alexander Bogomolny

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

### Proof

The proof is by induction on n. To start off, 2 is divisible by 2^{1}. Here's a few simple cases: 2^{2}|12, 2^{3}|112, 2^{4}|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 ^{k} = 2^{k}5^{k},^{k} but not by 2^{k+1}. Moreover, ^{k} / 2^{k+1} = 5^{k} / 2,^{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^{n} × (2 - [A(n)/2^{n} mod 2]),

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

|Contact| |Front page| |Contents| |Algebra| |Induction|

Copyright © 1996-2018 Alexander Bogomolny

70173651