How to use Pigeon Hole Principle here?

Question

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.

Answer 1

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.

Answer 2

First note that there are $4$ distinct primes less than $10$: $2,3,5$, and $7$.

Next, note that a positive integer is a square if and only if the exponent of each prime in its prime factorization is even.

Consider the prime factorizations of the $17$ distinct positive integers $n_1,...,n_{17}$: \begin{align*} n_1 &=2^{a_1}3^{b_1}5^{c_1}7^{d_1}\\ n_2 &=2^{a_2}3^{b_2}5^{c_2}7^{d_2}\\ &\vdots\\ n_{17} &=2^{a_{17}}3^{b_{17}}5^{c_{17}}7^{d_{17}}. \end{align*}

Then the product of integers $n_i$ and $n_j$ is: $$(n_i)(n_j) = 2^{a_i+a_j}3^{b_i+b_j}5^{c_i+c_j}7^{d_i+d_j}.$$

So you need to show using the pigeonhole principle that you can find $i$ and $j$ such that all of the exponents $(a_i+a_j)$, $(b_i+b_j)$, $(c_i+c_j)$, and $(d_i+d_j)$ are even. To have an even sum, we must add odd+odd or even+even. So you are looking for the parity of all the exponents to be the same. Do you see how to define the pigeonholes to show you can always do this?