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