[Introduction to Number Theory Series Part 12] Why Can We Reduce Big Numbers in Modular Arithmetic?

Once we know what congruence means, the next question is natural: if two numbers are congruent, can we replace one by the other inside a computation? For addition, subtraction, multiplication, and powers, the answer is yes.

What this post covers

• The basic idea of modular arithmetic
• Why addition, subtraction, and multiplication preserve congruence
• How to reduce powers
• Why modular division is a separate issue

Key terms

• modular arithmetic: arithmetic based on congruence classes
• congruence: the relation of having the same remainder
• modular inverse: the multiplicative inverse in modular arithmetic
• remainder: the leftover value after division

The basic idea

In mod 5,

$$12 \equiv 2 \pmod 5, \qquad 17 \equiv 2 \pmod 5.$$

So 12 and 17 can both be represented by the smaller value 2 in this modular setting.

Why are addition and multiplication safe?

If

$$a \equiv b \pmod n, \qquad c \equiv d \pmod n,$$

then

$$a+c \equiv b+d \pmod n,$$ $$a-c \equiv b-d \pmod n,$$

and

$$ac \equiv bd \pmod n.$$

This works because differences such as (a-b) and (c-d) are multiples of n, so the new differences remain multiples of n as well. In other words, congruent numbers can be substituted into these operations without changing the final remainder class.

Example 1: addition modulo 7

Compute

$$29+15 \pmod 7.$$

Since

$$29 \equiv 1 \pmod 7, \qquad 15 \equiv 1 \pmod 7,$$

we get

$$29+15 \equiv 1+1 \equiv 2 \pmod 7.$$

Indeed, 44 leaves remainder 2 modulo 7.

Example 2: multiplication modulo 6

Compute

$$14\times 11 \pmod 6.$$

Since

$$14 \equiv 2 \pmod 6, \qquad 11 \equiv 5 \pmod 6,$$

we get

$$14\times 11 \equiv 2\times 5 = 10 \equiv 4 \pmod 6.$$

Why are powers especially important?

Powers grow quickly, so modular reduction is especially useful there.

For example, in mod 5,

$$3^2=9 \equiv 4,$$

so

$$3^4=(3^2)^2 \equiv 4^2 = 16 \equiv 1 \pmod 5.$$

Why is division different?

Addition and multiplication behave nicely in every modulus. Division does not. In modular arithmetic, dividing by a number only makes sense when that number has a modular inverse. So division is not a basic operation here; it is a special case that depends on an extra condition.

Common mistakes

1. Reducing intermediate values and then forgetting the modulus

Every conclusion must still be read modulo n.

2. Assuming modular division always works

It does not. Division depends on inverses.

3. Thinking a congruence class has only one representative

In mod 5, the numbers 2, 7, 12, and 17 all represent the same class.

Wrap-up

Modular arithmetic works because congruence is preserved under addition, subtraction, multiplication, and powers.

Next we ask when division becomes possible in the modular world through modular inverses.