Browse · MathNet
PrintSAMC
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.
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