On this page
When you need to find the number of pairs with a sum divisible by 3 from a large set of numbers, checking every pair by brute force takes too much time. As explained in array algorithms on GeeksforGeeks, comparing all pairs directly scales as O(N²): for 100 numbers, you must test 4,950 pairs, and for 100,000 numbers, nearly 5 billion pairs.
Grouping numbers by their remainder modulo 3 reduces the time complexity to O(N). Here is exactly how the method works.
Why do the remainders matter?
Every integer leaves a remainder of 0, 1 or 2 when divided by 3. When you add two integers, the remainder of their sum equals the sum of their individual remainders, a core property of modular divisibility patterns.
To make the final sum divisible by 3 (remainder 0), there are only two valid remainder combinations:
Add 0 and 0: Both numbers are multiples of 3 (for example, 6 + 9 = 15).
Add 1 and 2: One number leaves remainder 1 and the other leaves remainder 2, summing to 3, which is 0 modulo 3 (for example, 4 + 5 = 9).
No other pairing works: 1 + 1 leaves remainder 2, and 2 + 2 leaves remainder 1.
How do you count pairs with a sum divisible by 3?
Once you establish the remainder rule, counting valid pairs becomes an exercise in selection rules in combinations.
First, partition your numbers into three remainder groups:
Group 0 (n₀): Multiples of 3 (3, 6, 9, 12...).
Group 1 (n₁): Numbers leaving remainder 1 (1, 4, 7, 10...).
Group 2 (n₂): Numbers leaving remainder 2 (2, 5, 8, 11...).
For Group 0, any two numbers combine to form a valid sum. Choosing 2 numbers out of n₀ yields n₀C₂ pairs, or n₀ × (n₀ − 1) / 2.
For Group 1 and Group 2, each number in Group 1 pairs with every number in Group 2, producing n₁ × n₂ cross pairs.
Adding these disjoint counts gives the total: Total Pairs = [n₀ × (n₀ − 1) / 2] + [n₁ × n₂]
How many pairs with a sum divisible by 3 are there from 1 to 100?
Let us apply this formula to the integers 1 to 100. Evaluating the combination formula C(n, 2) = n(n − 1) / 2 from Wolfram MathWorld across each remainder subset gives us the exact count.
First, count the elements in each group:
Group 0: Multiples of 3 up to 99, giving 33 numbers (n₀ = 33).
Group 1: Sequence 1, 4... up to 100, giving 34 numbers (n₁ = 34).
Group 2: Sequence 2, 5... up to 98, giving 33 numbers (n₂ = 33).
Now calculate each component:
Valid pairs from Group 0: 33 × 32 / 2 = 528 pairs.
Valid pairs from Groups 1 and 2: 34 × 33 = 1,122 pairs.
Total valid pairs: 528 + 1,122 = 1,650 pairs.
Because each pair comes from disjoint sets, this method is an effective way of preventing double counting in combinations. Out of 4,950 total pairs, exactly 1,650 pairs (one-third) sum to a multiple of 3.
When working through discrete mathematics problems, spotting the underlying pattern is always better than trying to memorise a shortcut formula. The Fermi Problem Library features worked problems with a step-by-step solver that explains the reasoning rather than printing an answer. When working through multi-step modular arithmetic, Fermi's AI tutor holds a line of reasoning across a whole session and writes on a board as it goes, so you sit down to a clear next step.
What if the divisor is larger than 3?
The same remainder logic generalises to any divisor K by partitioning numbers into K buckets (0 to K − 1). Group 0 still pairs with itself, contributing n₀C₂ pairs. All other buckets pair complementary remainders that sum to K (Group i with Group K − i), contributing n_i × n_{K−i} pairs. If K is even, the middle bucket at K / 2 also pairs with itself, contributing n_{K/2}C₂ pairs.
