# Integers With Digits 1 and 2 and Residues Modulo Powers of 2

The following curious fact was communicated to me by BùI Quang Tuãn.

There are 2^{n} integers whose only digits are 1 and 2. All such numbers have different residues modulo 2^{n}.

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

Copyright © 1996-2017 Alexander Bogomolny

There are 2^{n} integers whose only digits are 1 and 2. All such numbers have different residues modulo 2^{n}.

### Proof 1

First we establish

### Lemma

10^{n} ≡ 2^{n} (mod 2^{n+1}).

### Proof of Lemma

Observe that, for any odd number A, 5^{n} in particular,

A ≡ 1 (mod 2).

More explicitly, A = 2k + 1, implying 2^{n}A = 2^{n+1}k + 2^{n}, or, in case A = 5^{n},

10^{n} ≡ 2^{n} (mod 2^{n+1}).

### Proof of the statement

The proof is going to be by induction on n, the length of the integers at hand. Let B^{n} denote the set of all n-digit integers with digits 1 and 2 only. For

11 ≡ 3 (mod 4),

12 ≡ 0 (mod 4),

21 ≡ 1 (mod 4),

22 ≡ 2 (mod 4).

Now assume that the statement holds for n = k: {p modulo 2^{k}: p∈B^{k}} = **Z**_{2k}, where **Z**_{2k} = {0, 1, 2, ..., 2^{k} - 1}^{k}. We need to prove that

{p modulo 2^{k+1}: p∈B^{k+1}} = **Z**_{2k+1}.

For any p∈B^{k+1}, p = δ10^{k} + q, where δ is either 1 or 2, and q∈B^{k}. By the induction hypothesis, q has a unique (in B^{k}) residue r modulo 2^{k}:

q = s2^{k} + r, 0 ≤ r < 2^{k}.

Number s can be either even or odd such that,

q = t2^{k+1} + r, if s = 2t, or

q = t2^{k+1} + (r + 2^{k}), if s = 2t + 1,

meaning that, for s even, q ≡ r (mod 2^{k+1}), whereas, for s odd, q ≡ r + 2^{k} (mod 2^{k+1}).

If p = 10^{k} + q, the lemma gives

p ≡ r + 2^{k} (mod 2^{k+1}), if s is even, and

p ≡ r + 2·2^{k} ≡ r (mod 2^{k+1}), if s is odd.

For, p = 2·10^{k} + q, the impressions are reversed:

p ≡ r (mod 2^{k+1}), if s is even, and

p ≡ r + 2^{k} (mod 2^{k+1}), if s is odd.

So, let p ≡ r (mod 2^{k}). When we prepend one of the digits 1 or 2 to p∈B^{k} we obtain two numbers 1p and 2p from B^{k+1}. Suitably denoting one of them p_{1} and the other p_{2} (I do not know which is which) we get

p_{1} ≡ r (mod 2^{k+1}), and

p_{2} ≡ r + 2^{k} (mod 2^{k+1}).

Since 0 ≤ r < 2^{k} is unique, so are the two residues

0 ≤ r, r + 2^{k} < 2^{k} + 2^{k} = 2^{k+1}.

(Patrick Honner has observed that the statement of Lemma can be strengthened: 10^{n} ≡ 2^{n} (mod 2^{n+2}). This is because we can start with ^{k} ≡ 1 (mod 4)^{k} ≡ 1 (mod 2).

### Proof 2

BùI Quang Tuãn supplied a direct proof.

First observe that, if A ≡ B (mod 2^{n}), then certainly A ≡ B (mod 2). If _{i=0}a_{i}10^{i}_{i=0}b_{i}10^{i}^{n}),_{0} ≡ b_{0} (mod 2).

Now, let A and B be written with digits 1 and 2 and A ≡ B (mod 2^{n}). Then _{0} ≡ b_{0} (mod 2)_{0} and b_{0} are either 1 or 2 and, therefore, are equal:

a_{0} = b_{0}.

Let A_{1} be obtained by dropping a_{0} and dividing by 10, and define B_{1} similarly. Then

A_{1} ≡ B_{1} (mod 2^{n-1}),

and from here we may derive - as above - that a_{1} = b_{1}.

At this point we may simply suggest that the process may continue and, as the result, all corresponding decimal coefficients of A and B coincide, implying that

(This proof makes it obvious that the digits 1 and 2 can be replaced by any other pair of digits of different parities. Also, a little different approach is taken elsewhere.)

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

Copyright © 1996-2017 Alexander Bogomolny

62016739 |