Maths Olympiad Prep

Library / /1 of 12

Number theory Difficulty 5.6 AIME, harder Prove it Czech Republic

Prove the claim: If we choose any four factors of 720720, then one of them divides the product of the other three.

Solutions — 2

Solution 1

Given the decomposition 720=24325720 = 2^4 \cdot 3^2 \cdot 5, the number 720720 has exactly three prime factors: 22, 33 and 55. So, each of its factors is of the form 2α3β5γ2^\alpha \cdot 3^\beta \cdot 5^\gamma, where α,β,γ\alpha, \beta, \gamma are non-negative integers (satisfying the inequalities α4\alpha \le 4, β2\beta \le 2 and γ1\gamma \le 1 which we will not need further). Surely also the product of any three factors of 720720 is of the form 2α3β5γ2^\alpha \cdot 3^\beta \cdot 5^\gamma with non-negative integers α,β\alpha, \beta and γ\gamma. Considering any two numbers of this form, the first is a quotient of the second if and only if the values α,β,γ\alpha, \beta, \gamma of the first number do not exceed the corresponding values of the second number.

We prove the problem statement by contradiction. Let us admit that some four factors of the number 720720 have the property that none of them divides the product of the other three factors. Then each of them contains in its prime decomposition some of the primes 22, 33, 55 to a higher power than it has in its decomposition the product of the other three factors, and therefore any one of them. But there are four divisors and only three prime numbers, and this is the contradiction.

Solution 2

We present one of several possible variations of a direct proof. We use the observations contained in the first paragraph of the previous solution.

Let us choose any four factors of the number 720720, call them Numbers. First, we choose three Numbers, that contain prime factor 22 in powers not exceeding that power of 22 in the fourth Number (if there are more than one such choice, we choose one of them). Then we select two of these three Numbers that contain prime factor 33 in powers, that do not exceed power of 33 of the third Number. Of these two Numbers, we finally select the one that contains the prime factor 55 in a power not exceeding power of 55 of the second Number. In the last selected number, each p{2,3,5}p \in \{2, 3, 5\} has a power that does not exceed at least one of the powers of pp in the other three Number. This guarantees that the last selected Number has the property required by the problem statement.

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.