Mathword (http://mathworld.wolfram.com/Squarefree.html) stated that "There is no known polynomial time algorithm for recognizing squarefree integers or for computing the squarefree part of an integer."
Below we provide a simple method to check if a number is square free and provide the square part if it is not.
We start with two simple examples to show how the square part can be determined. We consider $N=3^2*13=117$ and find its sum of two square representation (2sq rep) $N=a^2 + b^2$. $N=3^2*13=117=6^2 + 9^2$. We immediately notice that the square part $3^2$ is common to both $a$ and $b$.
To check that this result is general, we calculate the 2sq rep of $N=3^2*17=153$. We find $N=153=3^2 + 12^2$. And here too we see that $3^2$ is common to both $a$ and $b$.
To check that the previous result is not specific to the $N=117$, we do the same with $N=5*7^2=245=7^2 + 14^2$. Here too, we see that the square part $7^2$ is common to both $a$ and $b$.
The three previous examples have only one 2sq rep. So we need to show that the method works for integers $N$ with more than one 2sq rep. We calculate the 2sq rep for $N=13^2*17=2873=8^2 + 53^2=13^2 + 52^2=32^2 + 43^2$. It is clear that the second 2sq rep $13^2+52^2$ is the one conveying the information on the square part $q^2$. With large integers, one can use the GCD(a^2,b^2) to find the 2sq rep that conveys the information.
We provide now an example of a number $N$ with $3$ factors, only one of which is a square. $N=3^2*5*13=585=12^2 + 21^2= 3^2 + 24^2$. Again, it's clear from this simple example that both representations have the common factor $3^2$.
We now provide an example of a number $N$ with 3 factors but two of which are squares. $N=3^2*5^2*13=2925=3^2 + 54^2=18^2 + 51^2 = 30^2 + 45^2$. It's clear that both $3^2$ and $5^2$ appear in at least one 2sq representation.
For completeness and to answer a question by Somos, we show that it is possible to find if a number $N=3*q^2$ is square free or square full. It is obvious that $N=3*q^2$ does not admit a 2sq rep.
However, if we square the number $N$ to get $N^2=M=9*q^4$, we will be able to show that $N$ was square full. We give the following example: $N=3*5^2$. We take the square to get $N^2=3^2*5^4=21^2 + 72^2=45^2 + 60^2$. It is easy to show that $21^2+72^2=3^2*7^2 + 3^2*24^2=3^2*(7^2+24^2)=3^2*25^2$. Now by taking the square root we get the original number $N=3*25=3*5^2$. We can do the same with the other 2sq rep.
This is of course not a proof that the 2sq rep of an integer will show either that N is square-free or has one square factor (or more). But the numerical evidence suggests that the 2sq rep does in fact provide the information on the square-free and square-full status of an integer. There was no need to factor the integer to find if it is square-free or square-full. Large numbers were not considered because all calculations were done by hand (I can't code). No theorem was proved because I simply don't know enough to provide a solid mathematical foundation to the method.
Any help with the proof and any help with more numerical evidence will be much appreciated.
When calculating the 2sq rep's, it is important to find all of them to make sure that the important one with the information is not missed. I can't make any statement on how efficient the method is compared to others or on how it relates to other areas of mathematics.
