Maths Olympiad Prep

Library / Ukrainian Mathematical Olympiad, Final Round /5 of 16

Ukrainian Mathematical Olympiad, Final Round

Number theory Difficulty 5.1 AIME, harder Prove it Ukraine

Prove for every integer n≥2n \ge 2, that such a set AnA_n of nn pairwise distinct positive integers can be collected that for any different i,j∈Ani, j \in A_n the sum of their squares i2+j2i^2 + j^2 is divisible by their difference i−ji - j.

Solution

An={1⋅n!;2⋅n!;… ;n⋅n!} A_n = \{1 \cdot n!; 2 \cdot n!; \dots; n \cdot n!\}
satisfies the condition of the problem. Indeed, take any two distinct numbers from the set AnA_n: k⋅n!k \cdot n! and m⋅n!m \cdot n!, where 1≤k<m≤n1 \le k < m \le n. Since m−k≤nm-k \le n, it follows that m−k∣n!m-k|n!. Therefore, obviously, (k2+m2)⋅(n!)2(k^2 + m^2) \cdot (n!)^2 is divisible by their difference (m−k)⋅n!(m-k) \cdot n!.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.