Does there exist a (base 10) 67-digit multiple of 2^{67}, written exclusively with the digits 6 and 7?

More generally, there exists a *k*-digit number, written exclusively with the digits 6 and 7, which is divisible by 2^{k}. The proof is by mathematical induction on `k`.

The induction will consist of two steps:

- Basis: Show the proposition is true for a 1-digit number.
- Induction step: Prove that
*if*the proposition is true for some arbitrary value,`k`> 0,*then*it holds for`k+1`.

The basis is straightforward: we simply note that 6 is a single-digit multiple of 2.

For the induction step, we assume the inductive hypothesis: there exists a k-digit number, n_{k}, written exclusively with the digits 6 and 7, divisible by 2^{k}.

Since n_{k} 0 (modulo 2^{k}), we have n_{k} 0 or 2^{k} (mod 2^{k+1}).

Note that, since 10^{k} = 2^{k}×5^{k}:

6×10^{k} 0 (mod 2^{k+1})

7×10^{k} 2^{k} (mod 2^{k+1})

Hence, we choose:

n_{k+1} | = 6×10^{k} + n_{k}, if n_{k} 0 (mod 2^{k+1}); or |

= 7×10^{k} + n_{k}, if n_{k} 2^{k} (mod 2^{k+1}) |

It follows that n_{k+1} is a (k+1)-digit number, written exclusively with the digits 6 and 7, and is divisible by 2^{k+1}.

This completes the inductive proof. Hence a 67-digit multiple of 2^{67}, written exclusively with the digits 6 and 7, *does* exist.

In fact, the induction step gives an explicit means of constructing successive values of n_{k}. Specifically, we find that

6677767667676666776766667777767666677766776777777777777666766667776 = 2^{67}×45250313829053138281370553831260951302463537892.

Dimitris Skouteris sent the following elegant solution which highlights another aspect of this puzzle.

There are exactly 2^{67} 67-digit numbers containing only the digits 6 and 7.

The difference of any two of these is not divisible by 2^{67} since it is expressible as the sum or difference of powers of 10, the smallest of which is 10^{n}, with n < 67.

Hence, these 2^{67} numbers have pairwise different remainders on division by 2^{67}, and since there are 2^{67} such remainders (from 0 to 2^{67}−1) there must be (exactly one) which has remainder 0 and hence is divisible by 2^{67}.

Thus, we see that the 67-digit numbers with digits 6 or 7 represent all congruences modulo 2^{67}: one each. This suggests a generalization:

For any pair of digits r and s (with r − s odd) there exists exactly one k-digit number containing only the digits r and s for each congruence modulo 2^{k}.

Show that every number which is not divisible by 5 has a multiple whose only digits are 6 and 7.

Source: Spirit of '76, on flooble :: perplexus