Numeri Idonei

Euler found sixty-five integers, which he called "numeri idonei",
that could be used to prove the primality of certain numbers.  The 
four papers that Euler presented to the Petersberg Academy in 1778 on
this subject were, according to Andre Weil, "so ill coordinated with 
one another, and some of the formulations and proofs in them are so 
confused and defective, that one is tempted to attribute them to a 
variety of assistants over whom Euler was not keeping close control".  

The typical definition of these numbers that one finds in the 
literature, such as in Scharlau and Opolka's "From Fermat to Minkowski",
Joe Robert's "Lure of the Integers" (p.266), or Dickson's "History of 
the Theory of Numbers", is that m is a numerus idoneus if every odd 
integer q that has exactly one representation of the form  x^2 + m y^2  
(with x,y corpime) is a prime.  Actually, Scharlau and Opolka elaborate
on this a bit, and say (p.30) that the numeri idonei have the following
property: 

  "If ab=m and if a number can be uniquely written in the form 
   ax^2 + by^2  with ax,by relatively prime, then this number is 
   of the form p, 2p, or 2^k  where p is a prime; specifically, 
   any odd number that can be written uniquely in this way is a 
   prime."

This seems to have come directly out of Dickson (Vol 1, p361).
Most references don't give the complete list of these numbers. Instead,
they usually just say that Euler found 65 of them, the largest of which
is 1848, and thirty-seven of them are square-free.  S. Chowla proved 
(in 1934) that the number of numeri idonei is finite, and it is known 
that there can be at most ONE more square-free numerus idoneus beyond 
those found by Euler.  Whether such another number exists is still 
an open question.

The sixty-five known idoneal numbers are

      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 1848

It might appear that there is a problem with the commonly quoted
definition of these numbers, according to which the only odd numbers
expressible in exactly one way in the form  x^2 + 2y^2  (with x and 
y coprime) must be primes.  The "problem" is illustrated by prime 
powers like  9 = (1)^2 + 2(2)^2, which has only this one single 
representation given the constraint that x and y are coprime.

Andre Weil, in his book "Number Theory from Hammurapi to Legendre" 
(p.225) gives a more subtle definition that seem to be closer to the 
truth when he says that "N, if square-free, is idoneus if and only if
every prime divisor p of X^2 + NY^2, prime to 2N, is such that either
p or 2p (or both) can be expressed as ux^2 + vy^2 with uv=N."  This 
definition is consistent with the fact that 9 has exactly one 
representation of the form x^2 + 2y^2, because the prime divisors of 
9 are 3 = (1)^2 + 2(1)^2.  Also, for the number N=5 we find that 49 
is expressible in just one way in the form x^2 + 5y^2, and although 
7 is not so expressible, 2*7=14 is expressible as (3)^2 + 5(1)^2.  
All this supports Weil's version of the definition.

However, the more common definitions are also correct IF we apply the
stated conditions sequentially, i.e., we should say

  The number m is a numerus idoneus if a sufficient condition
  for primality of an odd integer q is that q has exactly one 
  representation of the form  x^2 + m y^2 and in that single 
  representation x is co-prime to my.

Another equivalent definition is that if k is an odd number 
expressible in exactly one way in the form x^2 + Ny^2 for some 
numerus idoneus N, then k is a prime power.  This seems more 
restrictive than Weil's definition, since he would allow k to be 
a product of distinct expressible primes.  On the other hand, this 
condition also seems to be sufficient, i.e., if every odd uniquely 
N-expressible number is a prime power, then N is idoneal, so we 
don't need to refer to the expressibility of 2p in order to 
determine the idoneal values of N.

By the way, it's interesting to note the relation between the 
integers n such that the complex quadratic field k(sqrt(-n))
is "simple" (i.e., unique factorization holds) and the set of 
numbers that have a unique representation in the form  x^2 + ny^2 
for coprime integers x,y.  The only simple complex quadratic 
fields are those with n = 1, 2, 3, 7, 11, 19, 43, 67, or 163.

For example, consider the case n=163.  Every odd number less 
than 1750 that is expressible in exactly one way in the form  
x^2 + 163 y^2  is a prime, so we might be tempted to think that 
163 is a "numerus idoneus".  However, the number 1763 = 41*43 is 
uniquely expressible (and neither 41 nor 43 are expressible in 
this form, nor are their doubles).  Continuing on, it appears 
that every uniquely expressible odd number with n=163 must 
either be a prime power OR a product of two or more of the 
non- expressible primes

     41, 43, 47, 53, 61, 71, 83, 97, 113, ...

This is clearly related to Euler's famous "prime producing" 
polynomial f(x) = x^2 + x + 41, since the above primes are 
evidently f(k) for k = 0,1,2,3,...  The discriminant of this
of course -163.

Similarly, with n=67 we find that every uniquely expressible odd
number less than 320 is a prime, but beginning with 323=17*19 we
find uniquely expressible odd numbers composed of two or more of
the prime factors 17, 19, 23, 29, 37,...   These values are
evidently those given by the polynomial f(x) = x^2 + x + 17
for x=0,1,2,3,..., and the discriminant of this polynomial 
is -67.

This same type of behavior also applies to n=43, for which the 
uniquely representable numbers are all primes until reaching 
143=11*13, and thereafter the non-prime powers are all products 
of two or more of 11, 13, 17, 23, 31,...  Similar behavior is 
shown by n=19, although for n=11 (the smallest number that is 
NOT a "numerus idoneus") the pattern of unsuitable numbers seems 
to be somewhat scrambled.

Then we reach n=7 (as well as n=3, 2, and 1), for which the 
only uniquely expressible odd numbers are prime powers.  It's 
interesting that the boundary seems to be around n=11, which is 
the largest value of n such that the complex quadratic field 
k(sqrt(-n)) is Euclidean, i.e., possessing a Euclidean algorithm.