Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to prove the following:

The set $A$ consists of $n + 1$ positive integers, none of which have a prime divisor that is larger than the $n$th smallest prime number. Prove that there exists a non-empty subset $B\subseteq A$ such that the product of the elements of $B$ is a perfect square.

Clearly each number is of the type $2^{\alpha_1}3^{\alpha_2}5^{\alpha_3}\cdots p_n^{\alpha_n}$ where $p_n$ is the $n$th prime number and $\alpha_i\ge 0$.

Now if I was given more then $2^n$ numbers then I could have divided the numbers by the parity of the exponents of the primes in $2^n$ classes. By the pigeonhole principle two numbers would be in the same class and hence their product would be a perfect square.

Since I am given $n+1$ numbers I need to divide them into $n$ classes to get the pigeonhole working. The obvious thing is to divide into classes mod $n$. But this obviously doesn't work, as is evident from $n=4$ and the numbers $2,3,5,6,7$.

Anu suggestions on how should I prove this result?

share|improve this question

3 Answers 3

up vote 3 down vote accepted

Ah, you see, you are given $n+1$ numbers, but how many subsets of those numbers do you have?

If you've got a set $B$ whose elements multiply to $\pi=p_{1}^{\beta_1}\cdots p_n^{\beta_n}$, separate the square-free part, so that $\pi=m^2\chi$ where $\chi$ is some product of distinct primes. There are $2^n-1$ nonempty sets of distinct primes from $p_1,\ldots,p_n$ and $2^{n+1}-1$ nonempty subsets from your $n+1$ integers, so here is where you can use the pigeonhole principle.

After you've got your sets $A$ and $B$ with the same $\chi$ parts, the product of their $\pi$'s is a perfect square as you've said. This number itself may not be a $\pi$ of any subset though; at that point, you should look to $(A\cup B)\setminus (A \cap B)$ and prove that that's your perfect square.

share|improve this answer
    
Thanks. Please correct the typo in the last lineL The set is $(A\cup B)\setminus(A\cap B)$. –  Shahab Oct 7 '12 at 9:06

Given the $n+1$ numbers, how many non-empty products are there? Each product is $2^{\beta_1}3^{\beta_2}\cdots p_n^{\beta_n}$; how many "parity-boxes" are there for the exponents? Now you can use pigeonhole, though you still have to work out how to finish things off once you have your two pigeons in the same hole.

share|improve this answer

Here is a nice presentation of the proof using linear algebra:

Identify each number $p_1^{a_1}\dots p_n^{a_n}$ with the tuple $(a_1,\dots,a_n)$, with each $a_i$ reduced modulo $2$, and note that multiplying numbers corresponds to adding their tuples, and that a square is precisely a number whose associated tuple is $(0,\dots,0)$.

We can think of these tuples as vectors in ${\mathbb F_2}^n$, where $\mathbb F_2$ is the field of two elements. This is a vector space of dimension $n$, and $n+1$ vectors are given, so they are linearly dependent, that is, there is a nontrivial linear combination of them that equals $0$. But a linear combination is just a sum of some of them (since the only scalars are $0$ and $1$), and we are done.

share|improve this answer
1  
Thanks. I like your answer. –  Shahab Feb 22 at 13:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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