This file describes some of the available gists for sampwhite and links to them. It is not complete and it may at times be out of date. But if you follow the various links available and do a bit of searching, you should be able to find material about all the author's gists. The gists in this space are a companion to the blog Gyassa Blog. We start with a motivating question.
What is the largest N such that every positive integer that has no common factor with N has a square that has remainder 1 mod N? As a reminder, the "square" of a number is multiplying the number against itself, and the "remainder mod N" is the remainder after dividing by N. The answer can be found at Largest All Order 2 Elements in Group Mod N.
These are links to files relevant to algorithms and outcomes for splitting a prime into a square plus an integer times a square. These algorithms and results were derived without reading textbooks, but instead derived from the author's old memories of mathematics from over three decades ago.
- Primes to Many Squares - This Groovy script, which
can be executed at Groovy Web Console for Primes to Many Squares, will look for primes that split simultaneously into a square plus an integer
dtimes a square for manyd. The blog ariticle discussing this script can be found at Many Cases of Primes From Squares. - Thousand Digit Prime 1 MOD 24. First prime congruent
to
1 mod 24greater than 10^1000 (one followed by 1000 zeroes) split up into various squares plus a square timesdfordequals two, three, four, and six.
In particular, the book the author read is A Course In Computational Algebraic Number Theory by Henri Cohen. In there it presents a general approach for computing class groups of imaginary quadratic fields.
In the following we assume we have added the square root of -D for any positive integer D to the integers. This produces an integral number ring, although it may not be the maximal integral ring inside the rationals when the square root of -D is added. The general idea is that for primes where -D is a square mod p, p splits into the product of two ideals in the integer number ring, or two ideals that are above the prime p. The ones that map to the identity element in the class group are primes that can be written as a square plus a D times a square.
The amazing fact is that if you take a general square free positive integer N and split it into its prime factors, then N can be split into a square plus D times a square if and only if -D is a square mod p for every prime and there is an Ideal above each of the primes so that when the ideals are multiplied together in the class group, you get the identity element in the class group. This gives you, for any D, an efficient way to determine if a particular N can be written as a square plus D times a square, assuming factoring N into primes is not computationally infeasible.
At PrimesToSquaresClassGroup.groovy you can find an updated implementation of the code for splitting primes into a square plus D times a square and see Class Group Splitting Primes Groovy Console for a ready to execute version. In particular, this updated code computes class groups. In this new implementation, for primes (or powers of a prime) that split in the integer number field containing the square root of -D, we can choose a particular ideal, based on which ideal, if there are two, has the larger real coordinate. This allows specific elements of the class group to be associated one to one with primes. And by walking through primes less than the square root of -D divided by 3, you can find all the generators for the class group this way. Or to put it another way, any class group element can be uniquely represented as a number generated by taking the power of each prime used to construct the class group element. In our results, we present that mapping of a prime to that particularly chosen class group element. What this gives us, for primes where -D is a square mod p, a mapping from any of those primes to a unique representative integer bound to a specific element in the class group. This mapping is a homomorphism under multiplication when extending the map to multiplying the primes.
There is one subtly that the author wishes to call out. When generating the class group using representative ideals from splitting primes, any prime after the first will have a relative order to the sub group constructed before. An element's relative order to an existing sub group is the smallest power of that element which puts it into the sub-group. So for example, 2 might map to an element of order 4, but 3 might map to an element whose square is 2 cubed. In the output for the generators of the class group, you will see the relative order for the prime and what sub-group element it goes to once it reaches the relative order. It is possible to create a new generator basis for the class group where every generator's relative order is the same as its order, but then we would not be able to represent the generators one to one with primes.
I will not give a link for Idoneal Numbers, but a google search will likely find the same information that I have found. In general, the idea is this. If adding the square root of -D creates a ring with a class group G, there are facts you can deduce about how primes breakdown based on the properties of G. If an element has order N, then that implies you can create a polynomial of degree N that has the property that if it splits completely mod a prime and -D is a square mod that prime, then when that prime is split and lifted into the class group, it will have eliminated that group element from its representation in G. In particular, if the element generates all of G, then the prime will be principal and p can be written as a square plus a square. As an example, consider the prime 11. It has a class group of order 3. If the polynomial x^3 - x^2 - x - 1 splits completely mod p and -11 is a square mod p, then p can be written as a square plus 11 times a square. The production of this polynomial and a proof that it works is currently beyond the book knowledge I have recently (re)acquired. See Representation of primes by the principal form of discriminant -D when the class number h(-D) is 3.
The problem is this, for polynomials of degree greater than two, there is no simple criteria for determining whether the polynomial splits. But that is not true for polynomials of degree 2. Whether that polynomial splits is governed completely by the value of p mod 4D (four times D). See Primes of form x^2 + ny^2 and congruences. Such polynomials allow a simple congruence criteria to be used to determine whether they split. In particular, this means that if the class group has elements only of order two (or one), then whether p can be written square plus D times a square is determined by the value it has mod 4D (or sometimes a factor of 4D). Such D are the Idoneal numbers. It turns out that there is a finite list of such numbers, and the current list is expected to be complete, but is only proven to be complete if the Riemann Hypothesis extended to number fields is true.
In the gist PrimesToSquaresClassGroup.groovy referred to in the previous section, you will see a list of all the Idoneal numbers and the modulo 4D criteria for when p can be written as a square plus D times a square. As an example, a prime number can only be written as a square plus 22 times a square if modulo 88, it is one of 1, 9, 15, 23, 25, 31, 47, 49, 71, or 81
Since there is a simple congruence relation to determine if a prime can be expressed as *x2 + D·y2 for D an Idoneal number, it is possible to find primes that can be expressed by such a breakdown into squares for multiple Idoneal numbers. In fact it is possible to find a prime that satisfies the expression for all Idoneal numbers. We used the code referenced in the prior section to do this. See First prime expressed as x^2 + d·y^2 for Idoneal d for the result.