6
$\begingroup$

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

  • 0
    ...and those smaller squares can be chosen to be distinct unless the original number is the fourth power of a prime.2012-12-26

2 Answers 2

8

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.

  • 0
    yeah.. good one thanks :)2012-12-26
1

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.