Maths Olympiad Prep

Library / /34 of 101

Number theory Difficulty 5.8 AIME, harder Prove it Estonia

Let nn be a positive integer and dd one of its positive divisors. Integers 11 to nn are written in columns of length dd (the first column contains the numbers 11 to dd, starting from the top, the second column contains the numbers d+1d+1 to 2d2d etc.). Then, one finds the greatest common divisor of each row and finally the least common multiple of the greatest common divisors. Prove that if d<nd < n, then the final result is equal to dd.

Solution

The first two numbers of the ii-th row are ii and i+di+d. Denote the greatest common divisor of this row by aa; since aa divides both ii and i+di+d, it must also divide their difference dd. Thus all the greatest common divisors divide dd, meaning their least common multiple is at most dd. But as the final row is d,2d,,nd, 2d, \dots, n with the greatest common divisor dd, the least common multiple of the greatest common divisors is exactly dd.

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 and solution reproduced as published; topic and difficulty added by this site.