Modular Arithmetic

For integers a, b and n > 0, what does a ≡ b (mod n) mean?

a and b leave the same remainder when divided by n

How can ‘a and b leave the same remainder when divided by n’ be written formally?

n | (a − b) (a - b is divisible by n)

What are the properties of congruence if a ≡ b (mod n) and c ≡ d (mod n)?

Addition: a + c ≡ b + d (mod n)

Subtraction: a − c ≡ b − d (mod n)

Multiplication: ac ≡ bd (mod n)

What does ax ≡ b (mod n) mean?

when ax is divided by n, it leaves the same remainder as b

When does ax ≡ b (mod n) have a solution?

Iff hcf(a, n) | b which is the rule that tells you whether its solvable or not e.g. if hcf(a, n) = 1 then there’s exactly one solution mod n

Why does hcf(a, n) = 1 mean there’s only 1 solution?

Because Bézout’s Lemma guarantees integers x, y such that ax + ny = 1 so x acts as a multiplicative inverse of a mod n. We can multiply both sides of the congruence by that inverse to isolate x

What is the Chinese Remainder Theorem?

If the moduli n₁, n₂, …, n_k are pairwise coprime (no common factors other than 1), then the system:

x = a₁ (mod n₁)

x = a₂ (mod n₂)

…

x = a_k (mod n_k)

Has exactly 1 solution N = n₁n₂…n_k.

(If the moduli don’t “interfere” with each other (they’re coprime), you can combine several modular equations into one single equivalent equation)

What is Fermat’s Little Theorem?

If p is prime and a is not divisible by p, then: a^p−1 ≡ 1 (mod p)