I am not the only one to think 73 is special. See 73_(number) for a Wiki page on 73. But I have my own particular reason for seeing it as special.

We start with a question. But before get there, we start with some definitions. For integers N larger than 1, consider the integers mod N. Or to put it another way, map integers to their remainders after dividing by N. The remainder will be a number between 0 and N - 1. You can add and multiply these remainders and take the remainder of the result. This creates well defined addition and multiplication mod N. Now, of these remainders, only take the non zero remainders that have no common factor with N. For example, if N is 6, then only 1 and 5 satisfy this condition. In mathematics, these remainders under multiplication are called the multiplicative group mod N. It is group because it has an operation, multiplication, which combines two elements of the group to produce another element. Now in this multiplicative group, some elements have the property that if you square it, i.e. multiply it against itself, it gives the remainder 1, or the identity element of the multiplicative group. As a reminder, the identity element is an element that when multiplied against any other element leaves that element untouched.  We will call the remainders whose square is the identity to be of "order 2". Now notice that for N = 8, all the non identity elements in the multiplicative group, which are the remainders 3, 5, and 7, are of order 2. This raises the question, what other N is this true for? Or to be more precise, the question is this, what is the largest N such that the every remainder mod N that has no common factor with N and is not equal to 1 has order 2?

Why is such a question of interest? In mathematics group elements of order 2 are associated with symmetries. For example, if you flip a card and then flip it again, you have acted on it by group action of order 2. Symmetries in mathematics and physics show up everywhere and tend to be fundamental in the theories. Specifically for physics, symmetries, which are also dualities, are foundational. At every place you look you find examples, such as positive and negative charges, up and down spin states for particles, clockwise vs. counterclockwise rotation, and on and on. The derivation of special relativity uses symmetries as its primary driving assumption. They are also at the foundation of a lot of the richer theories in mathematics as well. In our particular case, suppose we have determined the N that is the answer to the question, would primes that map to the identity element mod N have any special properties? And what does this have to do with the prime 73? If you have been reading any of the prior blog articles, you may be able to guess the answer. An answer can be found at Largest N with All Order 2 Multiplicative Group Mod N.

This is a follow up of Three Cases of Primes From Squares which is itself a follow up of prior blogs articles. I started this journey by recalling the theorem that all primes congruent to 1 mod 4 can be written as a sum of two squares. I then recreated the algorithm for efficiently computing the two squares using the Euclidean algorithm on the Gaussian integers. This then led me to examine finding primes and their decompositions into integer squares for other d in the expression p = d·a² + b² where p is a prime. The cases d = 1 and d = 4 are equivalent, so I started with the cases of d = 2 and d = 3 where the quadratic imaginary extension produced by adding the square root of -d was still Euclidean. At that point I thought that I was done. I did not, at first, see a practical way to find the a and b for arbitrary values of d. But, as what is typical for me, I did not know how to stop picking at the problem. One day, when I figured out that there was actually an efficient algorithm for finding square roots mod p, I saw a way forward. But the main breakthrough was when I discovered that the Euclidean algorithm could be extended to non Euclidean fields in a useful way. Investigating this approach, I ran into another roadblock problem that I describe in Approximating Integers with Multiples of Rational Numbers. After eventually finding an efficient solution to that problem, I had all the pieces for breaking down primes with 100s of digits into d times a square plus a square for d up to about 10,000 in less than a minute on my laptop.

However, once I had code that could do arbitrary d, I wondered about finding primes that could do many d simultaneously. For example, what is the first prime that can be written as two times a square plus a square, three times a square plus a square, all the way up to 10 times a square plus square? The answer, which you can get if you execute the code in the link to the Groovy Console below, is 1009. Note that this prime is not as large as you might think it should be. In researching this general problem, I found some other interesting behaviors, which I will describe in blog articles following this one.

The Groovy code for the arbitrary and many simultaneous d can be found at the Gist Arbitrarily split primes into a multiple of a square plus a square. A preloaded and executable version can be found at Groovy Web Console. When executed it may take time for the code to be compiled. Results for simpler cases usually return in under 10 seconds. And as described in earlier blog articles, the Result tab is where you can find the primes and their decompositions. If you are truly interested in reading and understanding the code, you should probably start with prior iterations in the earlier blog articles. 

When doing larger d, one issue immediately comes up. The solutions you produce are for multiples of the prime, not just for the prime itself. As an example, if you examine the case of d = 5, the prime 7 cannot be written a 5 times a square plus a square. Instead it is 14 = 2·7 that can be written as one squared times 5 plus three squared. I deal with that by filtering out primes that have such solutions and only keeping the ones where p = d·a² + b² with no multiple of p. But the code has a flag where this filtering can be turned off.

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. ...