 # 55 arithmetic/digits/6.and.7.p

## Description

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.

# 55 arithmetic/digits/6.and.7.p

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: