Modular Arithmetic

Proof. Reflexive: $a-a=0=n\cdot 0$, so $n\mid a-a$.

Symmetric: if $a-b=nk$ then $b-a=n(-k)$, and $-k$ is an integer.

Transitive: if $a-b=nk$ and $b-c=n\ell$, then adding gives $a-c=n(k+\ell )$, and $k+\ell$ is an integer.

Each step used only that the multiples of $n$ form a set containing $0$, closed under negation and closed under addition.∎

Proof. Division with remainder gives unique integers $q,r$ with $a=qn+r$ and $0\le r<n$. Then $a-r=qn$, so $a\equiv r$, which proves that at least one such representative exists.

For uniqueness, suppose $0\le r<s<n$ with $r\equiv s(\mathrm{mod}n)$. Then $n\mid s-r$ while $0<s-r<n$, and no positive multiple of $n$ is smaller than $n$. So $s-r$ cannot be a multiple of $n$, a contradiction.

Finally, if $a=q_{1}n+r_1$ and $b=q_{2}n+r_2$ with $0\le r_1,r_2<n$, then $a-b=(q_1-q_2)n+(r_1-r_2)$, so $n\mid a-b$ exactly when $n\mid r_1-r_2$, which by the uniqueness just proved happens exactly when $r_1=r_2$.∎

Proof. Write $a-a^{\prime }=nk$ and $b-b^{\prime }=n\ell$.

For the sum, $(a+b)-(a^{\prime }+b^{\prime })=(a-a^{\prime })+(b-b^{\prime })=n(k+\ell )$. For the difference, replace $\ell$ by $-\ell$.

For the product, the trick is to change one factor at a time:

and $bk+a^{\prime }\ell$ is an integer. Hence $n\mid ab-a^{\prime }{b}^{\prime }$.∎

Proof. By the theorem Congruence is compatible with the ring operations and induction on $j$, $a\equiv b$ implies $a^j\equiv b^j$ for every $j\ge 0$: the case $j=0$ is $1\equiv 1$, and $a^{j+1}=a^j\cdot a\equiv b^j\cdot b=b^{j+1}$. Multiplying by the integer coefficient $c_j$ gives $c_j{a}^j\equiv c_j{b}^j$, and summing the finitely many terms gives $f(a)\equiv f(b)$.∎

Proof. If the $n$ elements are pairwise incongruent they meet $n$ distinct classes, and there are only $n$ classes by the proposition Least residues classify the classes, so they meet every class exactly once. The converse is immediate from "exactly one".

For the second claim, suppose $a{r}_i+b\equiv a{r}_j+b(\mathrm{mod}n)$. Subtracting $b$ and using compatibility, $a{r}_i\equiv a{r}_j$, so $n\mid a(r_i-r_j)$. Since $\gcd (a,n)=1$, Euclid's lemma gives $n\mid r_i-r_j$, hence $i=j$. So the $n$ new elements are pairwise incongruent, and the first claim applies.∎

Proof. ($\Leftarrow$) Suppose $\gcd (a,n)=1$. By Bézout's identity there are integers $u,v$ with $au+nv=1$. Reducing modulo $n$ kills the term $nv$, leaving $au\equiv 1(\mathrm{mod}n)$, so $u$ is an inverse.

($\Rightarrow$) Suppose $ax\equiv 1(\mathrm{mod}n)$, so $ax-1=nk$ for some $k$, that is $ax-nk=1$. Let $d=\gcd (a,n)$. Then $d$ divides both $ax$ and $nk$, hence divides their difference $1$, so $d=1$.∎

Proof. Suppose $ax\equiv 1$ and $ay\equiv 1(\mathrm{mod}n)$. Then

where each congruence used compatibility of multiplication with congruence.∎

Proof. The congruence says $ax-b=nk$ for some $k$, i.e. that $b=ax-nk$ lies in the set $\{ax+ny\}$ of integer combinations of $a$ and $n$. That set is exactly $d\mathbb{Z}$, so a solution exists if and only if $d\mid b$.

Assume $d\mid b$ and write $a=d{a}^{\prime }$, $b=d{b}^{\prime }$, $n=d{n}^{\prime }$ with $\gcd (a^{\prime },n^{\prime })=1$. Dividing the relation $ax-b=nk$ through by $d$ shows that $ax\equiv b(\mathrm{mod}n)$ is equivalent to

Since $\gcd (a^{\prime },n^{\prime })=1$, the theorem Invertibility criterion gives $(a^{\prime }{)}^{-1}$ mod $n^{\prime }$, and multiplying by it shows the solution set is the single class $x\equiv (a^{\prime }{)}^{-1}{b}^{\prime }(\mathrm{mod}{n}^{\prime })$ — in particular non-empty, and a class modulo $n^{\prime }=n/d$.

Finally, one class modulo $n/d$ splits into exactly $d$ classes modulo $n$, namely those listed, because two integers congruent mod $n/d$ differ by a multiple of $n/d$, and the multiples of $n/d$ fall into exactly $d$ classes mod $n$, represented by $0,n/d,\dots ,(d-1)n/d$.∎

