Track / Stage 4 / 75 of 340 #335 of 1964

Problem 335

AMC 12 late, AIME early

Number theory Difficulty 4.7 Prove it Kanada · Canada · 2011

Consider 70-digit numbers $n$ , with the property that each of the digits $1, 2, 3, \dots, 7$ appears in the decimal expansion of $n$ ten times (and $8$ , $9$ , and $0$ do not appear). Show that no number of this form can divide another number of this form.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Assume the contrary: there exist $a$ and $b$ of the prescribed form, such that $b \ge a$ and $a$ divides $b$ . Then $a$ divides $b-a$ .

Claim: $a$ is not divisible by $3$ but $b-a$ is divisible by $9$ . Indeed, the sum of the digits is $10(1 + \cdots + 7) = 280$ , for both $a$ and $b$ . [Here one needs to know or prove that an integer $n$ is equivalent to the sum of its digits modulo $3$ and modulo $9$ .]

We conclude that $b-a$ is divisible by $9a$ . But this is impossible, since $9a$ has $71$ digits and $b$ has only $70$ digits, so $9a > b > b-a$ . $\square$

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.