14.8 TwoSquares

TwoSquares( n )

TwoSquares returns a list of two integers x<=y such that the sum of the squares of x and y is equal to the nonnegative integer n, i.e., n = x^2+y^2. If no such representation exists TwoSquares will return false. TwoSquares will return a representation for which the gcd of x and y is as small as possible. If there are several such representations, it is not specified which one TwoSquares returns.

Let a be the product of all maximal powers of primes of the form 4k+3 dividing n. A representation of n as a sum of two squares exists if and only if a is a perfect square. Let b be the maximal power of 2 dividing n, or its half, whichever is a perfect square. Then the minimal possible gcd of x and y is the square root c of a b. The number of different minimal representations with x<=y is 2^{l-1}, where l is the number of different prime factors of the form 4k+1 of n.

    gap> TwoSquares( 5 );
    [ 1, 2 ]
    gap> TwoSquares( 11 );
    false        # no representation exists
    gap> TwoSquares( 16 );
    [ 0, 4 ]
    gap> TwoSquares( 45 );
    [ 3, 6 ]        # 3 is the minimal possible gcd because 9 divides 45
    gap> TwoSquares( 125 );
    [ 2, 11 ]        # not [ 5, 10 ] because this has not minimal gcd
    gap> TwoSquares( 13*17 );
    [ 5, 14 ]        # [10,11] would be the other possible representation
    gap> TwoSquares( 848654483879497562821 );
    [ 6305894639, 28440994650 ]        # 848654483879497562821 is prime 

Previous Up Top
Index