Proof. Let $e_i={\sum }_{j=i}^k{b}_j{2}^{j-i}$ be the integer whose binary digits are the leading bits $b_k\dots b_i$ of $e$. Then $e_k=1$ and $e_i=2e_{i+1}+b_i$, and $e_0=e$.

We show by downward induction that $r_i\equiv a^{e_i}$. The base case is $r_k=a=a^{e_k}$. If $r_{i+1}\equiv a^{e_{i+1}}$, then since congruence is compatible with multiplication, $r_{i+1}^2\equiv a^{2e_{i+1}}$ and $a\cdot r_{i+1}^2\equiv a^{2e_{i+1}+1}$; in both cases the recursion yields $r_i\equiv a^{2e_{i+1}+b_i}=a^{e_i}$. Taking $i=0$ gives $r_0\equiv a^e$.

Each of the $k$ steps costs one squaring and at most one further multiplication, so at most $2k$ multiplications; and since each $r_i$ is reduced below $n$, every product formed is below $n^2$.∎

Proof. If $d\mid e$, say $e=dm$, then $a^e=(a^d{)}^m\equiv 1^m=1$.

Conversely suppose $a^e\equiv 1$. Divide: $e=qd+r$ with $0\le r<d$. Then

If $r>0$ this contradicts minimality of $d$, so $r=0$ and $d\mid e$. For the last claim, assume $i\ge j$ and multiply $a^i\equiv a^j$ by $(a^{-1}{)}^j$, which exists because $a$ is a unit, to get $a^{i-j}\equiv 1$.∎

Proof. Since $p\nmid a$ we have $\gcd (a,p)=1$, so by the proposition Recognising a complete residue system the list $a\cdot 1,a\cdot 2,\dots ,a(p-1)$ is pairwise incongruent mod $p$, and none is $\equiv 0$. Hence it is a permutation of $1,2,\dots ,p-1$ modulo $p$. Multiplying the two lists together,

Each of $1,\dots ,p-1$ is coprime to $p$, so $(p-1)!$ is a unit mod $p$ and may be cancelled, leaving $a^{p-1}\equiv 1$. Multiplying by $a$ gives $a^p\equiv a$, which also holds when $p\mid a$ since then both sides are $\equiv 0$.∎

Proof. Let $u_1,\dots ,u_{\phi (n)}$ be the least residues coprime to $n$. Multiplication by $a$ permutes them: each $a{u}_i$ is coprime to $n$ (a product of two units is a unit), and $a{u}_i\equiv a{u}_j$ forces $u_i\equiv u_j$ after multiplying by $a^{-1}$. Multiplying all of them,

and the product of units is a unit, so it cancels. The divisibility statement is then the proposition The order divides every exponent that works.∎

Proof. Well defined: the definitions refer to representatives, so we must check the answer does not depend on which ones. If $[a]=[a^{\prime }]$ and $[b]=[b^{\prime }]$ then $a\equiv a^{\prime }$ and $b\equiv b^{\prime }$, so by the theorem Congruence is compatible with the ring operations $a+b\equiv a^{\prime }+b^{\prime }$ and $ab\equiv a^{\prime }{b}^{\prime }$, i.e. $[a+b]=[a^{\prime }+b^{\prime }]$ and $[ab]=[a^{\prime }{b}^{\prime }]$.

Axioms: each is inherited. For instance associativity of multiplication reads $([a][b])[c]=[(ab)c]=[a(bc)]=[a]([b][c])$, where the middle equality is associativity in $\mathbb{Z}$. Commutativity, distributivity, the additive identity $[0]$, additive inverses $-[a]=[-a]$ and the multiplicative identity $[1]$ all transfer by the same one-line argument, because every axiom is an identity between polynomial expressions in the elements.∎

Proof. The description of the units is the theorem Invertibility criterion restated, noting that $\gcd (a,n)$ depends only on $[a]$: if $a\equiv a^{\prime }(\mathrm{mod}n)$ then $a^{\prime }=a+nk$, and any common divisor of $a$ and $n$ divides $a^{\prime }$, and conversely.

The units of any commutative ring form a group: $1$ is a unit; if $a,b$ are units then $(ab)(b^{-1}{a}^{-1})=1$, so $ab$ is; and $a^{-1}$ is a unit with inverse $a$. Associativity is inherited. Counting: the classes coprime to $n$ are represented by the integers in $\{1,\dots ,n\}$ coprime to $n$, and there are $\phi (n)$ of those.∎

Proof. Prime $\Rightarrow$ field. If $n=p$ is prime, every $a$ with $[a]\ne [0]$ satisfies $p\nmid a$, hence $\gcd (a,p)=1$, hence $[a]$ is a unit by the theorem The group of units. So every nonzero element is invertible and $[1]\ne [0]$ because $p\ge 2$.

Field $\Rightarrow$ domain. In any field, if $[a][b]=[0]$ with $[a]\ne [0]$, multiplying by $[a{]}^{-1}$ gives $[b]=[0]$.

