• ModularArithmetic

1. Residue classes and the integers mod m

From the DivisionAlgorithm, we have that for each n, m there is a unique remainder r with 0≤r<m and n = qm+r for some q; this unique r is written as (n mod m). Define n ≡_m n' (read "n is congruent to n' mod m") if (n mod m) = (n' mod m) or equivalently if there is some q ∈ ℤ such that n = n' + qm. Because congruence is a relation defined by pulling equality back through a function, it's an equivalence relation, and we can partition the integers into equivalence classes (called residue classes, where residue is an old synonym for remainder) [0]_m, [1]_m, [2]_m, ..., [m-1]_m. These equivalence classes ℤ/≡_m form the integers mod m, written as ℤ_m. Usually we will drop the brackets and just write 0, 1, 2, ..., m-1; sometimes a (mod m) will be tacked on the end of any equation we write to remind ourselves that we are working in ℤ_m.

The most well-known version of ℤ_m is ℤ₂, the integers mod 2: the class [0]₂ is known as the even numbers and the class [1]₂ as the odd numbers.

2. Arithmetic on residue classes

We can define arithmetic operations on residue classes in ℤ_m just as we defined arithmetic operations on integers (defined as equivalence classes of pairs of naturals). Given residue classes [x]_m and [y]_m, define [x]_m + [y]_m = [x+y]_m, where the addition in the RHS is the usual integer addition in ℤ. So, for example, in ℤ₂ we have 0+0 = 0, 0+1 = 1, 1+0 = 1, and 1+1 = 0 (since 1+1 = 2 ∈ [0]_m). Note that as with the integers, we must verify that this definition of addition is well-defined: in particular, it doesn't matter which representatives x and y we pick.

Theorem

If x ≡_m x' and y ≡_m y', then x+y ≡_m x'+y'.

Proof

Choose q_x, q_x', r, q_y, q_y' and s such that x = q_xm+r, x' = q_x'm+r, y = q_ym+s, and y'=q_y'm+s. Then x+x' = (q_x+q_y)m+(r+s) and y+y'=(q_x'+q_y')m+(r+s). It follows that (x+y) mod m = (r+s) mod m = (x'+y') mod m and x+y ≡_m x'+y' as claimed.

Similarly, we can define -[x]_m = [-x]_m and [x]_m×[y]_m = [x×y]_m. A similar argument to the proof above shows that these definitions also give well-defined operations on residue classes. All of the usual properties of addition, subtraction, and multiplication are inherited from ℤ: addition and multiplication are commutative and associative, the distributive law applies, etc.

For example, here is an addition table for ℤ₃:

and here is the multiplication table:

It may help to think of 2 as -1; so it's not surprising that 2×2 =4 ≡_m 1 = -1×-1.

Using these tables, we can do arbitrarily horrible calculations in ℤ₃ using the same rules as in ℤ, e.g. 2(1+2)-2 = 2(0)-2 = -2 = 1 (mod 2). Note we tack on the "(mod 2)" at then end so that the reader won't think we've gone nuts.

Comment: the fact that [x]_m + [y]_m = [x+y]_m and [x]_m × [y]_m = [xy]_m for all x and y means that the remainder operation x ↦ x mod m is a homomorphism from ℤ to ℤ_m: it preserves the operations + and × on ℤ. We'll see more examples of homomorphisms between sets with attached operations (called algebras) in AlgebraicStructures.

3. Division in Zm

What we don't get in general in ℤ_m is the ability to divide. This is not terribly surprising, since we don't get to divide (without remainders) in ℤ either. But for some values of x and some values of m we can in fact do division: for these x and m there exists a multiplicative inverse x^-1 (mod m) such that xx^-1 = 1 (mod m). We can see the winning x's for example by looking for ones in the multiplication table below for ℤ₉:¹

Here we see that 1^-1 = 1, as we'd expect, but that we also have 2^-1 = 5, 4^-1 = 7, 5^-1 = 2, 7^-1 = 4, and 8^-1 = 8. There are no inverses for 0, 3, or 6.

What 1, 2, 4, 5, 7, and 8 have in common is that they are all relatively prime to 9. This is not an accident: when gcd(x,m) = 1 we can use the extended Euclidean algorithm (see NumberTheory) to find x^-1 (mod m). Observe that what we want is some x' such that xx' ≡_m 1, or equivalently such that x'x + qm = 1. But the extended Euclidean algorithm finds such an x' (and q) whenever 1 = gcd(x,m).

If gcd(x,m) ≠ 1, then x has no multiplicative inverse in ℤ_m. The reason is that if some d>1 divides both x and m, it continues to divide xx' and m for any x'≠0. So in particular xx' can't be congruent to 1 mod m since qm+1 and m don't share any common factors for any value of q.

The set of of residue classes [x]_m where gcd(x,m) = 1 is written as ℤ^*_m. For a prime p, ℤ^*_p includes all non-zero elements of ℤ_p, since gcd(x,p) = 1 for any x that is not 0 or a multiple of p.

