Number Theory • Topic 9

Congruences

Congruences are equations involving modular arithmetic. Solving linear congruences is similar to solving linear equations $a x = b$ , but with a twist regarding existence and uniqueness.

Linear Congruence

A linear congruence is of the form:

a x \equiv b (mod n)

Existence of Solutions

The congruence

a x \equiv b (mod n)

has solutions if and only if:

d = g cd (a, n) divides b

Number of Solutions

d ∣ b

, there are exactly $d$ distinct solutions modulo

n

If $g cd (a, n) = 1$ , there is exactly one unique solution modulo $n$ .

Solving Strategy

Check GCD: Calculate $d = g cd (a, n)$ . If $d ∤ b$ , no solution.
Simplify: If $d > 1$ , divide the entire congruence (including modulus) by $d$ :

\frac{a}{d} x \equiv \frac{b}{d} (mod \frac{n}{d})

Now the coefficient and new modulus are coprime.

Multiply by Inverse: Multiply both sides by the modular inverse of the coefficient (see Topic 14).

Example

Solve

6 x \equiv 15 (mod 21)

Proof. 1. $g cd (6, 21) = 3$ .

Does $3 ∣ 15$ ? Yes. There are 3 solutions modulo 21.
Divide by 3: $2 x \equiv 5 (mod 7)$ .
Multiply by inverse of 2 mod 7 (which is 4, since $2 \cdot 4 = 8 \equiv 1$ ):

x \equiv 20 \equiv 6 (mod 7)

Lift back to mod 21:

x \in {6, 6 + 7, 6 + 14} = {6, 13, 20}

. ∎

Practice Problems

Exercise (Problem 1)

Solve

4 x \equiv 2 (mod 10)

Exercise (Problem 2)

Find all integers

x

such that

5 x \equiv 1 (mod 11)

Exercise (Problem 3)

Prove that

x^{2} \equiv 2 (mod 5)

has no integer solutions.