Maths Olympiad Prep

Library / /1 of 9

, 2019

Number theory Difficulty 5.7 AIME, harder Prove it Japan

Find the smallest integer nn with the following property:
Remainders obtained when nn is divided by 9797, 100100, 103103 are 3232, 3333, 3434, respectively.

Solution

333033333033
Let nn be a positive integer satisfying the conditions of the problem. Then, n32n-32, n33n-33, n34n-34 are multiples of 9797, 100100, 103103, respectively. Then, we have
3n+1=3(n32)+97=3(n33)+100=3(n34)+103, 3n+1 = 3(n-32) + 97 = 3(n-33) + 100 = 3(n-34) + 103,
from which it follows that 3n+13n + 1 is a multiple of 9797, 100100, 103103. Any pair from 9797, 100100, 103103 are relatively prime, we see that 3n+13n+1 must be a multiple of 9710010397 \cdot 100 \cdot 103.
The smallest positive integer nn for which 3n+13n + 1 is a multiple of 9710010397 \cdot 100 \cdot 103 is
9710010313=333033, and since we have \frac{97 \cdot 100 \cdot 103 - 1}{3} = 333033, \text{ and since we have}
9710010313=9710010313+32=1009710010313+33=1039710013+34, \begin{aligned} \frac{97 \cdot 100 \cdot 103 - 1}{3} &= 97 \cdot \frac{100 \cdot 103 - 1}{3} + 32 = 100 \frac{97 \cdot 100 \cdot 103 - 1}{3} + 33 \\ &= 103 \cdot \frac{97 \cdot 100 - 1}{3} + 34, \end{aligned}
we conclude that 333033333033 is the desired answer to the problem.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.