Congruences, the Integers Modulo n and the Chinese Remainder Theorem

Let $a,b,n\in\mathbb Z$. We say that $a$ is congruent to $b$ modulo $n$, and write

$a\equiv b\pmod n,$

when $n\mid(a-b)$ in the sense of Divisibility in $\mathbb{Z}$: $d \mid a$ when $a = dq$ for some integer $q$. Thus there is an integer $q$ with $a-b=nq$. The modulus is any integer; it is not required to be positive.

At modulus $0$, the condition is $0\mid(a-b)$, which holds exactly when $a-b=0$. Hence

$a\equiv b\pmod 0\quad\Longleftrightarrow\quad a=b.$

At modulus $1$, every two integers are congruent because $1$ divides every integer. Changing the sign of the modulus changes nothing: $n\mid(a-b)$ exactly when $-n\mid(a-b)$.

• Congruence is a relation on integers. The quotient sets and operations below use nonnegative or positive moduli only where their statements require it.
• The notation $a\bmod n$ is not used for a chosen remainder here. The relation $a\equiv b\pmod n$ is defined even for $n=0$, where a remainder operation would not be available.

For every integer $n$, the relation $a\equiv b\pmod n$ on $\mathbb Z$ (Congruence modulo an integer: $a\equiv b\pmod n$ when $n\mid(a-b)$, including the moduli $0$ and $1$) is an equivalence relation (Equivalence relation, equivalence class, and the quotient set $A/{\sim}$). For $n=0$ it is equality, and for $n=1$ it is the universal relation.

Let $n,a,a',b,b'\in\mathbb Z$. If $a\equiv a'\pmod n$ and $b\equiv b'\pmod n$, then

$a+b\equiv a'+b'\pmod n,\qquad a-b\equiv a'-b'\pmod n,\qquad ab\equiv a'b'\pmod n.$

In particular $-a\equiv-a'\pmod n$, and for every $k\in\mathbb N$ the natural powers of Powers $g^{n}$: natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ satisfy $a^k\equiv(a')^k\pmod n$.

Fix an integer $n$. Congruence modulo $n$ is an equivalence relation on $\mathbb Z$ by Congruence modulo every integer is an equivalence relation on $\mathbb{Z}$. The congruence class of $a$ modulo $n$ is

$[a]_n:=\{\,b\in\mathbb Z:b\equiv a\pmod n\,\},$

and the integers modulo $n$ form the quotient set

$\mathbb Z/n:=\{\,[a]_n:a\in\mathbb Z\,\}.$

This is the quotient-set construction of Equivalence relation, equivalence class, and the quotient set $A/{\sim}$. By The equivalence classes of an equivalence relation are nonempty, cover $A$, and are pairwise equal or disjoint; conversely every such cover arises from exactly one equivalence relation, two classes are equal exactly when their representatives are congruent:

$[a]_n=[b]_n\quad\Longleftrightarrow\quad a\equiv b\pmod n.$

At $n=0$ each class is a singleton because congruence modulo $0$ is equality. At $n=1$ there is one class, namely $\mathbb Z$ itself.

• The notation $\mathbb Z/n$ in this item denotes a quotient set. It does not yet assert any algebraic structure.
• Since congruence modulo $n$ and modulo $-n$ are the same relation, their quotient sets are literally the same collection of subsets of $\mathbb Z$.

Let $n$ be a positive integer. Every class in $\mathbb Z/n$ (The congruence class $[a]_n$ and the quotient set $\mathbb{Z}/n$) contains exactly one integer $r$ with $0\le r<n$. Consequently the map

$r\longmapsto[r]_n\qquad(0\le r<n)$

is a bijection from the von Neumann natural $n$ to $\mathbb Z/n$, and $|\mathbb Z/n|=n$. This includes $n=1$, where the only representative is $0$. For $n=0$, the map $a\mapsto[a]_0$ is a bijection $\mathbb Z\to\mathbb Z/0$.

Let $n\in\mathbb N$, including $n=0$ and $n=1$. For classes in $\mathbb Z/n$ (The congruence class $[a]_n$ and the quotient set $\mathbb{Z}/n$) define

$[a]_n+[b]_n:=[a+b]_n,\qquad [a]_n[b]_n:=[ab]_n.$

These are binary operations in the sense of Binary operation on a set; associativity, commutativity, and a subset closed under the operation. Indeed, if $[a]_n=[a']_n$ and $[b]_n=[b']_n$, then $a\equiv a'\pmod n$ and $b\equiv b'\pmod n$, so

$a+b\equiv a'+b'\pmod n,\qquad ab\equiv a'b'\pmod n$

