This is a follow up of the prior blog post on primes that are congruent to 1 mod 4 being uniquely the sum of squares. In other words, such primes can be written as x² + y² with x and y positive integer. There is a natural follow up question, are there any more ways to combine squares of integers to produce primes. And yes, there is one more easily computable example. If a prime is congruent to 1 mod 3, then it can be written uniquely as the three times the square of one integer plus the square of another. In other words, such a prime can be written as 3x² + y² with x and y positive integers. And like for primes congruent to 1 mod 4, there is an efficient way to compute the break down of the prime into the squares. For more on this general topic see Fermat Sum of Two Squares.

For the primes congruent to 1 mod 4, we used the Gaussian integers and applied the Euclidean algorithm. For the primes congruent to 1 mod 3, we use the Cyclotomic 3rd root of unity integers and still use the Euclidean algorithm. Note, the Gaussian integers are actually the Cyclotomic 4th root of unity integers. See Cyclotomic Fields Wiki for a definition of Cyclotomic fields and the definition of a ring of integers inside the field. 

The key fact is that Cyclotomic 3 and Cyclotomic 4 fields are quadratic extensions of the rational numbers. And the general theory of Quadratic Forms says that finding solutions mod a prime will, for enough primes and powers of primes, will give you a solution in the integers. For our two simple cases, finding a solution mod p is sufficient for a mod p case to be lifted to integer solutions.

The code for the case of primes congruent to 1 mod 3 is similar enough to the code for primes congruent to 1 mod 4, that instead of providing code just to do the 1 mod 3 case, the code does both cases simultaneously. In particular if a prime is congruent to 1 mod 12, you will see a break down into a sum of squares and the breakdown into three times a square plus a square. To see the code click the three dots at the end of this sentence. ...

Lately I been revisiting some of my old number theory that I learned decades ago. In particular, there have generally been two principles that I learned about numbers.

• Primes are essentially random and at numbers of around size N, they appear with density one over the natural logarithm of N.
• Squares of positive integers are not random. And the density of squares at size N is one over the square root of N, far less often than primes for large N.

So decades ago, I was amazed by the theorem that says every prime congruent to one mod 4 (or have remainder one when dividing by 4) is always the unique sum of two squares. To see more click the triple dots following this sentence. ...