3.1. The size of ℤ*m and Euler's Theorem

The size of ℤ^*_m, or equivalently the number of numbers less than m whose gcd with m is 1, is written φ(m) and is called Euler's totient function or just the totient of m. When p is prime, gcd(n,p) = 1 for all n with 0<n<p, so φ(p) = |ℤ^*_p| = p-1. For a prime power p^k, we similarly have gcd(n,p^k) = 1 unless p|n. There are exactly p^k-1 numbers less than p^k that are divisible by p (they are 0, p, 2p, ... p^k-1p), so φ(p^k) = p^k - p^k-1 = p^k-1(p-1). For composite numbers m that are not prime powers, finding the value of φ(m) is more complicated; but we can show using the ChineseRemainderTheorem that in general

One reason φ(m) is important is that it plays a central role in Euler's Theorem, which describes the behavior of exponents mod m. The most general version of Euler's Theorem is that a^φ(m)+1 = a (mod m) for all a, although the usual statement is that a^φ(m) = 1 (mod m) when gcd(a,m) = 1.

We can prove the weaker version using an argument adapted from the proof of BiggsBook Theorem 13.3.2: Let z₁, z₂, ..., z_φ(m) be the elements of ℤ^*_m. For any y ∈ ℤ^*_m, define yℤ^*_m = { yz₁, yz₂, ..., yz_{φ(m) }. Since y has a multiplicative inverse mod m, the mapping z ↦ yz (mod m) is a bijection, and so yℤ^*^}m _{= ℤ^*^}m _{(mod m). It follows that ∏}i _zi _{= ∏}i _yzi _{= y^φ(m)^ ∏}i _zi _{(mod m). But now multiply both sides by (∏}i _zi,,)^-1 to get 1 = y^φ(m) (mod m) as claimed.

For the special case that m is a prime, Euler's Theorem is known as Fermat's Little Theorem, and says a^p-1 = 1 (mod p) for all primes p and all a such that p∤a.²

Euler's Theorem is popular in cryptography; for example, the RSA encryption system is based on the fact that (x^e)^d = x (mod m) when de = 1 (mod φ(m)). Here x is encrypted by raising it to the e-th power mod m, and decrypted by raising the result to the d-th power. It is widely believed that publishing e and m reveals no useful information about d provided e and m are chosen carefully.

4. Group structure of ℤm and ℤ*m

Assumes previous knowledge of GroupTheory.

The set of residue classes [x]_m where gcd(x,m) = 1 form an abelian group (see GroupTheory).

We will now show that ℤ^*_m = { x | 0 < x < m, gcd(x,m) } also forms an abelian group, whose operation is multiplication mod m (i.e. x*y = xy mod m), provided m is at least 2.

To show that ℤ^*_m is an abelian group, we need to show closure, commutativity, associativity, existence of an identity (1), and existence of inverses.

Closure

Let x and y be in ℤ^*_m so that gcd(x,m) = 1 and gcd(y,m) = 1. z = xy mod m = xy - km where k = ⌊xy/m⌋. Let p be any prime factor of m. If p|xy, then p|x or p|y; since x and y have no common factors with m, neither does xy. Subtracting km can't create a common factor with m, so gcd(z,m)=1. We also have 0≤z<m (true of all remainders), and z can't equal zero because gcd(0,m)=m≠0.

Commutativity

Trivial: xy mod m = yx mod m because xy = yx.

Associativity

The only tricky thing here is that taking mods in between multiplications might break associativity. We'll argue though that xyz mod m = (xy mod m) z mod m; by symmetry this will also show xyz mod m = (yz mod m) x mod m = (xy mod m) z mod m. To prove the claim, observe that xy = (xy mod m) + km for some k. Then xyz = (xy mod m) z + kzm, and xyz mod m = (xy mod m) z mod m + (kzm mod m) = (xy mod m) z mod m since kzm mod m = 0.

Identity

1.

Inverses

Let gcd(x,m) = 1. Then the extended Euclidean algorithm returns x',m' such that x'x+m'm=1. So (x'x + m'm) mod m = 1 mod m or x'x mod m = 1. So let x^-1 = x' mod m. We can easily show that x^-1 has gcd(x^-1,m)=1: if p divides m, then xx^-1 = km+1 = kk'p+1 which can't be divisible by p because it has remainder 1 when divided by p. But if p does not divide xx^-1, it can't divided either of x or x^-1, and so x^-1 in particular has no common factors with m.

Note that we could define the additive group ℤ_m as a quotient group of (ℤ,+) by the congruence x~y if x mod m = y mod m. This almost works for ℤ^*_m---but the problem is that ℤ with multiplication is not a group, because it doesn't have inverses. The best that we can do is construct the quotient monoid (ℤ,×)/~, which will contain at least one element with no inverse (0), and possibly many others.

CategoryMathNotes