congruence合同式ごうどうしき and mod operation演算えんざん

If congruences合同式ごうどうしき are viewed only as the calculation rule "the remainders are the same," it is hard to see why addition and multiplication are justified. In abstract algebra抽象代数ちゅうしょうだいすう, a congruence合同式ごうどうしき is viewed as equality of residue classes剰余類じょうよるい.

means

and at the same time means that $$a$$a and $$b$$b belong to the same residue class.

1The set of residue classes

Let $$n\text{[PARSE ERROR: Undefined("Command("ge")")]}2$$n\ge 2. Classifying all integers by their remainders modulo $$n$$n gives the quotient set商集合しょうしゅうごう

The elements of this set are not integers themselves, but equivalence classes of integers.

Here the quotient set is the set obtained by grouping integers with the same remainder into one class and then treating those classes as the elements.

Throughout this lecture the modulus $$n$$n is fixed, and $$\left[a\right]$$[a] abbreviates $$[a{]}_n$$[a]_n. Because changing the modulus changes the residue class, restore the subscript when several moduli are discussed at once.

2Addition and multiplication

Define addition and multiplication of residue classes by

The important point is that the right-hand side does not depend on the choice of representatives. If $$a\equiv a^{\prime }\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$a\equiv a'\pmod n and $$b\equiv b^{\prime }\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$b\equiv b'\pmod n, then

is a multiple of $$n$$n. Also,

is a multiple of $$n$$n. Therefore the sum and product are well-defined.

3The additive group structure

Now that addition is independent of representatives, we can verify the group axioms for $$(\mathbb{Z}/n\mathbb{Z},+)$$(\mathbb Z/n\mathbb Z,+). Closure follows from $$\left[a\right]+\left[b\right]=[a+b]\in \mathbb{Z}/n\mathbb{Z}$$[a]+[b]=[a+b]\in\mathbb Z/n\mathbb Z. Associativity follows from

The identity is $$\left[0\right]$$[0], and the inverse of $$\left[a\right]$$[a] is $$[-a]$$[-a]. Moreover, $$\left[a\right]+\left[b\right]=[a+b]=[b+a]=\left[b\right]+\left[a\right]$$[a]+[b]=[a+b]=[b+a]=[b]+[a], so addition is commutative. Therefore $$(\mathbb{Z}/n\mathbb{Z},+)$$(\mathbb Z/n\mathbb Z,+) is an abelian group.

The integer laws similarly pass to multiplication of residue classes. For example, associativity and left distributivity are

Commutativity and right distributivity follow in the same way, and $$\left[1\right]$$[1] is the multiplicative identity. Not every element has a multiplicative inverse. These addition and multiplication laws will later be organized as the ring axioms.

4The condition for an inverse

A residue class $$\left[a\right]$$[a] has a multiplicative inverse if there exists a class $$\left[x\right]$$[x] such that

This is the same as

The necessary and sufficient condition for this congruence to have a solution is

Indeed, if $$ax\equiv 1\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$ax\equiv1\pmod n, then $$ax-1=kn$$ax-1=kn for some integer $$k$$k. Every common divisor of $$a$$a and $$n$$n divides $$ax-kn=1$$ax-kn=1, so $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,n)=1$$\gcd(a,n)=1. Conversely, if $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,n)=1$$\gcd(a,n)=1, Bezout's identity gives integers $$x,y$$x,y such that

Reducing this equality modulo $$n$$n gives $$ax\equiv 1\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$ax\equiv1\pmod n, so $$\left[x\right]$$[x] is the inverse of $$\left[a\right]$$[a].

