Brier Numbers

A Sierpinski number is an odd number k such that k.2ⁿ +1 is not prime for any n > 0.

A Riesel number is an odd number k such that k.2ⁿ - 1 is not prime for any n > 0.

A Brier number is an odd number k that is simultaneously a Sierpinski number and a Riesel number.

A covering set is a set of primes P such that if e_i is the order of p_i Î P, and m = lcm{e_i}, then it is possible to arrange a set of congruences r_i mod e_i such that every position from 0 to m- 1 (or 1 to m) is covered by at least one of these congruences. Congruences of this type are known as Nash congruences, and a particular arrangement of Nash congruences that covers each position is known as a covering pattern. The value m is known as the modulus of the covering set. An additional point to note is that a covering set is minimal in the sense that the property no longer holds if any of the primes is removed.

Since the set of primes dividing the number 2^m - 1 is the set of all primes with exponent dividing m, covering sets with modulus m are necessarily subsets of this set.

Every Sierpinski number is associated with a particular covering set P of primes, that is, every value of k*2ⁿ +1 is divisible by at least one of the primes in P, where the positions mentioned above are simply the values of n mod m. It is possible to generate a Sierpinski number from a specific covering pattern by generating a list of congruences of the form k º - 2^r mod p for each p in P, where r mod p is the Nash congruence pertaining to p in the covering pattern. Let us also use P to represent the product of the primes in P. This set of congruences always has an odd solution less than 2P, and which can be obtained quickly and easily.

Analogously, the same is true of Riesel numbers, with the only difference being that given a Nash congruence r mod p, we have k º 2^r mod p. These congruences involving k are known as Sierpinski or Riesel congruences, as appropriate.

In trying to locate Brier numbers, we therefore require to find two separate covering sets P and Q such that for any prime p Î P Ç Q, the Sierpinski congruence and the Riesel congruence coincide. If this is the case, a different Brier number may be obtained from every different combination of covering patterns that exists. It is appropriate to obtain firstly a set of Nash congruences for k as a Sierpinski number, convert these to Sierpinski congruences, and for each overlapping prime, consider the Sierpinski congruence as a Riesel congruence and produce the associated Nash congruence. Once these are in place, we can then locate the remaining Nash congruences for k as a Riesel number.

Fortunately, the prime 3 can be used in both sets, eliminating even values of n in one case and odd values in the other one, otherwise the sizes of solutions would be huge. So let us suppose that 3 is in both sets. What other restrictions can be placed on overlapping primes ?

Given a prime p, with order e modulo 2, we require the Nash congruence with respect to p to convert to a Sierpinski congruence that then converts back to a Nash congruence with respect to Q, and such that the two Nash congruences switch signs, otherwise p will have no effect since one or other of P and Q has prime 3 with matching sign. Thus the congruence chain from (r mod e) to - 2^r mod p to 2^s mod p to (s mod e) must be such that r ¹ s mod 2 and such that - 2^r º 2^s mod p. Since r- s is odd and 2^{r- s} º - 1 mod p, we have e = 2(r- s), and so the order of p must be twice an odd number. This substantially restricts the available primes. In particular, 5 and 7 are excluded and so can occur in one or other of P and Q, but not both. Primes that can overlap include 11 and 19.

This first example was provided by Eric Brier. He obtained two covering sets using a particular technique in order to keep the combined products as small as possible. The two covering sets are

{3, 5, 17, 257, 65537, 97, 673, 193} of modulus 96

and

{1153, 6337, 577, 433, 38737, 241, 13, 37, 109, 73, 19, 7, 3} of modulus 288

Brier generated every possible covering pattern and calculated the associated value of k for each of the 13824 possible combinations. The smallest of all these values is

29364695660123543278115025405114452910889

This has 41 digits and its discovery was announced on 28^th September, 1998. This remained the smallest known Brier number until Yves Gallot announced the discovery of a 30 digit Brier number on 15^th January, 2000. This number is

623506356601958507977841221247

The relevant covering sets are

{3, 7, 73, 13, 19, 241, 37, 109, 97, 673} with modulus 144

and

{3, 5, 17, 257, 65537, 641, 6700417} with modulus 64

This was closely followed by the smaller solution the next day

3872639446526560168555701047

of 28 digits and covering sets

{3, 7, 73, 13, 19, 241, 37, 109, 97, 673} with modulus 144

and

{3, 5, 31, 17, 11, 151, 41, 331, 61681, 61} with modulus 120

Another solution, this time of 27 digits, followed a day later

878503122374924101526292469

with covering sets

{3, 7, 73, 13, 257, 19, 241, 37, 109, 97} with modulus 144

and

{3, 5, 31, 17, 11, 151, 41, 331, 61681, 61} with modulus 120

As with the case for Sierpinski numbers or Riesel numbers separately, an odd solution for k will always be found that is less than 2*P*Q/R where R represents the set P Ç Q and its product. Gallot proceeded by generating all covering sets for each consecutive possible modulus and comparing them to find pairs whose only intersection is the prime 3. Ultimately, the combined product 2PQ/3 becomes so large that the chance of finding a relatively small solution, in comparison to those already discovered, becomes poorer and poorer. The obvious step is to consider expanding R to include additional primes so that the combined product is reduced.