0
$\begingroup$

For each of n = 84 and n = 88, find the smallest integer multiple of n whose base 10 representation consists entirely of 6's and 7's.

How would I go about solving this?

I was thinking about modular arithmetic, but I'm not too familiar with it.

I read up on modular arithmetic, but could not figure out how to solve this problem.

Thanks!

$\endgroup$
5
$\begingroup$

$n=84:$

A number is a multiple of 84 if and only if it is a multiple of 4, 3, and 7.

A number is a multiple of 4 if and only if its last 2 digits form a multiple of 4. In this case, since the last two digits can only be 7 and 6, the only possibility for the last 2 digits is 76.

A number is a multiple of 3 if and only if its digits form a multiple of 3. Adding to a number 6 doesn't affect whether it is a multiple of 3 or not, so a number consisting of 6's and 7's is a multiple of 3 if and only if the number of 7's is a multiple of 3.

At this point we can just use brute force. Since the tens digit must be 7, there must be at least 3 7's. In this case, smallest possible number is 76776, and it is clear that we cannot do better by adding more 7's (since then we would have to have at least 6 7's).

$n=88:$

A number is a multiple of 88 if and only if it is a multiple of 8 and 11.

A number is a multiple of 8 if and only if its last 3 digits form a multiple of 8. In this case, since the last 3 digits can only be 7 and 6, the only possibility for the last 3 digits is 776.

A number is a multiple of 11 if and only if the sum of the digits in the odd place values is off by a multiple of 11 from the sum of the digits in the even place values. This isn't true for 776, but it is true for 6776, which we know is the answer because 6776 is also the smallest number with digits only 6 and 7 that ends in 776 other than 776 itself.

$\endgroup$
  • $\begingroup$ What is a smallest number with the same properties, which divided by $84$ and by $88$? $\endgroup$ – Michael Rozenberg Aug 6 '18 at 5:01
  • 2
    $\begingroup$ @MichaelRozenberg You mean the smallest number divisible by both? Using a similar technique, I see 77776776 as a likely candidate. This is certainly the best possible with 6 7's; as for 3 7's there's only a few possibilities to check. $\endgroup$ – alphacapture Aug 6 '18 at 5:07
  • $\begingroup$ If you break the number into pairs from right to left. Then a number is divisible by $11$ iff the sum of the pairs is divisible by $99$. In this case, $66$ and $77$ can be replaced by $0$, $67$ can be replaced by $1$ and $76$ can be replaced by $-$1. So $6776 \mapsto 1 + ^-1 = 0$. So $6776$ is a multiple of $11$. $\endgroup$ – steven gregory Aug 7 '18 at 1:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.