For a positive integer n, consider 1, 2, …, 5n. (a) Show that each remainder modulo 5 occurs n times. (b) Count the unordered pairs of distinct numbers whose sum is divisible by 5. (c) Evaluate your formula for n = 4.
1 · Understand & choose a strategy
What are we finding?
There are three connected tasks: prove that each remainder on division by 5 occurs n times among 1 through 5n; count distinct unordered pairs summing to a multiple of 5; then use n = 4. “Distinct” forbids using the same number twice, and “unordered” means {a,b} and {b,a} are one pair.
Why this approach?
Organize numbers by remainder rather than by their size. A sum is divisible by 5 exactly when its two remainders add to a multiple of 5. Prove the class sizes first, identify every legal class pairing, then count disjoint cases.
Pause and think
Why does choosing two numbers from the same class require a different formula from choosing one number from each of two different classes?
2 · Need a hint? Reveal one at a time
Try the first hint, then return to your own work. Open the next hint only if you need more help.
Hint 1 · Where to start
Every block 5k + 1, 5k + 2, 5k + 3, 5k + 4, 5k + 5 has remainders 1, 2, 3, 4, 0. Use k = 0 through n − 1.
Hint 2 · Build the setup
The unordered remainder pairs are (0,0), (1,4), and (2,3). For (0,0), exclude using a number twice and then correct for reversed order.
3 · Follow the worked solution & check
Work through the reasoning
All possible unordered remainder cases| Remainders | How to choose | Number of pairs |
|---|
| 0 and 0 | Two distinct members of one class | n(n − 1)/2 |
|---|
| 1 and 4 | One from each class | n × n |
|---|
| 2 and 3 | One from each class | n × n |
|---|
- Part (a): partition into blocks.
Use n blocks: 1–5, 6–10, …, (5n − 4)–5n. Each block has exactly one number of each remainder 0, 1, 2, 3, 4. Since the blocks cover the range without overlap, each class has n members.
- Part (b): prove which remainder pairs work.
Write a = 5q + r and b = 5t + s with 0 ≤ r,s ≤ 4. Then a + b = 5(q + t) + (r + s), so only r + s matters. It can be a multiple of 5 only by being 0 or 5. Ignoring order gives (0,0), (1,4), and (2,3).
- Count two remainder-zero numbers.
Choose the first from n numbers and the second from n − 1 different numbers. This gives n(n − 1) ordered choices. Each unordered pair appears twice, so this case contributes n(n − 1)/2.
- Count the two cross-class cases.
For (1,4), each of n remainder-1 numbers pairs with each of n remainder-4 numbers: n² pairs. No division by 2 is needed because the class roles identify each choice uniquely. The (2,3) case similarly contributes n².
- Add disjoint, complete cases.
Every valid pair belongs to exactly one of the three cases. The total is n(n − 1)/2 + n² + n² = (n² − n + 4n²)/2 = (5n² − n)/2.
- Part (c): specialize the formula.
For n = 4, the total is (5 × 4² − 4)/2 = (80 − 4)/2 = 38. The individual contributions are 6, 16, and 16.
Answer: (a) n per class; (b) (5n² − n)/2; (c) 38
Check the result
Test n = 1: among 1,2,3,4,5, the only valid pairs are {1,4} and {2,3}. The formula gives (5 − 1)/2 = 2. The lone multiple of 5 cannot pair with itself, matching the zero contribution from n(n − 1)/2.
Common mistake to avoid
Using n² for (0,0) permits self-pairs and counts reversed pairs twice. Adding both (1,4) and (4,1) also double-counts. Dividing the entire total by 2 would incorrectly halve the cross-class counts.
Use this on a similar problem
A complete counting proof explains three things: every counted object is valid, every valid object is included, and no object is counted twice. Residue classes turn a divisibility condition into a small case table.
