Maths Olympiad Prep

Library / /29 of 32

Number theory Difficulty 7.5 National Olympiad, round 2 Prove it Estonia

Ats and Pets both thought of two positive integers that do not exceed some positive integer nn. If they both added the numbers they thought of, then both sums gave the same remainder when divided by nn. But if both of them multiplied the numbers they thought of, then both products also gave equal remainders when divided by nn. Is it necessarily true that the numbers they thought of were the same, if
a) n=99n = 99?
b) n=101n = 101?

Solution

a) If Ats thought of numbers 11 and 2121 and Pets of numbers 1010 and 1212, then both get the sum 2222 and the products will be 2121 and 120120, respectively, both of which give the remainder 2121 when divided by 9999.

b) Let the numbers Ats chose be aa and bb, the ones Pets chose cc and dd. According to the conditions stated in the problem, the numbers (a+b)(c+d)(a + b) - (c + d) and abcdab - cd are both divisible by 101101. Let (a+b)(c+d)=101k(a + b) - (c + d) = 101k; then a=101kb+c+da = 101k - b + c + d, from where
abcd=(101kb+c+d)bcd=101kbb2+bc+bdcd=101kb(cb)(db). \begin{aligned} ab - cd &= (101k - b + c + d)b - cd = 101kb - b^2 + bc + bd - cd \\ &= 101kb - (c - b)(d - b). \end{aligned}
Hence also the product (cb)(db)(c - b)(d - b) is divisible by 101101. As 101101 is a prime number, it has to divide either the factor cbc - b or the factor dbd - b. W.l.o.g., let cbc - b be divisible by 101101. As all the numbers are on the interval from 11 to 101101, it means that c=bc = b. But then (a+b)(c+d)=ad(a + b) - (c + d) = a - d, which due to divisibility by 101101 means that a=da = d. Therefore Ats and Pets must have chosen the same numbers.

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.