Browse · MathNet
PrintKanada 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 .
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