Skip to main content
OlympiadHQ

Browse · MathNet

Print

SAMC

Saudi Arabia number theory

Problem

Prove that among any nine divisors of there are two whose product is a perfect square.
Solution
Let us factor .

Any divisor of can be written as where .

The product of two divisors and is a perfect square if and only if , , and are all even.

This is equivalent to , , .

Thus, for each divisor, consider the triple . There are possible such triples.

If we select 9 divisors, by the pigeonhole principle, at least two of them must have the same triple. For these two divisors, the exponents of , , and have the same parity, so their sum is even for each prime, and thus their product is a perfect square.

Therefore, among any nine divisors of , there are two whose product is a perfect square.

Techniques

Divisibility / FactorizationPigeonhole principle