Library / /2 of 17

, 2011

Number theory Difficulty 4.7 AIME Prove it Canada

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.

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$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.