This condition is also independent of the representative. If $$a^{\prime }=a+kn$$a'=a+kn, every common divisor of $$a$$a and $$n$$n divides $$a^{\prime }$$a', while every common divisor of $$a^{\prime }$$a' and $$n$$n divides $$a=a^{\prime }-kn$$a=a'-kn. Hence $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,n)=\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a^{\prime },n)$$\gcd(a,n)=\gcd(a',n).

Here we are not dividing by a symbol; we are proving the existence of an inverse from the fact that the greatest common divisor is 1. Therefore, whenever a division-like operation is used, one must first check the condition that an inverse exists.

5Cancellation is not always valid in congruences

The congruence

holds, but $$1\text{[PARSE ERROR: Undefined("Command("not")")]}\equiv 4\text{[PARSE ERROR: Undefined("Command("pmod")")]}6$$1\not\equiv4\pmod6. Thus the factor 2 cannot be cancelled unconditionally as it could in an equality of integers.

In general, if $$ca\equiv cb\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$ca\equiv cb\pmod n and $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(c,n)=1$$\gcd(c,n)=1, then $$\left[c\right]$$[c] has a multiplicative inverse. Multiplying both sides by $$[c{]}^{-1}$$[c]^{-1} gives $$\left[a\right]=\left[b\right]$$[a]=[b], or $$a\equiv b\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$a\equiv b\pmod n. Thus $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(c,n)=1$$\gcd(c,n)=1 is a sufficient condition for cancellation by $$c$$c.

6Connection to Fermat's little theorem

If $$p$$p is prime, every nonzero residue class has an inverse. Write the set of all nonzero residue classes as

This set has the $$p-1$$p-1 elements $$\left[1\right],\dots ,[p-1]$$[1],\ldots,[p-1], and every element has an inverse by the criterion proved above. If the product of nonzero $$\left[a\right]$$[a] and $$\left[b\right]$$[b] were $$\left[0\right]$$[0], multiplication by $$[a{]}^{-1}$$[a]^{-1} would give $$\left[b\right]=\left[0\right]$$[b]=[0], a contradiction. Thus it is closed under multiplication. Associativity follows from integer multiplication, and $$\left[1\right]$$[1] is the identity. It is therefore a group of order $$p-1$$p-1. Lagrange's theorem, studied later, gives $$[a{]}^{p-1}=[1]$$[a]^{p-1}=[1] whenever $$p\nmid a$$p\nmid a, or equivalently

This is Fermat's little theorem.

This section is a preview of later material on groups and Lagrange's theorem. The main thread of this page uses only the well-definedness of residue-class operations and the condition for inverses to exist.

7Proof supplement: why congruence合同式ごうどうしき is preserved by addition and multiplication

Let $$n$$n be a positive integer. If the congruences合同式ごうどうしき

hold, then

also hold.

First prove the statement for addition. The congruence合同式ごうどうしき $$a\equiv b\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$a\equiv b\pmod n means $$n\mid (a-b)$$n\mid(a-b), and $$c\equiv d\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$c\equiv d\pmod n means $$n\mid (c-d)$$n\mid(c-d). Therefore

is also divisible by $$n$$n. Hence $$a+c\equiv b+d\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$a+c\equiv b+d\pmod n.

For multiplication, rewrite

Since $$n\mid (a-b)$$n\mid(a-b) and $$n\mid (c-d)$$n\mid(c-d), both terms on the right are divisible by $$n$$n. Hence $$n\mid (ac-bd)$$n\mid(ac-bd), so $$ac\equiv bd\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$ac\equiv bd\pmod n.

This proof証明しょうめい does not divide by $$n$$n; it uses the fact that $$n$$n divides a difference. Therefore no issue of division by zero in symbolic division arises. However, in the notation $$\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$$\pmod n, the modulus $$n$$n is fixed as a positive integer.

8Exercise link

9Summary

A congruence合同式ごうどうしき is equality of residue classes. Mod operations are justified because addition and multiplication on residue classes are determined independently of representatives. The additive structure $$(\mathbb{Z}/n\mathbb{Z},+)$$(\mathbb Z/n\mathbb Z,+) is an abelian group. Multiplicative inverses do not always exist; the condition $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,n)=1$$\gcd(a,n)=1 is necessary and sufficient.