Domain $\Rightarrow$ prime. If $n$ is composite, write $n=st$ with $1<s,t<n$. Then $[s]$ and $[t]$ are nonzero — neither $s$ nor $t$ is divisible by $n$, being smaller and positive — while $[s][t]=[n]=[0]$. So $\mathbb{Z}/n\mathbb{Z}$ has zero divisors and is not a domain.∎

Proof. Uniqueness. Suppose $x$ and $y$ both satisfy the system. Then $n_i\mid x-y$ for every $i$. Since the $n_i$ are pairwise coprime, their product divides $x-y$: inductively, if $n_1\cdots n_j$ and $n_{j+1}$ both divide $x-y$ and are coprime — $\gcd (n_1\cdots n_j,n_{j+1})=1$ because $n_{j+1}$ is coprime to each factor — then their product divides $x-y$. Hence $N\mid x-y$, i.e. $x\equiv y(\mathrm{mod}N)$.

Existence. Consider the map

which is well defined because $n_i\mid N$, so $x\equiv y(\mathrm{mod}N)$ implies $x\equiv y(\mathrm{mod}{n}_i)$. Uniqueness, just proved, says $\Phi$ is injective. Both sides are finite sets of the same size $N=n_1\cdots n_k$, so an injective map between them is surjective. Surjectivity is exactly the assertion that every tuple $(a_1,\dots ,a_k)$ is achieved, i.e. that the system has a solution.∎

Proof. First, $M_i$ exists: $N_i$ is the product of the $n_j$ with $j\ne i$, each coprime to $n_i$, so $\gcd (N_i,n_i)=1$ and the theorem Invertibility criterion applies.

Now fix $j$ and reduce the sum modulo $n_j$. For $i\ne j$ the factor $N_i$ contains $n_j$ as a divisor, so $a_i{N}_i{M}_i\equiv 0(\mathrm{mod}{n}_j)$ and every such term drops out. Only the term $i=j$ survives, and there $N_j{M}_j\equiv 1(\mathrm{mod}{n}_j)$ by the choice of $M_j$. Hence

so the stated $x$ solves the system. By the theorem Chinese Remainder Theorem it is the only solution mod $N$.∎

Proof. Necessity. If $x$ solves both, then $d\mid m\mid x-a$ and $d\mid n\mid x-b$, so $d$ divides $(x-b)-(x-a)=a-b$.

Sufficiency. The first congruence says $x=a+mt$ for some integer $t$. Substituting into the second, we need

By the theorem Linear congruence this is solvable in $t$ exactly when $\gcd (m,n)=d$ divides $b-a$, which is the hypothesis, and then $t$ is determined modulo $n/d$. Writing $t=t_0+(n/d)s$ gives

so $x$ is determined modulo $mn/d=\mathrm{lcm}(m,n)$.∎

Proof. Necessity is the necessity half of the theorem Two congruences, general moduli applied to each pair.

For sufficiency, induct on $k$. The case $k=1$ is trivial. Suppose the first $k-1$ congruences have been merged into a single congruence $x\equiv c(\mathrm{mod}L)$ with $L=\mathrm{lcm}(n_1,\dots ,n_{k-1})$; note $c\equiv a_i(\mathrm{mod}{n}_i)$ for each $i<k$. We must merge it with $x\equiv a_k(\mathrm{mod}{n}_k)$, so by the theorem Two congruences, general moduli it suffices to show $g:=\gcd (L,n_k)$ divides $c-a_k$.

Let $q$ be any prime power dividing $g$ exactly, say $q=p^{\alpha }\Vert g$. Then $p^{\alpha }\mid n_k$ and $p^{\alpha }\mid L$, and since $L$ is a least common multiple, $p^{\alpha }\mid n_i$ for some $i<k$. Hence $p^{\alpha }\mid \gcd (n_i,n_k)$, which divides $a_i-a_k$ by hypothesis; and $p^{\alpha }\mid n_i\mid c-a_i$. Adding, $p^{\alpha }\mid c-a_k$. As this holds for every prime power exactly dividing $g$, we get $g\mid c-a_k$. The merged modulus is $\mathrm{lcm}(L,n_k)=\mathrm{lcm}(n_1,\dots ,n_k)$.∎

Proof. $\Phi$ is well defined and bijective by the theorem Chinese Remainder Theorem. It is a ring homomorphism because reduction is: $[x+y{]}_m=[x{]}_m+[y{]}_m$ and $[xy{]}_m=[x{]}_m[y{]}_m$ by the definition of the operations in $\mathbb{Z}/m\mathbb{Z}$, and the same in the second coordinate, while $[1{]}_{mn}\mapsto ([1{]}_m,[1{]}_n)$ is the identity of the product. A bijective ring homomorphism is an isomorphism, its set-theoretic inverse being automatically a homomorphism.∎

Proof. An isomorphism of rings carries units to units bijectively, so $(\mathbb{Z}/mn\mathbb{Z}{)}^{\times }\cong (\mathbb{Z}/m\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}{)}^{\times }$. A pair is invertible componentwise exactly when both components are, so the units of a product are the product of the unit groups. Counting with the theorem The group of units gives $\phi (mn)=\phi (m)\phi (n)$.∎