Congruence and well defined operations

Algebra often constructs a new object by treating several old objects as equivalent. The construction works only if its operations do not depend on a hidden choice of representative. Congruence classes of integers offer a concrete place to learn that proof technique before using abstract quotients.

1 Equivalence classes

A relation $\sim$ on a set is an equivalence relation if it is reflexive, symmetric and transitive. The class $[a]$ consists of all elements equivalent to $a$. Two classes are either identical or disjoint: an element in both lets transitivity connect their representatives. Thus classes partition the original set.

Fix an integer $n\ge2$. Define $a\equiv b\pmod n$ when $n$ divides $a-b$. The relation is reflexive because $n\mid0$, symmetric because divisibility survives negation, and transitive because it survives addition. Division with remainder shows there are exactly $n$ classes, represented by $0,\ldots,n-1$. The set of classes is $\mathbb Z/n\mathbb Z$.

Define $[a]+[b]=[a+b]$ and $[a][b]=[ab]$. These require a well-definedness proof. If $a'=a+rn$, $b'=b+sn$, then $a'+b'-(a+b)=n(r+s)$ and

$$a'b'-ab=n(rb+sa+rsn).$$

Both differences are divisible by $n$. Hence the resulting classes are independent of representatives. Exponentiation to nonnegative integer powers also respects congruence by repeated multiplication.

By contrast, a proposed operation $[a]/[b]=[a/b]$ is meaningless without additional conditions: $a/b$ might not be an integer, and a denominator class need not be invertible.

2 Groups domains and fields in one example

Under addition, the classes form an abelian group: zero is the identity, $[-a]$ is the inverse, and associativity descends from integer addition. With multiplication they form a commutative ring with identity $[1]$. A nonzero class can be a zero divisor, meaning it multiplies another nonzero class to zero. In $\mathbb Z/8\mathbb Z$, $[2][4]=[0]$.

A unit is a class with a multiplicative inverse.

Unit criterion. $[a]$ is a unit modulo $n$ if and only if $\gcd(a,n)=1$.

Proof. If the gcd is 1, Bézout gives integers $u,v$ with $ua+vn=1$, so $[u][a]=[1]$. Conversely, if $[u][a]=[1]$, then $ua-1$ is divisible by $n$, so every common divisor of $a,n$ divides 1. $\square$

Bézout itself follows from the Euclidean algorithm: repeated division preserves the set of integer combinations, and back substitution expresses the last nonzero remainder, the gcd, as such a combination.

For example, $1=3\cdot7-2\cdot10$, so $[7]^{-1}=[3]$ modulo 10. Modulo a prime $p$, every nonzero class is coprime to $p$, so every nonzero class is a unit: $\mathbb Z/p\mathbb Z$ is a field. Composite moduli fail: if $n=ab$ with $1<a,b<n$, the nonzero classes $[a],[b]$ multiply to zero.

3 Solving a linear congruence

The congruence $ax\equiv b\pmod n$ is solvable exactly when $d=\gcd(a,n)$ divides $b$. Necessity follows because $ax-b=kn$ makes $d\mid b$. For sufficiency, multiply a Bézout identity $ua+vn=d$ by $b/d$ to obtain a solution.

If one solution is $x_0$, all solutions differ by multiples of $n/d$ modulo $n$. Indeed, $a(x-x_0)$ is divisible by $n$ exactly when $(a/d)(x-x_0)$ is divisible by $n/d$; coprimality permits cancellation. There are exactly $d$ solution classes modulo $n$.

For $6x\equiv8\pmod{14}$, $d=2$ divides 8. Dividing gives $3x\equiv4\pmod7$ and the inverse of 3 modulo 7 is 5, so $x\equiv6\pmod7$. The two classes modulo 14 are 6 and 13. Direct substitution verifies both.

Full integer proof reused in the congruence argument

In this integer proof $\mathbb N$ means $\{0,1,2,\ldots\}$. The following division, gcd-invariance, termination and coefficient-update argument supplies the Bézout assertion used above; all signed and zero input cases are included.

Theorem

Division algorithm

Let $a,b\in\mathbb Z$ with $b\ne0$. Then there exist unique integers $q$ and $r$ such that

$$a=bq+r,\qquad 0\le r\lt|b|.$$

The integer $q$ is the quotient and $r$ is the remainder.

The condition $0\le r\lt|b|$ is not decoration. It is what makes the remainder unique. For example,

$$17=5\cdot3+2$$

has an allowed remainder $2$, while

$$17=5\cdot2+7$$

does not count as the division algorithm because $7$ is not smaller than $5$.

For existence, first take $a\ge0$ and $b>0$. The set

$$S=\{a-bn:n\in\mathbb N,\ a-bn\ge0\}$$

