Maths Olympiad Prep

Track / Stage 6 / 50 of 400 #1050 of 1964

Problem 1050

National olympiad, first round
Number theory Difficulty 6.0 Prove it

Example 1 (30th Russian Mathematical Olympiad) Can a positive integer be written at each integer point in the plane so that three integer points are collinear if and only if the 3 positive integers written on them have a common divisor greater than 1?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

It cannot be done. Assume it can be done. Now consider an integer point AA, assume it is labeled with a positive integer aa. Let aa have nn distinct prime factors.

Take another integer point A1A_{1} in the plane. Clearly, there are other integer points B1B_{1} on the line AA1A A_{1}, for example, B1B_{1} can be taken as the symmetric point of AA with respect to A1A_{1}.

Since the 3 numbers written on A,A1,B1A, A_{1}, B_{1} have a common divisor greater than 1, they can all be divided by some prime p1p_{1}. In particular, p1ap_{1} \mid a.
Take another integer point A2A_{2} in the plane, such that A2A_{2} is not on the line AA1A A_{1}.
There are other integer points B2B_{2} on the line AA2A A_{2}, the 3 numbers written on A,A2,B2A, A_{2}, B_{2} can all be divided by some prime p2p_{2}. In particular, p2ap_{2} \mid a.
Since A,A1,A2A, A_{1}, A_{2} are not collinear, p1p2p_{1} \neq p_{2}. Continue this process to construct lines AA3,AA4,,AAn+1A A_{3}, A A_{4}, \cdots, A A_{n+1}, each time obtaining a new prime that can divide aa, resulting in a total of n+1n+1 distinct primes, all of which can divide aa. This contradicts the assumption that aa has only nn distinct prime factors.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.