Ats and Pets both thought of two positive integers that do not exceed some positive integer . If they both added the numbers they thought of, then both sums gave the same remainder when divided by . But if both of them multiplied the numbers they thought of, then both products also gave equal remainders when divided by . Is it necessarily true that the numbers they thought of were the same, if
a) ?
b) ?
Solution
a) If Ats thought of numbers and and Pets of numbers and , then both get the sum and the products will be and , respectively, both of which give the remainder when divided by .
b) Let the numbers Ats chose be and , the ones Pets chose and . According to the conditions stated in the problem, the numbers and are both divisible by . Let ; then , from where
Hence also the product is divisible by . As is a prime number, it has to divide either the factor or the factor . W.l.o.g., let be divisible by . As all the numbers are on the interval from to , it means that . But then , which due to divisibility by means that . 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.