4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – player3236 Sep 29 at 16:11
  • $\begingroup$ 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. $\endgroup$ – vvgiri Sep 29 at 16:19
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – nmnsharma_007 Sep 29 at 16:14
  • 1
    $\begingroup$ How did you make sure that in case of 17 integers it will surely happen?Am i missing something? $\endgroup$ – nmnsharma_007 Sep 29 at 16:18
  • 1
    $\begingroup$ @nmnsharma_007 Yes, you seem to be missing a lot. Think some more. $\endgroup$ – peter.petrov Sep 29 at 16:20
  • 1
    $\begingroup$ 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? $\endgroup$ – nmnsharma_007 Sep 29 at 16:22
  • 2
    $\begingroup$ @nmnsharma_007 Yeah, exactly. $\endgroup$ – peter.petrov Sep 29 at 16:27
4
$\begingroup$

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?

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ how to define the pigeon holes? I suck at that already $\endgroup$ – nmnsharma_007 Sep 29 at 16:17
  • $\begingroup$ The pigeonholes are sequences of length 4 formed by just 0s and 1s. E.g. (0,1,0,1) is one such pigeonhole. (1,1,0,1) is another and so on. $\endgroup$ – peter.petrov Sep 29 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.