Theorem
is a multiple of when
Algebra • Permutations and Combinations
Formula
For whole numbers , , so is a multiple of and of every factor of .
How to use it
- 1Why it works: is the product , and its first factors already make .
- 2For the remainder of a sum of factorials on division by : find the smallest with a multiple of . Every term from on leaves remainder , so only the terms before it matter.
- 3For : , so only
can leave a remainder.
Worked example
Find the remainder when is divided by .
Step-by-step
- 1, so
are all multiples of . Why: Each of them contains as a factor.
- 2
Why: Only the terms before can leave a remainder.
- 3, so the remainder is .
Answer
Watch out
The remainder of the early terms' sum must itself be reduced if it is larger than the divisor: leaves on division by , not .