Overview

Modular arithmetic is one of the most important tools in olympiad mathematics. It allows us to work with remainders instead of entire numbers, often turning complicated expressions into manageable computations.

Many problems involving:

• Divisibility
• Last digits
• Cyclic patterns
• Parity
• Residues
• Number theoretic equations

and more become a lot simpler when viewed modulo some integer.

The main idea is that two integers are considered equivalent if they leave the same remainder when divided by a fixed modulus.

Motivation

Suppose we want to determine the last digit of

Computing the entire number is impossible by hand. However, the last digit of a number depends only on its remainder modulo $10$. As such, we can work modulo $10$:

The powers repeat with period $4$:

Since

the last digit matches that of $7^2$, namely $9$.

Instead of handling a very large number directly, modular arithmetic reduced the problem to studying a short repeating cycle.

Congruences

Definition

Let $m$ be a positive integer. We say that

if $a$ and $b$ leave the same remainder when divided by $m$.

Equivalently,

In words, $a-b$ is divisible by $m$.

Examples

because $17-5=12$ is divisible by $12$.

because $38-2=36$ is divisible by $9$.

Negative numbers also work:

since

Residue Classes

Modulo $m$, every integer belongs to one of the residue classes

For example, modulo $5$:

• $12 \equiv 2 \pmod{5}$
• $27 \equiv 2 \pmod{5}$
• $102 \equiv 2 \pmod{5}$

so all three numbers belong to the same residue class.

You can think of modular arithmetic as a number system that 'wraps around' after reaching the modulus.

For instance, modulo $12$ behaves like a clock

• $10+5 \equiv 3 \pmod{12}$
• $11+4 \equiv 3 \pmod{12}$

because after passing $12$, we begin again at $0$.

Basic Properties

If

and

then:

Addition

Subtraction

Multiplication

Powers

for all positive integers $k$.

These rules allow us to simplify expressions significantly before computing.

Important Warning: Division

In ordinary arithmetic, we can cancel common factors freely:

In modular arithmetic, cancellation requires more thought.

For example,

since both sides equal $2$ modulo $6$.

However,

We can only divide by a number if it is coprime to the modulus.

Cancellation Rule

If

and

then

This idea appears frequently in olympiad problems.

Modular Inverses

Closely related to cancellation is the idea of a modular inverse. We say that $a$ has a multiplicative inverse modulo $m$ if there exists an integer $b$ such that $ab \equiv 1 \pmod{m}$. This inverse exists if and only if $\gcd(a,m)=1$, a fact following from Bézout's identity. When it does exist, dividing by $a$ modulo $m$ means multiplying by $b$.

Working with Large Numbers

A major advantage of modular arithmetic is that we can reduce numbers at every step.

For example,

Since

we instead compute

Now notice:

Therefore

Hence

Cyclicity

Powers modulo $m$ often repeat in cycles. Since there are only finitely many possible residues modulo $m$, repeated multiplication must eventually produce a repeated residue.

Example

Find the last digit of

The powers of $2$ modulo $10$ are:

The cycle length is $4$.

Since

the last digit corresponds to the fourth term in the cycle:

Recognising cyclic behaviour is one of the most common uses of modular arithmetic in AMC and AIME problems.

Divisibility Tests

Many familiar divisibility rules come naturally from modular arithmetic.

Let

be a positive integer.

Since

we can analyse $N$ modulo different integers.

Divisibility by $2$

Because

all powers of $10$ beyond the units digit disappear modulo $2$.

So only the final digit matters.

Divisibility by $3$

Since

we have

for all $k$. Therefore,

Hence a number is divisible by $3$ when its digit sum is divisible by $3$.

Divisibility by $9$

The same argument works because

Divisibility by $11$

Since

we get

As such, a number is divisible by $11$ when the alternating digit sum is a multiple of $11$.

Solving Congruences

Linear Congruences

Consider

We want a multiplicative inverse of $3$ modulo $7$.

Since

multiplying both sides by $5$ gives

Thus

Key Olympiad Insight

Modular arithmetic is powerful because it allows us to:

• Eliminate impossible cases
• Reduce very large computations
• Classify numbers into residue classes
• Detect patterns and cycles
• Prove divisibility or non divisibility.

In many olympiad problems, choosing the correct modulus is the main challenge.

A good heuristic is:

• Use modulo $2$ for parity
• Modulo $10$ for last digits
• Modulo $3$ or $9$ for digit sums
• Modulo primes for divisibility and residues
• Modulo small numbers to simplify expressions

Worked Examples

Example 1

Find the remainder when $3^{2026}$ is divided by $7$.

The powers of $3$ modulo $7$ cycle:

The cycle length is $6$.

Since

we get

Hence the remainder is $4$.

Example 2

Prove that no perfect square leaves remainder $2$ when divided by $4$.

Every integer is congruent to one of $0,1,2,3$ modulo $4$.

Squaring each possibility gives:

Therefore every square is congruent to either $0$ or $1$ modulo $4$, never $2$.

Example 3

Determine the last two digits of $7^{222}$.

We work modulo $100$.

Observe:

Then

Therefore,

Common Pitfalls

• Forgetting that congruence means equality of remainders, not ordinary equality.
• Cancelling factors modulo $m$ when the factor is not coprime to $m$.
• Reducing incorrectly after exponentiation.
• Using a modulus that does not actually simplify the problem.
• Assuming patterns continue without proof.

Strategy Tips

• Reduce numbers modulo $m$ as early as possible.
• Search for cycles in powers.
• Test small cases to identify residue patterns.
• Use negative residues when convenient:

is often easier to work with than $19 \equiv 9 \pmod{10}$.

• When proving impossibility, try looking at all residue classes modulo a small integer.

Practice Problems