This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

Does every number which is not divisible by 5 have a multiple whose

only digits are 6 and 7?

arithmetic/digits/6.and.7.s

Yes. My proof follows:

Claim 1: For every k, there is a k-digit number whose only digits

are 6 and 7, which is divisible by 2^k.

The proof is by induction. Suppose N is a k-digit number

satisfying the above condition. Then either N = 0 (mod 2^(k+1))

or N = 2^k (mod 2^(k+1)). Note that 6(10^k) = 0 (mod 2^(k+1)),

and 7(10^k) = 2^k (mod 2^(k+1)). So, either 6*10^k + N or

7*10^k + N is divisible by 2^(k+1).

Claim 2: If m and 10 are relatively prime, then for any r,

there is a number N whose only digits are 6 and 7 such that

N = r (mod m).

Proof: Let K be the (m^2)-digit number whose only digit is 6.

There is an s, 0 <= s < m, so that K + s = r (mod m).

Let N = K + 10^(m - 1) + 10^(2m - 2) + . . . + 10^(sm - s).

Since 10^(im - i) = 1 (mod m), N = K + s (mod m) = r (mod m).

Clearly, every digit of N is either 6 or 7.

Claim 3: If n is not divisible by 5, then there is a number N whose

only digits are 6 and 7, so that N is divisible by n.

Proof: We can write n = (2^k)m, with gcd(m,10)=1.

Use claim 1 to find a k-digit number M, whose only digits are 6 and 7,

which is divisible by 2^k. Choose an integer r so that

(10^k)r + M = 0 (mod m). Use claim 2 to find a number K whose

only digits are 6 and 7, so that K = r (mod m). Let N = 10^k K + M.

Then N = 0 (mod m) and N = 0 (mod 2^k), so N is divisible by n.

Finally, the only digits of N are 6 and 7, so we are done.

--

David Radcliffe radcliff@csd4.csd.uwm.edu

Continue to: