Maths Olympiad Prep

Library / /1 of 4

Combinatorics Difficulty 4.4 AIME Prove it Brazil

Show that there is a number of the form 19991199\dots 91 (with nn 9s) with n>2n > 2 which is divisible by 19911991.

Solution

There are many ways to solve the problem, using, for instance, Euler-Fermat theorem. But one student, André Reys Leal, obtained a clever, simple solution: consider all numbers of the form 1999911999\dots 91 with more than two nines. If one of them is multiple of 19911991 we are done. If not, since there are infinite of them there are two that are the same modulo 19911991. By subtracting them, we obtain 19999800001999\dots 98000\dots 0, which is a multiple of 19911991. We may ignore all rightmost zeros, but we do keep three of them, obtaining 1999980001999\dots 98000, which is still a multiple of 19911991. Sum 19911991 to it and we are done.

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.