Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
4  
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
add comment

2 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.