Competition problem — Number theory

Library / /3 of 18

Number theory Difficulty 4.7 AIME Prove it United States

Problem:

Six distinct numbers are chosen from the list $1, 2, \ldots, 10$ . Prove that their product is divisible by a perfect square greater than 1.

Solutions — 2

Solution 1

Solution:

If all the odd numbers are chosen, then in particular $9$ is chosen and the product is divisible by $9$ .
If not all the odd numbers are chosen, then at most $4$ odds and thus at least $2$ evens are chosen. Therefore the product is divisible by $4$ .

Solution 2

Solution:

At most one of the numbers is $1$ , and each of the other numbers has at least one prime factor. Therefore the product of the six chosen numbers consists of at least five prime factors. But there are only four prime factors in the numbers from $1$ to $10$ : $2, 3, 5$ , and $7$ . So some prime appears twice, making a square divisor greater than $1$ .

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.