Use Pigeon Hole Principle here

pigeonhole-principle

Here is the question:

There are 17 distinct positive integers such that none of them has a prime factor exceeding 10. Show that product of some two of them is a square.

Now, how to do this using Pigeon Hole Principle? I have absolutely no idea about that here. The fact that we have to prove here doesn't even seem intuitive at all. Please help.

Thanks.

Best Answer

The primes below 10 are 4:

$2,3,5,7$

So each of your numbers has the form:

$2^a \cdot 3^b \cdot 5^c \cdot 7^d$

There 16 possible tuples (a,b,c,d) when each of $a,b,c,d$ is viewed modulo 2.

We define each pigeonhole as the sequence $(A,B,C,D)$ where A,B,C,D are the residues of a,b,c,d respectively when divided by 2. There are 16 possible pigeonholes ($2 \cdot 2 \cdot 2 \cdot 2$).

This means you can find two numbers $X,Y$ among those 17 such that their tuples

$a_1,b_1,c_1,d_1$ and $a_2,b_2,c_2,d_2$

are such that

$a_1$ and $a_2$ are both odd or both even
$b_1$ and $b_2$ are both odd or both even
$c_1$ and $c_2$ are both odd or both even
$d_1$ and $d_2$ are both odd or both even

Now multiply X and Y and you get a square because

$a_1 + a_2$, $b_1 + b_2$, $c_1 + c_2$, $d_1 + d_2$

will all be even.

Related Question