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.
|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
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
{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
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
Now, let A and B be written with digits 1 and 2 and A ≡ B (mod 2n). Then
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
(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
72522386