The Rogers theorem on excluding congruence classes is an elementary result of C. A. Rogers in number theory from the 1960s, that for many years had the status of a folk theorem not well documented in published literature. After more than half a century, its value as a principle in contemporary sieve theory received recognition.
Background Arithmetic progressions of integers are sets of the form a + nd where n is any integer, and a (the offset) and d (the difference) are fixed. They can be intersected: the result may be empty, for example even numbers and odd numbers are disjoint. Otherwise, if two progressions have a number in common, there will be an arithmetic progression in common, with a difference that is the least common multiple (lcm) m of the differences in the two progressions. That means that the intersection can be read as a question on integers modulo m. The intersection of n progressions with differences d1, d2, ..., dn is easiest to understand when the lcm m of the di is their product, or equivalently di and dj have no common factor when i≠j. In that case the Chinese remainder theorem implies that congruences modulo m are the same as simultaneous congruences modulo all the di: the residue numeral system principle. The intersection will be a single progression with difference m.
Sieving The interest in sieve theory is in simultaneously excluding congruence classes for a number of moduli di. In Boolean algebra terms, one intersects a number of sets of congruence classes defined by complementation. The underlying problem is to understand cases when the Chinese remainder theorem does not apply, because the di are not coprime in pairs. The use of disjunctive normal form is a standard technique for Boolean manipulations. It here allows one to see that the result, at the progression level, is the union of a number of progressions, those resulting from non-empty intersections. These correspond to "surviving" (non-sieved) residue classes modulo m, and there arises the question of how many there might be.
Case when d2 divides d1 A simple situation occurs when d2 divides d1, because then the residue class modulo d1 determines the residue class modulo d2. The progressions P(1) given by r + kd1 and P(2) given by s + ld2 will have a non-empty intersection if and only if
r ≡ s modulo d2 and then the condition modulo d2 is always satisfied. In other words, the intersection is P(1). The smallest example not covered in this way, for the prime factors 2 and 3, is with d1 = 12, and d2 = 18. A numerical example is given by Das.
Statement of the theorem The result of Rogers states that number of surviving residue classes is bounded above by the number when the congruence conditions are t ≡ 0 modulo di for all i. In other words, when the "simple situation" cannot exclude anything because 0 ≡ 0 is automatic, the surviving classes are at a maximum. It is possible to count those classes, in the special case. In fact the system of congruences is then equivalent to a system where the di are replaced by the powers of primes in the prime factorisation of the lcm m; and in this case the Chinese remainder theorem applies. The original statement by Rogers, as modified by Heini Halberstam and Klaus Roth in their 1966 book Sequences, concerned minimising the natural density of the union of sets of progressions, when the offsets are varied. The minimum is attained for the offsets all set to 0. This approach looks at the complemented situation: the minimum union corresponds to the maximum non-sieved set.
Notes
External links "Rogers' theorem on sieving". terrytao.wordpress.com. 19 January 2026.
