Skip to main content
OlympiadHQ

Browse · MathNet

Print

Kanada 2011

Canada 2011 number theory

Problem

Consider 70-digit numbers , with the property that each of the digits appears in the decimal expansion of ten times (and , , and do not appear). Show that no number of this form can divide another number of this form.
Solution
Assume the contrary: there exist and of the prescribed form, such that and divides . Then divides .

Claim: is not divisible by but is divisible by . Indeed, the sum of the digits is , for both and . [Here one needs to know or prove that an integer is equivalent to the sum of its digits modulo and modulo .]

We conclude that is divisible by . But this is impossible, since has digits and has only digits, so .

Techniques

Divisibility / FactorizationModular Arithmetic