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

Proof

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

Copyright © 1996-2018 Alexander Bogomolny

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

Proof 1

First we establish

Lemma

10n ≡ 2n (mod 2n+1).

Proof of Lemma

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

A ≡ 1 (mod 2).

More explicitly, A = 2k + 1, implying 2nA = 2n+1k + 2n, or, in case A = 5n,

10n ≡ 2n (mod 2n+1).

Proof of the statement

The proof is going to be by induction on n, the length of the integers at hand. Let Bn 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 2k: p∈Bk} = Z2k, where Z2k = {0, 1, 2, ..., 2k - 1} is the set of the residues modulo 2k. We need to prove that

{p modulo 2k+1: p∈Bk+1} = Z2k+1.

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

q = s2k + r, 0 ≤ r < 2k.

Number s can be either even or odd such that,

q = t2k+1 + r, if s = 2t, or
q = t2k+1 + (r + 2k), if s = 2t + 1,

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

If p = 10k + q, the lemma gives

p ≡ r + 2k (mod 2k+1), if s is even, and
p ≡ r + 2·2k ≡ r (mod 2k+1), if s is odd.

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

p ≡ r (mod 2k+1), if s is even, and
p ≡ r + 2k (mod 2k+1), if s is odd.

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

p1 ≡ r (mod 2k+1), and
p2 ≡ r + 2k (mod 2k+1).

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

0 ≤ r, r + 2k < 2k + 2k = 2k+1.

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

Proof 2

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

First observe that, if A ≡ B (mod 2n), then certainly A ≡ B (mod 2). If A = ∑i=0ai10i, B = ∑i=0bi10i and A ≡ B (mod 2n), then a0 ≡ b0 (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 2n). Then a0 ≡ b0 (mod 2) while both a0 and b0 are either 1 or 2 and, therefore, are equal:

a0 = b0.

Let A1 be obtained by dropping a0 and dividing by 10, and define B1 similarly. Then

A1 ≡ B1 (mod 2n-1),

and from here we may derive - as above - that a1 = b1.

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

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

Copyright © 1996-2018 Alexander Bogomolny

71492476