Modular arithmetic — definition, addition, multiplication, congruence: Question bank

This bank targets the ideas behind modular arithmetic, not the arithmetic. Every trap below is a place where intuition from ordinary numbers quietly breaks. Read the prompt, commit to an answer out loud, then reveal.

Reminder of the vocabulary you'll need (all built in the parent note):

$a \equiv b (mod n)$ means == $a - b$ is a whole-number multiple of $n$ == — equivalently, $a$ and $b$ leave the same remainder when divided by $n$ .
The modulus $n$ is the "wrap-around" number; the residue (or remainder) is the standard representative in ${0, 1, \dots, n - 1}$ .
A divisor of $n$ is a whole number $d$ that divides $n$ evenly (no remainder) — e.g. $3$ is a divisor of $12$ because $12 = 3 \times 4$ .
Two numbers are coprime if their greatest common divisor is $1$ .
$φ (n)$ (Euler's totient) counts how many numbers in ${1, 2, \dots, n - 1}$ are coprime to $n$ — i.e. how many residues have an inverse. E.g. $φ (6) = 2$ (only $1$ and $5$ ).

Figure — Modular arithmetic — definition, addition, multiplication, congruence

True or false — justify

TF1. If

a \equiv b (mod n)

then

b \equiv a (mod n)

True — congruence is symmetric. If

a - b = k n

then

b - a = (- k) n

, still an integer multiple of

n

, so the roles swap freely.

TF2. If

a \equiv b (mod n)

then

a

and

b

are equal.

False — they are equal as residue classes, not as integers.

17 \equiv 3 (mod 7)

but

17 \neq = 3

; they only share the same remainder.

TF3. If

a \equiv b (mod n)

, then

a \equiv b (mod d)

for every divisor

d

n

(a whole number that divides

n

evenly).

True — if

a - b

is a multiple of

n

, and

d

divides

n

, then

a - b

is also a multiple of

d

. Congruence "survives" moving to a divisor modulus.

TF4. If

a \equiv b (mod 4)

and

a \equiv b (mod 6)

, then

a \equiv b (mod 24)

False — you get

a \equiv b

mod the least common multiple

lcm (4, 6) = 12

, not the product

24

. See GCD and LCM; multiplying moduli only works when they are coprime.

TF5.

c a \equiv c b (mod n)

always implies

a \equiv b (mod n)

False — you may only cancel

c

when

g cd (c, n) = 1

. E.g.

2 \cdot 3 \equiv 2 \cdot 0 (mod 6)

but

3 \neq \equiv 0 (mod 6)

, because

g cd (2, 6) = 2

TF6. Every non-zero residue mod

n

has a multiplicative inverse.

False — only residues coprime to

n

do. Mod

6

, the number

2

has no inverse since

g cd (2, 6) = 2

; see Modular Inverses.

TF7. If

n

is prime, every non-zero residue mod

n

has an inverse.

True — for prime

p

, every

a

1, \dots, p - 1

satisfies

g cd (a, p) = 1

, so all of them are invertible. This is what makes prime moduli so friendly for Linear Congruences.

TF8.

a^{2} \equiv b^{2} (mod n)

implies

a \equiv b (mod n)

False — squaring loses sign information. Mod

8

3^{2} = 9 \equiv 1

and

5^{2} = 25 \equiv 1

, yet

3 \neq \equiv 5

. This is exactly the subtlety behind Quadratic Residues.

TF9. There are exactly

n

residue classes modulo

n

True — every integer lands in exactly one of the buckets

0, 1, \dots, n - 1

by the Division Algorithm, which guarantees a unique remainder in that range.

Spot the error

SE1. "

- 3 mod 7 = - 3

, since

- 3

is already smaller than

7

The standard residue must be non-negative: add

7

to get

- 3 \equiv 4 (mod 7)

. "Smaller than

n

" is not the rule; "in

{0, \dots, n - 1}

" is.

SE2. "

6 x \equiv 9 (mod 15)

, so

x \equiv \frac{9}{6} = \frac{3}{2} (mod 15)

You can't divide by

6

because

g cd (6, 15) = 3 \neq = 1

. Instead divide the whole congruence and the modulus by

3

2 x \equiv 3 (mod 5)

SE3. "

a \equiv b (mod n)

and

c \equiv d (mod n)

, so

a^{c} \equiv b^{d} (mod n)

Exponents do not reduce mod

n

. The base can be swapped (

a \to b

), but the exponent lives in a different world — its reduction is governed by Eulers Theorem or Fermats Little Theorem, mod

φ (n)

(Euler's totient), not mod

n

SE4. "

5 x \equiv 0 (mod 10)

has the unique solution

x \equiv 0

It has five solutions in

{0, \dots, 9}

: every even value

{0, 2, 4, 6, 8}

makes

5 x

a multiple of

10

. When

g cd (a, n) = g > 1

, the congruence

a x \equiv 0

has exactly

g

solutions — here

g = g cd (5, 10) = 5

SE5. "Since

3 \times 5 = 15 \equiv 0 (mod 15)

, the number

3

must equal

0

mod

15

A product being

0

does not force a factor to be

0

when the modulus is composite.

3

and

5

are zero divisors mod

15

; neither is

0

itself.

SE6. "

a \equiv b (mod 0)

just means

a = b

, so mod

0

is fine."

The modulus

0

is degenerate: "

a - b

is a multiple of

0

" forces

a - b = 0

, so it collapses to ordinary equality and no wrap-around exists. We require

n \geq 1

(usually

n \geq 2

) for modular arithmetic to be interesting.

SE7. "To reduce

17 + 23 (mod 7)

I must first add to get

40

, then divide."

You may, but you don't have to — the addition rule lets you reduce first:

3 + 2 = 5

. For huge numbers, reducing first is the whole point (this powers RSA Cryptography).

Why questions

WHY1. Why is congruence an equivalence relation and not just "sometimes true"?

Because it is reflexive (

a - a = 0 \cdot n

), symmetric (negate

k

), and transitive (add the two differences). Those three together let us treat whole classes as single objects.

WHY2. Why does reducing the base before taking a power work, but reducing the exponent does not?

The multiplication rule applies to bases repeatedly, so bases reduce mod

n

. The exponent counts how many times you multiply — that count isn't a factor being multiplied, so it follows a separate cycle length

φ (n)

(Euler's totient), not

n

(Eulers Theorem).

WHY3. Why do we need

g cd (a, n) = 1

to divide by

a

Dividing by

a

means multiplying by an inverse

a^{- 1}

with

a a^{- 1} \equiv 1

. Such an inverse exists only when

a

and

n

share no common factor, otherwise no multiple of

a

ever lands on

1

. See Modular Inverses.

WHY4. Why does the Chinese Remainder Theorem insist the moduli be coprime?

Coprime moduli guarantee the combined system pins down a unique residue mod the product. With a shared factor the two conditions can either overlap redundantly or contradict, so uniqueness breaks.

WHY5. Why can two different numbers square to the same residue?

Because

x

and

- x

(i.e.

n - x

) always share a square:

(n - x)^{2} = n^{2} - 2 n x + x^{2} \equiv x^{2}

. Squaring folds the circle in half, so it can't be undone by a single "square root". This is the heart of Quadratic Residues.

WHY6. Why is mod arithmetic called "clock arithmetic"?

A clock has finitely many positions and wraps: after the top you return to the start. Residue classes are exactly the finitely many marks on that circle, and adding is stepping around it.

WHY7. Why does the multiplication rule stay valid even for negative operands?

The proof only used "

a - b

is a multiple of

n

", which is a statement about differences, not about signs. Negatives are handled by choosing a negative

k

, so nothing changes.

Edge cases

EC1. What is every integer congruent to, modulo

1

Everything is

\equiv 0 (mod 1)

. Since

1

divides every difference, there is a single residue class — the whole number line collapses to one point.

EC2. Is

0 \equiv 0 (mod n)

? What class is

0

in?

Yes —

0 - 0 = 0 = 0 \cdot n

. Zero sits in the class of all multiples of

n

{\dots, - n, 0, n, 2 n, \dots}

EC3. What are the residues of

a

and

- a

mod

n

, and when do they coincide?

They coincide only when

2 a \equiv 0 (mod n)

— e.g.

a = 0

always, and

a = n /2

when

n

is even. Otherwise

- a \equiv n - a

, the "mirror" position on the circle.

EC4. Does

a \equiv b (mod n)

with

n

negative make sense?

Yes, but it's identical to

(mod ∣ n ∣)

, since "multiple of

n

" and "multiple of

- n

" describe the same set. By convention we always write a positive modulus.

EC5. If

g cd (a, n) = g

, when does

a x \equiv c (mod n)

have any solution?

Exactly when

g

divides

c

(i.e.

g

is a divisor of

c

). If it does, there are precisely

g

solutions mod

n

; if not, there are none. This is the solvability test for Linear Congruences.

EC6. What happens to "reduce to

{0, \dots, n - 1}

" when the input is already in range but the operation overshoots by exactly

n

Landing on

n

itself wraps to

0

: e.g.

4 + 3 (mod 7) = 7 \equiv 0

. The top of the range and the bottom are the same mark on the clock.

EC7. For prime modulus

p

, how many square roots can a nonzero residue have?

At most two —

x

and

p - x

. A quadratic can have no more than two roots in the field of residues mod a prime, unlike composite moduli where roots can multiply (mod

8

, the residue

1

has four).

Recall One-line self-test

Why can you swap a base but never an exponent inside a congruence? ::: The base is a factor obeying the multiplication rule (mod $n$ ); the exponent is a count of multiplications, governed by a separate cycle length $φ (n)$ (mod the totient).