# 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.

{1, 4} {1, 9} {1, 16} {1, 25} {1, 36}

{2, 8} {2, 18} {2, 32}

{3, 12} {3, 27}

{4, 9} {4, 16} {4, 25} {4, 36}

{5, 20}

{6, 24}

{7, 28}

{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.

• Please include in your post your attempt at solving the problem. Otherwise, your question will likely be closed. – Aaron Hendrickson Jun 10 at 21:13
• Hint: consider sets of the form $\{xy\mid y\in\{1,4,9,16,25,36\},\;xy\leq 36\}$ for square free natural numbers $x$. – Don Thousand Jun 10 at 21:14
• This doesn't really seem like a contest problem. If nothing else you can simply check for each $a$ which integers $b; b> a$ in $\{1,2,\ldots, 36\}$ are such that $ab$ is a perfect square, with a few shortcuts along the way: If $a$ is prime then $b$ must be of the form $c^2a$; if $a$ is not prime then write $a=d^2e$ where $d^2$ is the largest square dividing $a$; then $b$ must be of the form $ef^2$ for some other square $f$.... – Mike Jun 10 at 21:48
• So $6$ gives $6=1^2 \times 6$ so $e=6$ and $c^2=1^2$, so the pairs where $6$ is the smallest integer is $(6,24)$. – Mike Jun 10 at 21:50
• OR rather, for each integer $c$ in $\{1,2,\ldots, 36\}$, check the number of ways you can get $c^2$. For example, $c=8$, so $c^2=64=2 \times 32 =4 \times 16$. This is more direct. – Mike Jun 10 at 22:03

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.

• Ah, I see my answer here is essentially the same as Aaron's, just more tersely presented. – Barry Cipra Jun 10 at 23:08
• This explanation is helpful . Thank you. – LxSquid Official Jun 16 at 16:14

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.

• This explanation is helpful . Thank you. – LxSquid Official Jun 16 at 16:14

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.