Number System

What is a remainder?

When you share 47 sweets among 5 children equally, each gets 9 and 2 are left over. Here 47 is the dividend, 5 the divisor, 9 the quotient and 2 the remainder. The remainder is always smaller than the divisor.

The division formula

$\text{Dividend} = \text{Divisor} \times \text{Quotient} + \text{Remainder}$ $47 = 5 \times 9 + 2$. Almost every "find the dividend / divisor" question is just this formula. Example: divisor 24, quotient 13, remainder 17 → dividend $= 24 \times 13 + 17 = 329$.

Rule 1: divisor-multiple rule

If $N$ leaves remainder $r$ when divided by $D$, and $d$ is a factor of $D$, then $N$ leaves $r \bmod d$ when divided by $d$. Example: $N \div 342$ leaves 47. Since $342 = 18 \times 19$, $N \div 18$ leaves $47 \bmod 18 = 11$. If $d$ is not a factor of $D$, the remainder cannot be fixed.

Rule 2: remainders of sums and products

The remainder of a sum (or product) = remainder of the sum (or product) of the individual remainders. Example: $(1021 \times 1023 \times 1025) \div 17$: remainders 1, 3, 5 → $1 \times 3 \times 5 = 15$ → remainder 15. This lets you replace huge numbers by tiny ones before multiplying.

Rule 3: negative remainders

A remainder can be written as a negative number to keep things small. $67 \div 68$ leaves 67, which is the same as $-1$. So $67^{67} \div 68$ leaves $(-1)^{67} = -1$, i.e. $68 - 1 = 67$. If your final answer is negative, add the divisor.

Rule 4: large powers

Look for a small power that gives remainder $1$ or $-1$.

• $2^3 = 8$ leaves 1 with 7, so $2^{100} = (2^3)^{33} \times 2$ leaves $1 \times 2 = 2$.
• $5^2 = 25$ leaves $-1$ with 13, so $5^4$ leaves 1.
• Base one more than divisor: $(d+1)^n \div d$ always leaves 1.
• Base one less than divisor: $(d-1)^n \div d$ leaves 1 if $n$ is even, $d - 1$ if $n$ is odd.
• Fermat's rule: if $p$ is prime and does not divide $a$, then $a^{p-1}$ leaves 1 with $p$.

Rule 5: remainder of $kN$, $N^2$, $N^3$

If $N \div d$ leaves $r$, then $kN$ leaves $kr \bmod d$ and $N^2$ leaves $r^2 \bmod d$. Just work with $r$.

Rule 6: successive division

"Divided successively by 3 and 5 leaves remainders 2 and 3" means: divide $N$ by 3 (remainder 2), then divide that quotient by 5 (remainder 3). Work backwards from the last step: start with the smallest quotient 0 (or 1 if asked), and rebuild: $x = \text{divisor} \times \text{next} + \text{remainder}$.

Rule 7: sum of factorials

From $4! = 24$ onwards every factorial is a multiple of 12, and from $5!$ onwards a multiple of 10 and 120. So for $1! + 2! + \dots + 100!$ divided by 12, only $1! + 2! + 3! = 9$ matters.

Quick revision

• Dividend = divisor × quotient + remainder; remainder < divisor.
• New divisor is a factor of the old → answer = old remainder mod new divisor.
• Reduce each number first, then add/multiply the remainders.
• Use $\pm 1$ remainders for big powers; add the divisor to a negative answer.
• $(d+1)^n \to 1$; $(d-1)^n \to 1$ or $d-1$.
• Successive division: rebuild from the last divisor backwards.