Problem : Given a number (N) and you need to find whether it can be represented as sum of two squares or not.
Pre-Requisites : None
Explanation :
Any number (lets say A) can be represented in form 4*k+r (where r can 0 , 1 , 2 , 3). Thus possible values for A^2 is 4*k and 4*k+1 , so sum of two squares can never be of the form 4*k +3 .
N = p1 ^ x1 * p2 ^ x2 * …… pm ^ xm (prime factorisation of N) can be represented as the sum of two squares if every prime of the form 4*k +3 have even degree (or power) .
This can be proved using following 5 statements :-
- The product of two numbers, each of which is a sum of two squares, is itself a sum of two squares.
- If a number which is a sum of two squares is divisible by a prime which is a sum of two squares, then the quotient is a sum of two squares.
- If a number which can be written as a sum of two squares is divisible by a number which is not a sum of two squares, then the quotient has a factor which is not a sum of two squares.
- If a and b are relatively prime then every factor of a^2 + b^2 is a sum of two squares.
- Every prime of the form 4n+1 is a sum of two squares.
For proof of these statements refer here.