15.5 Miscellaneous

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²+y². If no such representation exists TwoSquares will return fail. TwoSquares will return a representation for which the gcd of x and y is as small as possible. It is not specified which representation TwoSquares returns, if there is more than one.

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 minmal possible gcd of x and y is the square root c of a b. The number of different minimal representation with x £ y is 2^l-1, where l is the number of different prime factors of the form 4k+1 of n.

The algorithm first finds a square root r of -1 modulo n / (a b), which must exist, and applies the Euclidean algorithm to r and n. The first residues in the sequence that are smaller than [Ö(n/(a b))] times c are a possible pair x and y.

Better descriptions of the algorithm and related topics can be found in: S. Wagon, The Euclidean Algorithm Strikes Again, AMMon 97, 1990, 125-129 D. Zagier, A One-Sentence Proof that Every Pri.., AMMon 97, 1990, 144-144

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

[Top] [Previous] [Up] [Index]