Solution to puzzle 80: Sixes and sevens

Does there exist a (base 10) 67-digit multiple of 2⁶⁷, 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⁶⁷, written exclusively with the digits 6 and 7, does exist.

Remarks

In fact, the induction step gives an explicit means of constructing successive values of n_k. Specifically, we find that

6677767667676666776766667777767666677766776777777777777666766667776 = 2⁶⁷×45250313829053138281370553831260951302463537892.

Alternative proof

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

There are exactly 2⁶⁷ 67-digit numbers containing only the digits 6 and 7.

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

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

Thus, we see that the 67-digit numbers with digits 6 or 7 represent all congruences modulo 2⁶⁷: 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.

Generalization

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