# How many perfect squares exist? [closed]

Consider a set of $1985$ positive integers not necessarily distinct. Every number in set can be written in the form $p_1^{{\alpha _1}}p_2^{{\alpha _2}} \cdots p_9^{{\alpha _9}}$ where $p_1,p_2,\ldots,p_9$ are distinct prime numbers and $\alpha_1,\alpha_2,\ldots,\alpha_9$ are non-negative integers. At least how many pairs of integers exist in this set such that their product is a perfect square?

## closed as off-topic by heropup, Shailesh, Daniel W. Farlow, JonMark Perry, Claude LeiboviciApr 14 '16 at 3:52

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – heropup, Shailesh, Daniel W. Farlow, JonMark Perry, Claude Leibovici
If this question can be reworded to fit the rules in the help center, please edit the question.

• I'm not sure I understand the question, but isn't one pair enough? Example $p_1=2$ and $\alpha_1=2$. – Paul Irofti Apr 6 '16 at 15:47
• not necessarily distinct $\implies$ multi-set, not set. – barak manos Apr 6 '16 at 16:02

Consider the map $f\colon n\mapsto(\alpha_1\bmod 2,\ldots,\alpha_9\bmod 2)\in\{0,1\}^{9}$. For two numbers $n,m$, the product $nm$ is a perfect square iff $f(n)=f(m)$. So if $c_1,\ldots,c_{512}$ are the cardinalities of preimages of the $1024$ elements of $\{0,1\}^{9}$, then we have $$\sum{c_i\choose 2}=\frac12\sum c_i^2-\frac12\sum c_i=\frac12\sum c_i^2-\frac{1985}2$$ such pairs. The quadratic sum becomes minimal (under the restriction of $\sum c_i=1985$) if the $c_i$ are "as equal as possible", so there must be $449$ times $c_i=4$ and $63$ times $c_i=3$, leading to a minimal (and actually achievable) result of $$449\cdot{4\choose 2}+63\cdot {3\choose 2}=2883.$$