contains $a$, so well-ordering supplies a least member $r=a-bq$. If $r\ge b$, then $r-b=a-b(q+1)$ would be a smaller nonnegative member. Hence $0\le r\lt b$. If $a\lt0$ and $b>0$, the integer $A=a+(-a)b=(-a)(b-1)$ is nonnegative. Divide $A=bQ+r$ by the case just proved; rearranging gives $a=b(Q+a)+r$ with the same allowed remainder. For $b\lt0$, divide by $B=|b|>0$ and replace the resulting quotient $Q$ by $-Q$. Thus no sign case requires a negative remainder.

For uniqueness, suppose $a=bq+r=bq'+r'$ with both remainders in range. Then $b(q-q')=r'-r$, but $|r'-r|\lt|b|$. A nonzero integer multiple of $b$ has absolute value at least $|b|$, so $r'=r$. Since $b\ne0$, the remaining equality forces $q'=q$. The strict upper bound proves uniqueness; merely requiring a nonnegative remainder would not.

Theorem

Gcd step

If $a=bq+r$, then

$$\gcd(a,b)=\gcd(b,r).$$

Proof: Preserve the entire set of common divisors

The target is equality of two gcds. A stronger intermediate statement makes the proof direct: an integer $h$ divides both $a,b$ exactly when it divides both $b,r$. In the forward direction use $r=a-bq$; in the reverse direction use $a=bq+r$. Both steps use closure under integer linear combinations.

The two divisor sets therefore have the same greatest element when the inputs are not both zero. If $a=b=0$, then $r=0$ and both gcds equal $0$ by convention. The identity itself does not need a remainder bound; the bound is needed to make the algorithm progress.

Concept lensAlgorithmic

An invariant and a decreasing computation

The gcd is the quantity preserved by each replacement $(a,b)\mapsto(b,r)$. The remainder is the quantity made smaller. These serve different purposes: preservation proves that the final answer is the original gcd, while strict decrease proves that a final step will occur. Start with absolute values, swap to put the larger positive input first, and stop immediately if the other input is zero. In every remaining division the divisor is positive.

The algorithm must terminate because the remainders form a strictly decreasing sequence of nonnegative integers:

$$r_1>r_2>r_3>\cdots\ge0.$$

A strictly decreasing sequence of nonnegative integers cannot continue forever.

Back-substitution can also be organized forward. For positive inputs put $r_0=a$, $r_1=b$, and keep coefficients $r_k=s_ka+t_kb$, starting with $(s_0,t_0)=(1,0)$ and $(s_1,t_1)=(0,1)$. If $r_{k+2}=r_k-q_{k+1}r_{k+1}$, then

$$s_{k+2}=s_k-q_{k+1}s_{k+1},\qquad t_{k+2}=t_k-q_{k+1}t_{k+1}.$$

Substituting the two known linear combinations proves this update. Every coefficient remains integral, and the row for the last nonzero remainder supplies the required coefficients of the gcd.

Theorem

Bézout's identity

For any integers $a,b$, there exist integers $x,y$ such that

$$\gcd(a,b)=ax+by.$$

For signed nonzero inputs, compute using $|a|,|b|$ and absorb their signs into the resulting coefficients. If one input is zero, use $|a|=a\operatorname{sgn}(a)$ or its counterpart for $b$; for $(0,0)$ use $x=y=0$. This proves all cases of the identity.

When the inputs are not both zero, the gcd is also the smallest positive integer linear combination. It is such a combination by the identity, and every positive combination is a positive multiple of the gcd, hence at least as large. For $(0,0)$ there is no positive combination.

4 Graded practice

E1 Foundation. List the units modulo 12 and identify one nonzero zero divisor.

E2 Congruence. Solve $4x\equiv6\pmod{10}$ and $4x\equiv5\pmod{10}$.

E3 Well-definedness. Does $f([a]_6)=[a]_3$ define a function? Does $g([a]_3)=[a]_6$?

E4 Proof. In an integral domain, prove $ab=ac$ and $a\ne0$ imply $b=c$. Explain why cancellation fails in $\mathbb Z/8\mathbb Z$.

5 Full solutions

S1. Units are $[1],[5],[7],[11]$, the classes coprime to 12. For example $[3]$ is a zero divisor since $[3][4]=[0]$ with both factors nonzero.

S2. The first reduces to $2x\equiv3\pmod5$, so $x\equiv4\pmod5$: classes 4 and 9 modulo 10. The second has no solution because $\gcd(4,10)=2$ does not divide 5.

S3. Yes for $f$: a difference divisible by 6 is divisible by 3. No for $g$: $[0]_3=[3]_3$ but $[0]_6\ne[3]_6$, so one input would receive two outputs.

S4. $a(b-c)=0$, and absence of zero divisors forces $b-c=0$. Modulo 8, $[2][1]=[2][5]$ although $[1]\ne[5]$, because $[2][4]=[0]$. Nonzero is not enough for multiplicative cancellation in a ring with zero divisors.

Summary

Equivalence classes are sets of indistinguishable representatives. Operations and maps on them must be checked for well-definedness. Congruence arithmetic exhibits additive groups, rings, units and fields concretely, while the gcd controls both inverses and linear-congruence solvability.