Covering system

In mathematics, a covering system (also called a complete residue system) is a special way to describe all the whole numbers. It uses a collection of groups of numbers, called residue classes, to make sure every integer is included. Each residue class is written as aᵢ (mod nᵢ), which means a set of numbers that share the same remainder when divided by nᵢ.

For example, a residue class like 2 (mod 5) includes numbers such as 2, 7, 12, and so on — all numbers that leave a remainder of 2 when divided by 5. When several of these classes are put together, they can cover every integer without missing any.

Covering systems are important in number theory and help mathematicians solve problems about divisibility, patterns in numbers, and how numbers relate to each other. They show how different sets of remainders can work together to describe the entire number line.

Examples and definitions

The idea of a covering system was first talked about by Paul Erdős in the early 1930s.

A covering system is a special collection of numbers that can represent every integer. For example:

• The numbers 0, 1, and 2 when looking at remainders after dividing by 3 cover all integers.
• The numbers 1 (when dividing by 2), 2 (when dividing by 4), 4 (when dividing by 8), and 0 (when dividing by 8) also cover all integers.

These systems can have different properties. Some covering systems don’t overlap, meaning no two numbers in the system represent the same integer. Others have all different divisors, like the third example above. Mathematicians study these systems to understand how numbers can fit together perfectly.

Mirsky–Newman theorem

The Mirsky–Newman theorem is an important idea in mathematics. It says that there cannot be a special kind of covering system where the parts do not overlap. This idea was guessed to be true in 1950 by Paul Erdős. Later, it was shown to be true by Leon Mirsky and Donald J. Newman, though they did not write it down. Others, like Harold Davenport and Richard Rado, found the same answer on their own.

Main article: Herzog–Schönheim conjecture

Primefree sequences

Covering systems help us create special sequences of numbers. These sequences follow the same pattern as Fibonacci numbers, but every number in the sequence is a composite number, meaning it can be divided by numbers other than one and itself.

For example, a sequence discovered by Herbert Wilf starts with the numbers 20615674205555510 and 3794765361567513. In this sequence, the positions where numbers can be divided by a certain prime number form a pattern. These patterns together make a covering system, ensuring that every number in the sequence has at least one prime divisor.

Boundedness of the smallest modulus

Mathematician Paul Erdős wondered if we could find special number patterns where the smallest number used could be made as large as we want. He and others found examples where the smallest number was 2, 3, 4, 20, 40, and even 42.

Later, Bob Hough showed that there is a limit to how large that smallest number can be, using a clever mathematical idea called the Lovász local lemma.

Systems of odd moduli

Mathematicians are still trying to answer an important question: can we create a special kind of number system called a covering system using only odd numbers as the rules? This question was proposed by famous mathematicians Erdős and Selfridge. While we don’t know the answer yet, we do know that if such a system exists and uses certain simple odd numbers, it would need to involve at least 22 different prime numbers.