by Congruent integers may be added, subtracted and multiplied: representative changes preserve both arithmetic operations. Thus the two displayed classes do not depend on the representatives chosen.

For $n=0$, every class is a singleton and these operations reproduce integer addition and multiplication under the bijection $\mathbb Z\to\mathbb Z/0$. For $n=1$, the quotient has one element, so $[0]_1=[1]_1$ and both operations are the unique binary operation on a one-element set.

• The representative-independence argument is part of the definition. Without it the displayed formulas would be rules on integers, not operations on classes.
• No field assertion is made here. In particular, the coincidence $[0]_1=[1]_1$ will exclude $\mathbb Z/1$ from being a field.

For every $n\in\mathbb N$, with addition and multiplication as in Addition and multiplication on $\mathbb{Z}/n$ by $[a]_n+[b]_n=[a+b]_n$ and $[a]_n[b]_n=[ab]_n$:

1. $(\mathbb Z/n,+,[0]_n)$ is an abelian group (Group and abelian group), with $-[a]_n=[-a]_n$;
2. $(\mathbb Z/n,\cdot,[1]_n)$ is a commutative monoid (Semigroup and monoid);
3. multiplication distributes over addition on both sides.

The assertions include $n=0$ and $n=1$. At $n=1$, the two distinguished identities coincide because $[0]_1=[1]_1$.

Let $n\ge1$ be an integer. Multiplication makes $\mathbb Z/n$ a commutative monoid with identity $[1]_n$ by For every natural $n$, $(\mathbb{Z}/n,+)$ is an abelian group, multiplication is a commutative monoid operation, and both distributive laws hold. A class $u\in\mathbb Z/n$ is a unit when it is invertible in that monoid (Left inverse, right inverse, and invertible element of a monoid). The set of all units is

$(\mathbb Z/n)^\times:=\{\,u\in\mathbb Z/n:\text{some }v\in\mathbb Z/n\text{ satisfies }uv=[1]_n\,\}.$

By The invertible elements of a monoid form a group under the restricted operation, multiplication restricts to a group operation on $(\mathbb Z/n)^\times$, called the unit group modulo $n$.

The quotient $\mathbb Z/n$ is finite with cardinality $n$ by For $n\ge 1$, every class in $\mathbb{Z}/n$ has one representative $r$ with $0\le r<n$, so $\lvert\mathbb{Z}/n\rvert=n$; while $\mathbb{Z}/0$ is in bijection with $\mathbb{Z}$, and its unit set is a finite subset by A subset of a finite set is finite, with $\lvert B\rvert \le \lvert A\rvert$, and equality holds if and only if $B = A$. Euler's totient function is therefore defined for every positive integer $n$ by

$\varphi(n):=\big|(\mathbb Z/n)^\times\big|\in\mathbb N$

(The cardinality $\lvert A\rvert$ of a finite set). For $n=1$, the quotient has one element, which is its multiplicative identity and hence a unit, so $\varphi(1)=1$ follows from the definition.

• The domain of $\varphi$ here is the positive integers. No value $\varphi(0)$ is defined.
• The one-element multiplicative monoid is a group, even though its identity is also its additive zero. It is not a field because a field requires distinct elements $0$ and $1$ (Field).

Let $n\ge1$ and $a\in\mathbb Z$. Then $[a]_n$ is a unit of $\mathbb Z/n$ (The unit group $(\mathbb{Z}/n)^\times$ and Euler's totient $\varphi(n)=\lvert(\mathbb{Z}/n)^\times\rvert$ for $n\ge1$) if and only if

$\gcd(a,n)=1,$

that is, if and only if $a$ and $n$ are coprime (Coprime integers: $\gcd(a,b) = 1$). Consequently the condition $\gcd(a,n)=1$ depends only on the class $[a]_n$.

Euler's totient satisfies $\varphi(1)=1$. If $p$ is prime (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$), then

$\varphi(p)=p-1.$

Let $p$ be prime and let $k\in\mathbb N$ with $k\ge1$. Write $k-1$ for the unique natural $j$ with $j+1=k$. Multiplication by $p$ gives a bijection

$\{\,r\in\mathbb Z:0\le r<p^{k-1}\,\}\longrightarrow\{\,s\in\mathbb Z:0\le s<p^k,\ p\mid s\,\},\qquad r\longmapsto pr.$

Thus the standard representatives modulo $p^k$ divisible by $p$ are exactly $0,p,2p,\ldots,(p^{k-1}-1)p$, and there are $p^{k-1}$ of them.

For every prime $p$ and natural $k\ge1$,

$\varphi(p^k)=p^k-p^{k-1}.$

Equivalently, among the $p^k$ standard classes modulo $p^k$, the nonunits are exactly those whose standard representatives are divisible by $p$.