Technique

Remainders all short of their divisors by the same amount

Arithmetic • Number System • LCM and HCF

Statement

N

leaves remainder

d_{i} - c

on division by each of

d_{1}, d_{2}, \dots, d_{k}

for one fixed

c

with

0 < c \leq min d_{i}

, then

N + c

is divisible by every

d_{i}

, so

N = m LCM (d_{1}, \dots, d_{k}) - c

for some positive integer

m

How to use it

1Subtract each remainder from its divisor first; the technique applies only when every difference is the same number $c$ .
2Compute the LCM of all the divisors at once — not pairwise products — and the solutions are then spaced exactly one LCM apart.
3The smallest positive member is $LCM - c$ , which makes counting the members in a given range immediate.

Worked example

Find the least positive integer that leaves remainders

5, 7

and

9

on division by

7, 9

and

11

respectively.

Step-by-step

1
$7 - 5 = 9 - 7 = 11 - 9 = 2$
Why: Every remainder is short of its divisor by the same $c = 2$ .
2
$N + 2 is divisible by 7, 9, 11 \Rightarrow LCM (7, 9, 11) = 693$
Why: The shifted number must be a common multiple of all three divisors.
3
$N = 693 - 2 = 691$

Answer

691

Watch out

The deficits must all be equal. When they differ the congruences still have a solution (if consistent), but it must be found by the Chinese remainder construction, not by a single shift.

Builds on

Prime factorisation

Also known as

common deficit remainder, remainder one less than the divisor, N+1 divisible by all, LCM minus one, n congruent to -1

Remainders all short of their divisors by the same amount

Statement

Worked example

Appears in past papers

2016 (II)