Olympiad Maths Prep

Library / /45 of 60

Number theory Difficulty 6.5 National olympiad Prove it Ukraine

NN positive integer numbers are given, such that greatest common divisors of all nonempty sets of these numbers are pairwise distinct. Determine the smallest possible number of distinct prime divisors of the product of these NN numbers.
(OleksandrGolovanov)

Solution

Firstly we provide an example of such NN numbers. Consider numbers ak=pkpk+1pk+2pk+N1a_k = p_k p_{k+1} p_{k+2} \dots p_{k+N-1}, where p1,p2,,pNp_1, p_2, \dots, p_N are NN distinct prime numbers and pN+i=pip_{N+i} = p_i (1iN11 \le i \le N-1). Indeed, GCD of any set will include pkp_k exactly in a power 1 if and only if aka_k belongs to this set. It means that GCD of all sets will be distinct.

Let us prove that it could not be less than NN prime divisors. Assume that numbers a1,a2,...,aNa_1, a_2, ..., a_N satisfy the condition and their product has only m<Nm < N distinct prime divisors p1,p2,...,pmp_1, p_2, ..., p_m. For every pip_i we choose akia_{k_i} that includes pip_i in the smallest possible power. Consider the set of all such akia_{k_i} taken once (it might be that aki=akja_{k_i} = a_{k_j} with iji \neq j, in this case still our set will include akia_{k_i} exactly one time). This set will consist of not more than m<Nm < N numbers. GCD of all numbers of this set will include pip_i in the power that is equal to the smallest power in which pip_i belongs to a1,a2,...,aNa_1, a_2, ..., a_N. Thus if we add any of the aia_i to our set, GCD of all numbers in the set will be the same. And we have a contradiction.

Looking for a route rather than 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.