4

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.

user26857
  • 52,094
nmnsharma007
  • 383
  • Each integer is in the form $2^a 3^b 5^c 7^d$. Consider the parities of $a,b,c,d$ for each integer. – player3236 Sep 29 '20 at 16:11
  • 2, 3, 5, 7 are primes less than 10. What kind of numbers can you form by multiplying just these numbers amongst themselves if you need to construct 17 different numbers? Use that logic and build your solution. – vvg Sep 29 '20 at 16:19

2 Answers2

5

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.

Acccumulation
  • 12,210
peter.petrov
  • 12,568
  • 1
    Actually I did, but it came out to be wrong, because there are 16 tuples when all powers are odd.But what after that? What if one power was odd and other were even?? So, please the provide the full solution.Thanks. – nmnsharma007 Sep 29 '20 at 16:14
  • @nmnsharma_007 "because there are 16 tuples when all powers are odd" >>> this does not make sense. I wrote the complete solution. – peter.petrov Sep 29 '20 at 16:16
  • 1
    How did you make sure that in case of 17 integers it will surely happen?Am i missing something? – nmnsharma007 Sep 29 '20 at 16:18
  • 1
    @nmnsharma_007 Yes, you seem to be missing a lot. Think some more. – peter.petrov Sep 29 '20 at 16:20
  • 1
    Oh!!! If I understood correctly, since we have 4 numbers and hence 16 tuples are possible, then if a 17th tuple exists, it must surely be a repetitive one and so when multiplied by its previous existence, it will give a square.is it correct? – nmnsharma007 Sep 29 '20 at 16:22
  • @nmnsharma_007 Yeah... sort of... each tuple is a sequence of 1s and 0s (the residues when divided by 2) Basically we prove that you have two numbers whose parities of the exponents coincide. – peter.petrov Sep 29 '20 at 16:23
  • 1
    Yeah, so if 17th tuple exists. It is surely same as some previous tuple and hence we get a square.is it correct? – nmnsharma007 Sep 29 '20 at 16:23
  • The 17th tuples exists, you have 17 numbers :) Yeah, in the set of the (A,B,C,D) tuples you surely have 2 which are equal. – peter.petrov Sep 29 '20 at 16:25
  • 1
    But a 17th tuple isn't possible. is it? – nmnsharma007 Sep 29 '20 at 16:25
  • You have 17 tuples but only 16 possible distinct tuples. So two tuples must be equal. When I say you have 17 tuples I don't mean they are distinct. – peter.petrov Sep 29 '20 at 16:26
  • 1
    and hence they can combine to give a square. Thanks a lot for your help. I got it. – nmnsharma007 Sep 29 '20 at 16:27
  • 2
    @nmnsharma_007 Yeah, exactly. – peter.petrov Sep 29 '20 at 16:27
5

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?

kccu
  • 20,808
  • 1
  • 22
  • 41