I don't understand why the author states that we can divide the elements of M into 8 classes, what stops us from dividing them into 9 classes instead. There are no restrictions on how many times we multiply the same prime right? The book is "A Walk Through combinatorics" by Miklos Bona. (I will post the solution given by the book below)
>>16873965
>>16873965Write out the prime factorization of an element of M, and consider the parity of each exponent. For each of these exponents, there are two options - odd or even - and since there are only three primes less than 6, this gives 2^3=8 possible exponent parity combinations. Then by the pigeonhole principle, since M has 9 elements, at least two of them must have the same exponent parity combination. The product of two such elements is then a perfect square.
>>16873971Thanks a lot, I understand the solution now.
>>16873986I didn’t even understand the question.
>>168739652, 2, 2, 2, 2, 2, 2, 2, 2
[math]\[\text{Since no element of } M \text{ has a prime divisor } >6,\ \text{every } m\in M \text{ has prime factors only in } \{2,3,5\}.\]Hence we can write uniquely\[m = 2^{a}3^{b}5^{c}\qquad (a,b,c\in \mathbb{Z}_{\ge 0}).\]Define the parity vector\[\pi(m) := (a\bmod 2,\; b\bmod 2,\; c\bmod 2)\in \{0,1\}^3.\]There are only \(2^3=8\) possible values of \(\pi(m)\), but \(M\) contains \(9\) integers. By the pigeonhole principle, there exist distinct \(x,y\in M\) such that\[\pi(x)=\pi(y).\]Write \(x=2^{a}3^{b}5^{c}\) and \(y=2^{a'}3^{b'}5^{c'}\). Then\[a\equiv a'\pmod 2,\quad b\equiv b'\pmod 2,\quad c\equiv c'\pmod 2,\]so \(a+a'\), \(b+b'\), and \(c+c'\) are all even. Therefore\[xy = 2^{a+a'}3^{b+b'}5^{c+c'}\]has all exponents even, hence \(xy\) is a perfect square. \(\qed\)[/math]
