# product of two distinct squares

Is there any shorter and efficient way to find
if a number can be formed by the product of two distinct square numbers
for example

• 36=4*9
• 144=16*9

help me with an algorithm or the logic

-
Every perfect square that is not the square of a prime number can be written as the product of two smaller squares. –  Brian M. Scott Dec 26 '12 at 13:50
...and those smaller squares can be chosen to be distinct unless the original number is the fourth power of a prime. –  Ilmari Karonen Dec 26 '12 at 14:36

You are looking for a number formed by product of two squares, so you have it written in this form: $n = a^2 b^2$, apply product of powers property, so you have: $n = a^2 b^2 = (ab)^2$, so at the end you have to check if this number is a square. If you want to control if the number is made of two factors you have to find its square root, then check if it's a prime number (as in comment $49 = 7\cdot 7$, $7$ is prime, so you will get only $1 \cdot 49$).

So taking your examples: 36 is a square because $36 = 6 \cdot 6$, now take factors: $6 = 1 \cdot 2 \cdot 3$, so $36 = 1 \cdot 4 \cdot 9$, at the end you multiply some of them: $36 = 4 \cdot 9$ or $36 = 1 \cdot 36$.

144 is a square because $144 = 12 \cdot 12$, now take factors: $12 = 1 \cdot 2 \cdot 2 \cdot 3$, so $144 = 1 \cdot 4 \cdot 4 \cdot 9$, at the end you multiply some of them: $144 = 1 \cdot 144$ or $144 = 4 \cdot 36$ or $144 = 9 \cdot 16$.

If you try with $15$ you can find any product of squars because $15$ isn't a square.

-
I want a and b to be different. you said its enough to check if n is a square. 49=7*7 ( 49 is square,but a and b are not different ) it fails here –  yuv60 Dec 26 '12 at 14:17
yes, you also has to check if squared number is a prime number: 49 = 7*7 (7 is a prime number), so you will get only 7*7 or 1*49 –  Blex Dec 26 '12 at 14:21
yeah.. good one thanks :) –  yuv60 Dec 26 '12 at 14:24

As Blex wrote, a number $n$ is the product of two distinct squares $a^2$ and $b^2$ if and only if can be written as $n = a^2 b^2 = (ab)^2$. Thus, first of all, all such numbers are themselves squares.

Given a square number $n = r^2$, it is the product of two distinct squares if and only if its square root $r$ can be written as the product of two distinct numbers $r = ab$. If we're allowed to choose $a = 1$ and $b = r$ (or vice versa), then this is always possible for any $r > 1$, but I assume you're only interested in the cases where $a$ and $b$ are strictly between $1$ and $r$.

In that case, there are only two ways in which this factorization can fail: either when $r$ is itself a prime, in which case it has no divisors other than $1$ and itself, or when it is the square of a prime $p$, in which case its only non-trivial factorization is $r = p^2$.

Thus, we get the result:

A number $n > 1$ can be written as the product of two distinct squares (both greater than $1$) if and only if it is the square of a number which is neither a prime nor the square of a prime.

-