Maths Olympiad Prep

Library / /10 of 44

Number theory Difficulty 4.5 AIME Prove it Slovenia

Exactly p1p-1 distinct positive integers are written on the blackboard for some prime number pp. The number pp is among these p1p-1 numbers. For any pair of the numbers the absolute value of their difference is also on the board. Prove that all the numbers on the blackboard are divisible by pp.

Solution

Denote the numbers on the board by a1,a2,,ap1a_1, a_2, \dots, a_{p-1}.
Without loss of generality we may assume that a1<a2<<ap1a_1 < a_2 < \dots < a_{p-1}. Then the numbers a2a1<a3a1<<ap1a1a_2 - a_1 < a_3 - a_1 < \dots < a_{p-1} - a_1 are also written on the blackboard. There are p2p-2 of them and they are all distinct. This is only possible when
ap2=ap1a1a2=a3a1a1=a2a1 \begin{aligned} a_{p-2} &= a_{p-1} - a_1 \\ &\vdots \\ a_2 &= a_3 - a_1 \\ a_1 &= a_2 - a_1 \end{aligned}
Thus, a2=2a1,a3=3a1,,ap2=(p2)a1a_2 = 2a_1, a_3 = 3a_1, \dots, a_{p-2} = (p-2)a_1 and ap1=(p1)a1a_{p-1} = (p-1)a_1. Since pp is a prime and it appears on the blackboard we must have a1=pa_1 = p. We conclude that all the numbers on the blackboard are divisible by pp.

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.