The numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 15, 16, 18, 21, 22, 24, 25, 28, 30, 33, 37, 40, 42, 45, 48, 57, 58, 60, 70, 72, 78, 85, 88, 93, 102, 105, 112, 120, 130, 133, 165, 168, 177, 190, 210, 232, 240, 253, 273, 280, 312, 330, 345, 357, 385, 408, 462, 520, 760, 840, 1320, 1365, and 1848 are called Idoneal numbers. If you do a google search on “Idoneal Numbers” you will find many useful links, so I will not put any links defining Idoneal numbers here. The Idoneal numbers are also called convenient numbers for the reason we will be explaining below. Also, it is mostly assumed that this is the complete list, but there is a possibility that there is one more undiscovered Idoneal number.
Our focus is on the relationship between Idoneal numbers and how primes behave when you try to split them into a square plus a square times an idoneal number. In particular we are looking at the expression
x2 + d·y2
for varying values of d.
This leads us to the following question. For a given d, is there a simple characterization of a prime p on whether p can be expressed in such an equation with x and y being positive integers? For example, when d is 5, a prime can only be expressed by such an equation if p is congruent to 1 or 9 mod 20. So to be more specific, for a specific value of d, can we determine the primes expressible by the equation by whether they satisfy a congruence relation?
The answer, which is probably not surprising at this point, is that the list of Idoneal numbers is exactly the numbers d where such a congruence relation is possible. That makes these numbers quite "convenient" when trying to predict when p can be expressed by the equation above. But there is more that we can say.
Before asking whether the equation has an exact expression for a prime p, you can ask whether you can express p if you do arithmetic mod p. This is equivalent to asking if -d is a square mod p, or what is called a quadratic residue. Or using the language of the Jacobi symbol that is used to calculate quadratic residues, it is asking if the Jacobi symbol of -d over p has the value 1. Using quadratic reciprocity it is possible to characterize whether -d is a square mod p by congruence relations of p mod 4·d or sometimes mod a number that divides 4·d. All this can be efficiently calculated by a computer, and for Idoneal numbers with pencil and paper if you are good with arithmetic. We will not go into the details here, but the start of practically any book on number theory will go through how to do such a calculation.
So we can easily characterize p for which the expression has solutions mod p. We need to be able to lift it to that characterization to the integers. Is there a general way to do this?
The answer is that d has to be an Idoneal number, as said before, and for each odd prime q that divides d, p must be a square mod q. See Primes of form x^2 + ny^2 and congruences and the statement towards the end.
This can be calculated using quadratic reciprocity. Let us look at 15 as an example. First we need -15 to be a square mod p. Using quadratic reciprocity we can show that it breaks down into two cases. The first is for p = 1 mod 4, for those p, p must be congruent to 1, 2, 4 or 8 mod 15. The second is for p = 3 mod 4 where it must be 7, 11, 13 or 14 mod 15. Also, since 3 and 5 are the two odd primes dividing 15, p must be a square mod 3 and a square mod 5. This essentially reduces us to the p = 1 mod 4 case with 2 and 8 being eliminated. Or expressing this mod 60, p must be either 1 or 4 mod 60. For the calculation done for all Idoneal numbers see Congruences for primes that can be expressed as square plus an Idoneal number times a square. This list was not actually computed using quadratic residues but by brute force using variations of the script referenced in the Readme for my recent work with primes.
There is also another characterization of an Idoneal number. If d is an Idoneal number then every square of a prime p, assuming that p does not divide and -d is a square mod p, satisfies the equation above non-trivially, i.e. with y != 0. The converse is also true. If d is not an Idoneal number, then there are many squares of primes that cannot be expressed this way even if -d is a square mod p.
Since Idoneal numbers have a simple congruence for determining whether p can satisfy the squares expression, it is possible computationally to find primes for many Idoneal numbers simultaneously. In fact, it is possible to find a prime that can be represented as a square plus an Idoneal number times a square for all the Idoneal numbers simultaneously. See First prime expressed as x^2 + d·y^2 for all Idoneal d.