Technique

Enumerate a residue class within a bound

Arithmetic • Number System • Divisibility

Statement

The integers leaving remainder

r

on division by

m

are exactly those of the form

mk + r

, so they form an arithmetic progression of common difference

m

; to find all of them in a range, list

r, m + r, 2 m + r, \dots

as far as the range allows and then test each listed value against the problem's remaining conditions.

How to use it

1Bound the search first: the largest value that can possibly occur turns an open-ended condition into a finite list.
2When the quantity is a product $ab$ , list the admissible products and factorise each one, rather than testing every pair - the list is far shorter than the grid.
3Read the inequalities exactly: a condition such as $ab > 12$ is usually there to remove the smallest member of the progression.

List the positive integers below

60

that leave remainder

3

on division by

7

Step-by-step

1
$n = 7 k + 3$
Why: This is what 'remainder $3$ on division by $7$ ' means.
2
$k = 0, 1, \dots, 8 \Rightarrow n = 3, 10, 17, 24, 31, 38, 45, 52, 59$
Why: Stop at the last value below $60$ .

Answer

3, 10, 17, 24, 31, 38, 45, 52, 59

Watch out

A remainder must satisfy

0 \leq r < m

; anything stated as a 'remainder' of

m

or more has not been reduced. The progression continues below zero under the usual convention, so

- 4

also leaves remainder

3

on division by

7

Also known as

numbers of the form 12k+4, residue class, remainder when divided by, arithmetic progression of remainders, enumerate under a modular condition