We have seen that the sum of two squares (2 sq rep) of an integer $N^2$ can be used to factor $N$.
Here we use the same method to show that it can determine if an integer $N$ is a prime. For composite numbers represented by $N^2= a^2+b^2$, we have seen that $a^2$ and $b^2$ will have at least one common factor which is easily calculated using the $\gcd(a^2,b^2)$.
As a reminder, we will give the example of $N=7*37=259$. $N^2=259^2=67081$. $N^2=84^2+245^2$. Calculating the $\gcd$, we get $\gcd(84^2,245^2)= 7^2$. And $\gcd(49,259)=7$ showing that $7$ is a factor.
For primes $p$, we use the same method. First we calculate the 2sq rep of $p^2=a^2 + b^2$, then we calculate the $\gcd(a^2,b^2)$.
Example 1. $N=13=2^2+3^2$. We can't determine from the 2sq rep of $N=13$ if it is a prime. However, using $N^2=13^2=5^2+12^2$, we can check if $a^2$ and $b^2$ have a common factor. Calculating the $\gcd$, we get $\gcd(5^2,12^2)=1$. So we can conclude that $N=13$ is a prime.
This test cannot, of course, determine if a number $N=4*k-1$ is a prime but it can tell if an integer of the form $N=4*k+1$ is a prime.
It would be interesting to see how such a test does when dealing with large numbers and how the above method compare with other primality tests.
Any help with running time, proof and testing large numbers will be greatly appreciated.