Let **N** be a **n-digit** number that contains only the digits **1** and **2**.

If **n = 2**, that is, a 2-digit number that contains __both__ the digits 1 and 2.

The set of these numbers is (12, 21)

Only **12** is divisible by **2^2**.

12 mod 2^2 = 0

21 mod 2^2 = 1

If **n = 3**. The set is (112, 121, 211, 221, 212, 122)

**112** = 2 * 2 * 2 * 2 * 7

**121** = 11 * 11

**211** is a prime number.

**221** = 13 * 17

**212** = 2 * 2 * 53

**122** = 2 * 61

Only **112** is divisible by **2^3**

122 mod 2^3 = 2

121 mod 2^3 = 1

112 mod 2^3 = 0

211 mod 2^3 = 3

221 mod 2^3 = 5

212 mod 2^3 = 4

If **n = 4**. The set is

(1112, 1121, 1211, 2111, 2211, 2121, 2112, 1212, 1122, 2221, 2212, 2122, 1222, 1221)

**1112** = 2 * 2 * 2 * 139

**1121** = 19 * 59

**1211** = 7 * 173

**2111** is a prime number.

**2211** = 3 * 11 * 67

**2121** = 3 * 7 * 101

**2112** = 2 * 2 * 2 * 2 * 2 * 2 * 3 * 11

**1212** = 2 * 2 * 3 * 101

**1122** = 2 * 3 * 11 * 17

**2221** is a prime number.

**2212** = 2 * 2 * 7 * 79

**2122** = 2 * 1061

**1222** = 2 * 13 * 47

**1221** = 3 * 11 * 37

Only **2112** is divisible by **2^4**

1112 mod 2^4 = 8

1121 mod 2^4 = 1

1211 mod 2^4 = 11

1212 mod 2^4 = 12

1221 mod 2^4 = 5

1122 mod 2^4 = 2

1222 mod 2^4 = 6

2111 mod 2^4 = 15

2211 mod 2^4 = 3

2121 mod 2^4 = 9

2112 mod 2^4 = 0

2221 mod 2^4 = 13

2212 mod 2^4 = 4

2122 mod 2^4 = 10

These examples show that for **n = 2, 3** and **4** there is a unique number that is divisible by **2^n**

Generalize this.

That is, prove that for any integer N that contain __both__ the digits 1 and 2, there exists only one n-digit number that is divisible by 2^n.

We can always find an n-digit number that is formed with only digits 1 and 2 and divisible by 2^n.

It remains to prove that there exists a **unique** n-digit number.

To prove that **N mod 2^n = 0** is unique.

Let A_n and B_n be n-digit numbers.

A_n = a(1).a(2).a(3)….a(n) and B_n = b(1).b(2).b(3)….b(n)

where each of a(1), a(2), …, a(n) and b(1), b(2), …, b(n) is 1 or 2.

Let’s suppose that

a(1).a(2).a(3)….an ≡ b(1).b(2.b3)….bn (mod 2^n)

Then clearly

a(1).a(2).a(3)….an ≡ b(1).b(2).b(3)….b(n) (mod 2)

then we also have

a(1).a(2).a(3)….a(n) ≡ a(n) (mod 2)

b(1).b(2).b(3)….b(n) ≡ b(n) (mod 2)

so a(n) ≡ b(n) (mod 2)

But **a(n)** is either 1 or 2 and **b(n)** either 1 or 2

so a(n) = b(n) = 1 or a(n) = b(n) = 2

In either case a(n) = b(n)

Hence a(n).a(2)…a(n-1) ≡ b(1).b(2)….b(n-1) ( mod 2^(n-1) )

we can finish by induction to conclude a(1).a(2)…a(n) = b(1).b(2)….b(n)

Do recursively: if string of 1’s & 2’s of length n is div by 2^n, prepend 1 if quotient is odd, 2 if even http://bit.ly/VGosp9