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(\mathrm{m}\mathrm{o}\mathrm{d}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(\mathrm{m}\mathrm{o}\mathrm{d}0)⟺a=b\mathrm{.}$

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<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>n$ is not used for a chosen remainder here. The relation $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}n)$ is defined even for $n=0$, where a remainder operation would not be available.

For every integer $n$, the relation $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}n)$ on $\mathbb{Z}$ (Congruence modulo an integer: $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}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\mathrm{/}\sim$). For $n=0$ it is equality, and for $n=1$ it is the universal relation.

Let $n,a,a^{\mathrm{\prime }},b,b^{\mathrm{\prime }}\in \mathbb{Z}$. If $a\equiv a^{\mathrm{\prime }}(\mathrm{m}\mathrm{o}\mathrm{d}n)$ and $b\equiv b^{\mathrm{\prime }}(\mathrm{m}\mathrm{o}\mathrm{d}n)$, then

$a+b\equiv a^{\mathrm{\prime }}+b^{\mathrm{\prime }}(\mathrm{m}\mathrm{o}\mathrm{d}n),a-b\equiv a^{\mathrm{\prime }}-b^{\mathrm{\prime }}(\mathrm{m}\mathrm{o}\mathrm{d}n),ab\equiv a^{\mathrm{\prime }}{b}^{\mathrm{\prime }}(\mathrm{m}\mathrm{o}\mathrm{d}n)\mathrm{.}$

In particular $-a\equiv -a^{\mathrm{\prime }}(\mathrm{m}\mathrm{o}\mathrm{d}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^{\mathrm{\prime }}{)}^k(\mathrm{m}\mathrm{o}\mathrm{d}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(\mathrm{m}\mathrm{o}\mathrm{d}n)\},$

and the integers modulo $n$ form the quotient set

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

This is the quotient-set construction of Equivalence relation, equivalence class, and the quotient set $A\mathrm{/}\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⟺a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}n)\mathrm{.}$

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}\mathrm{/}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}\mathrm{/}n$ (The congruence class $[a{]}_n$ and the quotient set $\mathbb{Z}\mathrm{/}n$) contains exactly one integer $r$ with $0\le r<n$. Consequently the map

$r⟼[r{]}_n(0\le r<n)$

is a bijection from the von Neumann natural $n$ to $\mathbb{Z}\mathrm{/}n$, and $\mathrm{\mid }\mathbb{Z}\mathrm{/}n\mathrm{\mid }=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}\mathrm{/}0$.

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

$[a{]}_n+[b{]}_n:=[a+b{]}_n,[a{]}_n[b{]}_n:=[ab{]}_n\mathrm{.}$

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^{\mathrm{\prime }}{]}_n$ and $[b{]}_n=[b^{\mathrm{\prime }}{]}_n$, then $a\equiv a^{\mathrm{\prime }}(\mathrm{m}\mathrm{o}\mathrm{d}n)$ and $b\equiv b^{\mathrm{\prime }}(\mathrm{m}\mathrm{o}\mathrm{d}n)$, so

$a+b\equiv a^{\mathrm{\prime }}+b^{\mathrm{\prime }}(\mathrm{m}\mathrm{o}\mathrm{d}n),ab\equiv a^{\mathrm{\prime }}{b}^{\mathrm{\prime }}(\mathrm{m}\mathrm{o}\mathrm{d}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}\mathrm{/}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}\mathrm{/}1$ from being a field.

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

1. $(\mathbb{Z}\mathrm{/}n,+,[0{]}_n)$ is an abelian group (Group and abelian group), with $-[a{]}_n=[-a{]}_n$;
2. $(\mathbb{Z}\mathrm{/}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\ge 1$ be an integer. Multiplication makes $\mathbb{Z}\mathrm{/}n$ a commutative monoid with identity $[1{]}_n$ by For every natural $n$, $(\mathbb{Z}\mathrm{/}n,+)$ is an abelian group, multiplication is a commutative monoid operation, and both distributive laws hold. A class $u\in \mathbb{Z}\mathrm{/}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}\mathrm{/}n{)}^{\times }:=\{u\in \mathbb{Z}\mathrm{/}n:\text{some }v\in \mathbb{Z}\mathrm{/}n\text{ satisfies }uv=[1{]}_n\}\mathrm{.}$

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

The quotient $\mathbb{Z}\mathrm{/}n$ is finite with cardinality $n$ by For $n\ge 1$, every class in $\mathbb{Z}\mathrm{/}n$ has one representative $r$ with $0\le r<n$, so $\mid \mathbb{Z}\mathrm{/}n\mid =n$; while $\mathbb{Z}\mathrm{/}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 $\mid B\mid \le \mid A\mid$, and equality holds if and only if $B=A$. Euler's totient function is therefore defined for every positive integer $n$ by

$\phi (n):=\mid (\mathbb{Z}\mathrm{/}n{)}^{\times }\mid \in \mathbb{N}$

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

• The domain of $\phi$ here is the positive integers. No value $\phi (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\ge 1$ and $a\in \mathbb{Z}$. Then $[a{]}_n$ is a unit of $\mathbb{Z}\mathrm{/}n$ (The unit group $(\mathbb{Z}\mathrm{/}n{)}^{\times }$ and Euler's totient $\phi (n)=\mid (\mathbb{Z}\mathrm{/}n{)}^{\times }\mid$ for $n\ge 1$) 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 $\phi (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

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

Let $p$ be prime and let $k\in \mathbb{N}$ with $k\ge 1$. 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}\}⟶\{s\in \mathbb{Z}:0\le s<p^k,p\mid s\},r⟼pr\mathrm{.}$

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

For every prime $p$ and natural $k\ge 1$,

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

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