# Solution to puzzle 80: Sixes and sevens

Does there exist a (base 10) 67-digit multiple of 267, 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 2k.  The proof is by mathematical induction on k.

The induction will consist of two steps:

1. Basis: Show the proposition is true for a 1-digit number.
2. 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, nk, written exclusively with the digits 6 and 7, divisible by 2k.

Since nk 0 (modulo 2k), we have nk 0 or 2k (mod 2k+1).

Note that, since 10k = 2k×5k:

6×10k 0 (mod 2k+1)
7×10k 2k (mod 2k+1)

Hence, we choose:

 nk+1 = 6×10k + nk,  if nk 0 (mod 2k+1);  or = 7×10k + nk,  if nk 2k (mod 2k+1)

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

This completes the inductive proof.  Hence a 67-digit multiple of 267, 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 nk.  Specifically, we find that

6677767667676666776766667777767666677766776777777777777666766667776 = 267×45250313829053138281370553831260951302463537892.

## Alternative proof

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

There are exactly 267 67-digit numbers containing only the digits 6 and 7.

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

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

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

## 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