This note gives a short account of how the Atlas computer of the Science Research Council at Chilton was used to study a problem in the theory of numbers and how, as a result, a new theorem - much stronger than any previously published on the subject - was discovered. The note assumes no knowledge of number theory; it is only necessary to understand the meaning of a few terms which will now be defined.
Let x, a and b be integers. By a congruence is meant a statement of the type
x ≡ a(mod b)
which means that x-a is divisible by b. Thus 19 ≡ 1(6), 27 ≡ 0(3) are congruences. In the congruence above we call b the modulus and a the residue. By a system of congruences is meant a set of statements of the above type, viz.
x ≡ a1 (mod b1 ) x ≡ a2 (mod b2 ) ... x ≡ an (mod bn )
A system of congruences may or may not have a common solution. Thus the pair
x ≡ 1 (mod 3) x ≡ 2 (mod 5)
has the solution x = 7 (also x = 22, 37, ....), whereas the pair
x ≡ 0(mod 2) x ≡ 1(mod 4)
has no solution since the first congruence implies that x is even, whereas the second implies that x is odd. Finally, a system of congruences
x ≡ a1 (mod b1 ) x ≡ a2 (mod b2 ) ... x ≡ an (mod bn )
is said to form a covering set if every integer satisfies at least one of them. For example the system of congruences
x ≡ 0 (mod 2) x ≡ 0 (mod 3) x ≡ 1 (mod 4) x ≡ 1 (mod 6) x ≡ 11 (mod 12)
form a covering set (the verification of this is left as an exercise for the reader). In this covering set all the moduli are divisors of 12 and the smallest modulus is 2. Suppose, however, that we are not allowed to use the modulus 2, can we still find a covering set? It turns out that we can and that all the moduli are divisors of 120. If we are not allowed to use the moduli 2 or 3 we can still find a covering set, the smallest apparently being based on the divisors of 720. These results suggest two problems:
Problem 1 Is it always possible to find a covering set of congruences
x ≡ ai (mod bi), i = 1, 2, ... n where k ≤ b1 < b2 < . . . < bn, for any positive integer k?
Problem 2 Is it possible to find a covering set of congruences
x ≤ ai (mod bi), i = 1, 2, ... n where all the bi are odd numbers?
Despite the elementary nature of these problems neither has been answered. The only result known is of a very simple nature and states:
Theorem 1 If the system of congruences x ≤ ai mod(bi), i=l, 2,... n forms a covering set then
In the hope of finding out something about Problem 1 I wrote a program for the S.R.C. Atlas. The program attacked the problem as follows: given two numbers N and k find all those divisors d1, d2, ..., ds of N which are ≥ k. Set up a system of congruences
x ≡ ai (mod di), i = 1, 2, ... s
and choose the ai so that as many as possible of the numbers from 1 to N satisfy at least one of the congruences. If all the numbers from 1 to N satisfy at least one congruence then we have found a covering set. In practice the program couldn't guarantee to make the best possible choice for a1, a2,.., as. To do so would require an enormous amount of computer time even for quite small N; in fact the time required would be proportional to
since s, for cases in which we are interested, is sure to be at least log N and so we see that this exhaustive approach is quite impracticable. For example, if N = 75,600, a case cited below, s = 120. The number of trials would therefore be about 10270; the strategy adopted cut this number to less than 107. It was clearly necessary to adopt some sort of strategy and the one used was to make the best choice for each ai at the time the modulus di was being examined and never later change the value of ai . In this way the running time of the program was brought down to be proportional to sN, or, say, some multiple of N log N. Even then it was necessary to program in machine code and to use each bit in the computer store to represent an integer in the range 1 to N. Thus, theoretically, the program could tackle problems in which N went as high as 48 × 49,152 = 2,359,296 - the total number of bits in the Atlas core store. In practice of course it was not possible to go quite so high since the program itself required some space.
As a result of these runs Problem 1 was solved for all k ≤ 9, the results being:
| k | N |
|---|---|
| 2 | 12 |
| 3 | 120 |
| 4 | 720 |
| 5 | 2520 |
| 6 | 10080 |
| 7 | 30240 |
| 8 | 75600 |
| 9 | 604800 |
Only the first two results were known previously.
In the course of obtaining these results many other values of N were tried and by studying the output in these cases I gradually came to the conclusion that a much stronger result than that given by Theorem 1 must be true. Let us first restate Theorem 1 in another form.
Theorem 1 (restated)
Let N = P1 n1 P2 n2 ... Pk nk and let d1, d2 ... ds be divisors of N. Then the number of distinct integers x in the interval 1 ≤ x ≤ N which satisfy at least one of the congruences x ≡ ai (mod di), i = 1, 2, ..., s is at most
Now there are, in all, divisors of N. Hence the sum referred to in the theorem involves terms when di runs through all divisors of N except unity.
The theorem discovered with the aid of Atlas can now be stated.
Theorem 2
Let N = P1 n1 P2 n2 ... Pk nk and let d1, d2 ... ds be divisors of N. Then the number of distinct integers x in the interval 1 ≤ x ≤ N which satisfy at least one of the congruences
x ≡ ai (mod di), i = 1, 2, ..., s
is at most
That this result is much stronger than the result given in Theorem 1 is seen from the fact that the double sum in Theorem 2 contains only terms of the more than terms in the previous case. For example, in the case N = 75,600 which occurs above the sum in Theorem 1 involves 112 terms, whereas the sum in Theorem 2 involves only 10.
Theorem 2 is not too difficult to prove but it is not trivial and the proof is too long to give here. The computer played no part in the finding of a proof, nor do I see how it could have done so.
I said above that I wrote a computer program to study Problem 1. It is a curious fact that the theorem discovered by means of this program has its nicest application to Problem 2. The simplest result in this direction is given by
Theorem 3
Let N = 3a 5b 7b and let d1, d2 ... ds be divisors of N. Then no set of congruences
x ≡ ai (mod di)
can form a covering set, no matter how large a, b, c might be.
Proof
By Theorem 2 the number of distinct solutions to such a set of congruences in the interval 1 ≤ x ≤ N does not exceed
This shows that some number in 1 ≤ x ≤ N does not satisfy congruence in the set and hence the system does not form a covering set.
It is possible to prove rather more. By means of a special result from the computer and an application of the theorem it can be proved that no system of congruences based on the divisors of any number of the form 3a 5b 7c 11d 13e can form a covering set. It therefore seems that if there is a set of congruences to odd moduli all of which are divisors of N and which form a covering set, then N is likely to be a very large number indeed - quite possibly well beyond the range of attack by existing computers. Thus the computer, having played its part, retires from the scene and the number theorists, better equipped than before, are left to complete the task.
