Maths Olympiad Prep

Library / /41 of 158

Number theory Difficulty 5.2 AIME, harder Prove it Estonia

In his last research, professor PP was concentrating on natural numbers with a certain property. It is known that whenever a natural number xx has this property, all multiples of xx also have this property. Let a1,,ana_1, \dots, a_n be positive integers such that all their divisors that are greater than one have the property professor PP studied. Is it true that all divisors greater than one of the product a1ana_1 \dots a_n definitely have this property?

Solutions — 2

Solution 1

Let k>1k > 1 be any divisor of the product a1ana_1 \dots a_n. Then kk has a prime divisor pp, which is also a divisor of the product a1ana_1 \dots a_n. As pp is a prime, there exists ii, such that pp is a divisor of aia_i. As all the divisors of aia_i greater than 11 have the property, pp also has this property. By the premise, all the multiples of pp have the property, so kk has the property.

Solution 2

Let k>1k > 1 be any divisor of the product a1ana_1 \dots a_n. If kk were relatively prime to all aia_i, it would be relatively prime to the product a1ana_1 \dots a_n, but gcd(k,a1an)=k>1\text{gcd}(k, a_1 \dots a_n) = k > 1. Hence gcd(k,ai)>1\text{gcd}(k, a_i) > 1 for some aia_i. As a divisor of aia_i, the number gcd(k,ai)\text{gcd}(k, a_i) has the property studied by professor PP. As a multiple of gcd(k,ai)\text{gcd}(k, a_i), also kk has the same property.

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.