Math Core

"What is the remainder when $3^{100}$ is divided by $7$ ?" The number $3^{100}$ has $48$ digits, but you never need to compute it. Remainders follow simple arithmetic rules of their own, so you can throw away everything except the remainders and work with small numbers the whole time.

The basic rules

When you divide $n$ by $m$ , you get a quotient $q$ and a remainder $r$ with $n = qm + r$ and $0 \le r < m$ . For example, $47 = 6 \cdot 7 + 5$ , so $47$ leaves remainder $5$ when divided by $7$ .

Replace numbers by their remainders

When you add, subtract or multiply whole numbers, the remainder of the result (on division by $m$ ) depends only on the remainders of the numbers you started with. So you may replace any number by its remainder at any step.

Why it works. Say $a = 7s + 3$ and $b = 7t + 5$ . Then $a \cdot b = 49st + 35s + 21t + 15.$ Every term except $15$ is a multiple of $7$ , so $ab$ has the same remainder as $3 \cdot 5 = 15$ , namely $1$ . Sums work the same way.

Many contest writers use the notation $a \equiv b \pmod{m}$ (" $a$ is congruent to $b$ mod $m$ ") to mean $a$ and $b$ leave the same remainder when divided by $m$ . For example, $47 \equiv 5 \pmod 7$ .

Worked example: A big product

What is the remainder when $1234 \times 5678$ is divided by $9$ ?

A number and its digit sum leave the same remainder on division by $9$ . $1234$ has digit sum $10$ , remainder $1$ . $5678$ has digit sum $26$ , remainder $8$ . So the product leaves remainder $1 \cdot 8 = 8$ .

Powers: look for a 1

To find the remainder of a huge power, compute small powers until the remainder is $1$ . After that, the pattern repeats.

Worked example: A huge power

What is the remainder when $3^{100}$ is divided by $7$ ?

Remainders of $3^1, 3^2, 3^3, \dots$ divided by $7$ : $3, 2, 6, 4, 5, 1$ . So $3^6$ leaves remainder $1$ . Since $100 = 6 \cdot 16 + 4$ , $3^{100} = (3^6)^{16} \cdot 3^4,$ which has the same remainder as $1^{16} \cdot 3^4 = 81$ . And $81 = 11 \cdot 7 + 4$ , so the remainder is 4.

Tip

Days of the week are remainders on division by $7$ . A date $100$ days from a Saturday is $100 = 14 \cdot 7 + 2$ days later, so it falls $2$ days after Saturday: Monday. And because $365 = 52 \cdot 7 + 1$ , a date moves forward one weekday each ordinary year.

Several conditions at once

Worked example: One less than a multiple

What is the smallest positive integer that leaves remainder $3$ when divided by $4$ , remainder $4$ when divided by $5$ , and remainder $5$ when divided by $6$ ?

Each remainder is one less than the divisor. So $n + 1$ is divisible by $4$ , $5$ and $6$ , meaning $n + 1$ is a multiple of $\operatorname{lcm}(4, 5, 6) = 60$ . The smallest is $n + 1 = 60$ , so $n = 59$ .

When there's no such pattern, list the numbers that satisfy the condition with the largest divisor and test them against the others.

Worked example: Listing

Find the smallest positive integer that leaves remainder $2$ when divided by $5$ and remainder $3$ when divided by $7$ .

Numbers with remainder $3$ mod $7$ : $3, 10, 17, 24, \dots$ Their remainders mod $5$ : $3, 0, 2$ . So the answer is $17$ . (All solutions are $17 + 35k$ .)

Common mistake

A remainder can never be negative or as large as the divisor. If your work gives $-2$ when dividing by $7$ , add $7$ to get the true remainder, $5$ .