For how many two-element subsets $\{a, b\}$ of the set $\{1, 2, 3, 4, 5, 6, \dots , 36\}$ is the product $ab$ a perfect square? Problem:
For how many two-element subsets $\{a, b\}$ of the set $\{1, 2, 3, 4, 5, 6, \dots , 36\}$ is the product $ab$ a perfect square?
Note:
The numbers $a$ and $b$ are distinct, so the $a$ and $b$ must be different integers from the set of numbers $1 - 36$.
Reiteration:
Using two integers selected from the number group, $1-36$, how many combinations are possible so that the product of the two numbers selected is a perfect square.
Attempt:
First list out the square numbers between 1-36 (inclusive):
1, 4, 9, 16, 25, 36.
NOTE: The square number “1” does not work because a and b need to be distinct.
Rewrite the numbers paired with the number “1” so that it is in the format {a, b}.
(4, 1)
(9, 1)
(16, 1)
(25, 1)
(36, 1)
Next, since the number “16” for example, it can be broken down into 4•4 or 8•2, the subset {8, 2} also works.
4 : 2•2 (Note: 2•2 does not work because a and b need to be distinct)
16 : 4•4 or 8•2 (Note: 4•4 does not work because a and b need to be distinct)
36 : 2•18 or 3•12 or 4•9
Currently, we have found 9 solutions.
Issue:
I currently found 9 out of the total number of solutions that satisfy this problem. But, I have ran into an issue : What is the most efficient way to organize your solutions and find other combinations?
Attempt Continued:
I then continued to list out the combinations but started with the sets with “1” in the front and then 2, then 3, then 4, etc.
Subsets which start with “1”:
{1, 4}
{1, 9}
{1, 16}
{1, 25}
{1, 36}
Subsets which start with “2”:
{2, 8}
{2, 18}
{2, 32}
Subsets which start with “3”:
{3, 12}
{3, 27}
Subsets which start with “4”:
{4, 9}
{4, 16}
{4, 25}
{4, 36}
Subsets which start with “5”:
{5, 20}
Subsets which start with “6”:
{6, 24}
Subsets which start with “7”:
{7, 28}
Subsets which start with “8”:
{8, 18}
{8, 16}
Conclusion:
The list keeps going on. The correct answer for this question is 27. If you carefully calculate and list out the subsets, you can get the answer.
 A: Every number $n$ can be written as the product of a square part and a square-free part $n=a^2b$ where no perfect square besides $1$ divides $b$.  One way to see this is to look at the prime factorization: if $n=\prod p_i^{k_i}$, let $\epsilon_i=1$ if $k_i$ is odd and $0$ if $k_i$ is even.  Then $a=\prod p_i^{\lfloor k_i/2 \rfloor}$ and $b=\prod p_i^{\epsilon_i}$.  Then $mn$ will be a perfect square if and only if the squarefree part of $m$ equals the squarefree part of $n$.
By getting rid of all the multiples of 4, 9, and 25, we see that the squarefree numbers less than 36 are
$$1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 33, 34, 35$$
For each of these numbers, we can look at how many different square parts can go with those square-free parts to get a number less than or equal to 36. For any number greater than 9, there is at most 1 number with that square-free part: we would be $1^2b$, but then $2^2b$ would already be too big.  So, for example, there aren't two numbers less than 36 that both have square-free part 11, and so no way to multiply 11 by something less than 36 to get a perfect square.
The squarefree numbers less than 9 are
$$1, 2, 3, 5, 6, 7$$
and the numbers with those square-free parts are the following sets
$$\{1,4,9,16,25,36\}, \{2, 8, 18, 32\}, \{3, 12, 27\}, \{5, 20\}, \{6, 24\}, \{7, 28\}.$$
There are 6C2 ways to pick 2 numbers from the first set, 4C2 ways to pick 2 numbers from the second set, 3C2 ways to pick 2 numbers from the 3rd set, and 1 way to pick 2 numbers from each of the last 3 sets.  This gives a total of $15+6+3+1+1+1=27$ different 2 element sets.
Note that we could have figured out how big each of those sets were without listing out all the elements, for example, if the square-free part of a number is 3, and $3a^2\leq 36$, then $a\leq \sqrt{26/3}$, but it is instructive to list out the full sets.
A: The challenge here is to think of some efficient way to "see" the solution. Here's one idea, based on the OP's first step, namely isolating the squares:
Partition the integers from $1$ to $36$ into square multiples of squarefree numbers:
$$\begin{align}
&\{1,4,9,16,25,36\}\\
&\{2,8,18,32\}\\
&\{3,12,27\}\\
&\{5,20\}\\
&\{6,24\}\\
&\{7,28\}\\
\end{align}$$
where we don't need to go any further because every other number belongs to a singleton. Now pairs $a$ and $b$ that multiply to a square must both come from the same set. We thus have
$${6\choose2}+{4\choose2}+{3\choose2}+{2\choose2}+{2\choose2}+{2\choose2}=15+6+3+1+1+1=27$$
pairs in all.
A: Define $f(n)$ to be $n$ divided by the largest perfect square that divides $n$; for example, $f(180) = f(6^2\cdot5)=5$ and $f(30)=30$ and $f(25)=1$. Then $ab$ is a perfect square if and only if $f(a)=f(b)$, which should make the answer easy to calculate.
