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ⁿ integers whose only digits are 1 and 2. All such numbers have different residues modulo 2ⁿ.

Proof

There are 2ⁿ integers whose only digits are 1 and 2. All such numbers have different residues modulo 2ⁿ.

Proof 1

First we establish

Lemma

10ⁿ ≡ 2ⁿ (mod 2ⁿ⁺¹).

Proof of Lemma

Observe that, for any odd number A, 5ⁿ in particular,

A ≡ 1 (mod 2).

More explicitly, A = 2k + 1, implying 2ⁿA = 2ⁿ⁺¹k + 2ⁿ, or, in case A = 5ⁿ,

10ⁿ ≡ 2ⁿ (mod 2ⁿ⁺¹).

Proof of the statement

The proof is going to be by induction on n, the length of the integers at hand. Let Bⁿ denote the set of all n-digit integers with digits 1 and 2 only. For n = 1, there are two such integers - 1 and 2 - and their residues modulo 2 are 1 and 0, respectively. We do not need to check that for other values of n, but for the sake of fun,

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_2^k, where Z_2^k = {0, 1, 2, ..., 2^k - 1} is the set of the residues modulo 2^k. We need to prove that

{p modulo 2^k+1: p∈B^k+1} = Z_2^k+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₁ and the other p₂ (I do not know which is which) we get

p₁ ≡ r (mod 2^k+1), and
p₂ ≡ 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ⁿ ≡ 2ⁿ (mod 2ⁿ⁺²). This is because we can start with 5^k ≡ 1 (mod 4) instead of 5^k ≡ 1 (mod 2).)

Proof 2

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

First observe that, if A ≡ B (mod 2ⁿ), then certainly A ≡ B (mod 2). If A = ∑_i=0a_i10ⁱ, B = ∑_i=0b_i10ⁱ and A ≡ B (mod 2ⁿ), then a₀ ≡ b₀ (mod 2). This is because all nonzero powers of 10 are divisible by 2.

Now, let A and B be written with digits 1 and 2 and A ≡ B (mod 2ⁿ). Then a₀ ≡ b₀ (mod 2) while both a₀ and b₀ are either 1 or 2 and, therefore, are equal:

a₀ = b₀.

Let A₁ be obtained by dropping a₀ and dividing by 10, and define B₁ similarly. Then

A₁ ≡ B₁ (mod 2^n-1),

and from here we may derive - as above - that a₁ = b₁.

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 A = B. What we've done so far can also be considered as the inductive step, a portion of which makes the basis for a proof by induction.

(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.)

71052245