1.5 Linear Congruences

Let $m\in \mathbb{N}$ We say that $0,1,...,m-1$ form a complete set of residues module $m$, because they have exactly one representative from each congruence class. The ring $\mathbb{Z}/m\mathbb{Z}$ is $\{0,1,...,m-1\}$ equipped with addition and multiplication modulo $m$. It is easy to check that this ring is commutative.

Example 1.5.1 (Associativity)

Let $a,b,c\in \{0,1,...,m-1\}$. We write
$ab=q_{1}m+r_1,bc=q_{2}m+r_2$
with $0\le r_1,r_2<m$. Then
$r_{1}c\equiv abc\equiv a{r}_2\mathrm{mod}m$
hence $(ab)c=a(bc)\in \mathbb{Z}/m\mathbb{Z}$

Notation We will denote the multiplicative group of units (invertible elements) modulo $m$ by ($\mathbb{Z}/m\mathbb{Z}{)}^{\times }$

Lemma 1.5.2

Let $m\in \mathbb{N}$ and $a\in \mathbb{Z}$ Then $a$ is invertible modulo $m$ if and only if $\gcd (a,m)=1$.

Example 1.5.3

We have $(\mathbb{Z}/m\mathbb{Z}{)}^{\times }=\{1,5\}\mathrm{mod}6$

Proof

The integer $a$ is invertible module $m$ if and only if there exist $x,y\in \mathbb{Z}$ such that $ax+my=1$. By Bezout’s lemma, such integers exist if $(a,m)=1$, and conversely if such integers exist then $a,m$ must be coprime.

Hence $(\mathbb{Z}/m\mathbb{Z}{)}^{\times }$ comprises the coprime residue classes modulo $m$. The Euler totient function $\phi$ counts the number of coprime residue classes:
$\phi (m)=\#\{a\in \{1,2,...,\}:\gcd (a,m)=1\}$ Therefore $|(\mathbb{Z}/m\mathbb{Z}{)}^{\times }|=\phi (m)$

Example 1.5.4

We have $\phi (6)=2$

Lemma 1.5.5

If $p$ is prime, then $\mathbb{Z}/p\mathbb{Z}$ is a field, and
$(\mathbb{Z}/p\mathbb{Z}{)}^{\times }=\{1,2,...,p-1\}\mathrm{mod}p$
has order $\phi (p)=p-1$

Proof

It is a commutative ring, and any non-zero element is invertible (being coprime to the modulus)

We also denote this by ${\mathbb{F}}_p$. Note that if $m$ is composite then $\mathbb{Z}/m\mathbb{Z}$ isn’t a field since any prime divisor of $m$ is non-invertible.

Example 1.5.6

We have
$1^2\equiv 2\times 4\equiv 3\times 5\equiv 6^2\equiv 1\mathrm{mod}7$

Mod 13 (Card Game)

1. Each player is dealt a hand of cards, interpreted as residue classes modulo 13, and two cards $a_1,a_2$ are placed into the centre.
2. Racing, a player can either play the sum ($a_1+a_2),product($a1a2$),arithmeticprogression($2a2—a1$)orgeometricprogression($a2^2a1^{-1}$)asthecard$a_3$, declaring what type of move they have made
3. Play continues with cards $a_2$ and $a_3$ in place of $a_1$ and $a_2$ and so on, until somebody finishes and wins

Example 1.5.7

Geometric progression: 7, J, and..? We have
$11\equiv 24\equiv 4(-7)\equiv 9\times 7\mathrm{mod}13$
so the next card is
$9\times 11\equiv 8$

Lemma 1.5.8 (Solving a linear congruence)

Let $a,b\in \mathbb{Z}$ and $m\in \mathbb{N}$. Then: #
(a) There exists $a\in \mathbb{Z}$ solving $ax\equiv b\mathrm{mod}m$ if and only if $\gcd (a,m)\mid b$
(b) If $\gcd (a,m)\mid b$ and $x_0\in \mathbb{Z}$ is a solution to $a{x}_0\equiv b\mathrm{mod}m$, then all solutions are given by
$x_0+\frac{tm}{\gcd (a,m)}(t\in \mathbb{Z})$

Proof

Put
$g=\gcd (a,m),a=g{a}^{\prime },m=g{m}^{\prime }$
so that $(a^{\prime },m^{\prime })=1$
(a) if $x\in \mathbb{Z}$ and $ax\equiv b\mathrm{mod}m$ then $b\equiv ax\equiv 0\mathrm{mod}g$. Conversely, if $g\mid b$ then, writing $b=g{b}^{\prime }$, our congruence becomes $a^{\prime }x\equiv b^{\prime }\mathrm{mod}{m}^{\prime }$. This has a solution because $(a^{\prime },m^{\prime })=1$. It’s given by $b^{\prime }$ times the inverse of $a^{\prime }$ module $m^{\prime }$.
(b) If $t\in \mathbb{Z}$ and $x=x_0+tm/g$ then $ax\equiv b+atm/g\equiv b\mathrm{mod}m$. It remains to show that there are no other solutions. If $x$ solves the congruence then $a^{\prime }x\equiv b^{\prime }\equiv a^{\prime }{x}_0\mathrm{mod}{m}^{\prime }$, so $m^{\prime }$ divides $x-x_0$ by the general Euclid lemma. Therefore $x=X_0+t{m}^{\prime }$ for some $t\in \mathbb{Z}$.

Theorem 1.5.10 (Classical Chinese Remainder Theorem)

Let $m_1,...m_K\in \mathbb{N}$ be pairwise coprime, and let $a_1,...,a_K\in \mathbb{Z}$. Then there exists $x\in \mathbb{Z}$, unique modulo ${\prod }_k{m}_k$ such that
$x\equiv a_k\mathrm{mod}{m}_k(1\le k\le K)$
This is given by ${\sum }_i{a}_i{M}_i{y}_i$, where $M_i={\prod }_{j\ne i}{m}_j$ and $M_i{y}_i\equiv 1\mathrm{mod}{m}_i$

Proof $k$ we have ${\sum }_i{a}_i{M}_i{y}_i\equiv a_k{M}_k{y}_k\equiv a_k\mathrm{mod}{m}_k$ For uniqueness, observe that if $x,y$ are solutions then $x-y$ is divisible by $m_1,...,m_K$. As the $m_i$ are pairwise coprime, it follows from the fundamental theorem of arithmetic that $m_1...m_K$ divides $x-y$

For existence, observe that for each

Theorem 1.5.14 (Algebraic Chinese Remainder Theorem)

Let $m_1,...,m_K\in \mathbb{N}$ be pairwise coprime, and put $M={\prod }_k{m}_k$. Then
$\psi :\mathbb{Z}/M\mathbb{Z}\to \mathbb{Z}/m_1\mathbb{Z}\times ...\times \mathbb{Z}/m_K\mathbb{Z}$
$x\mapsto (x\mathrm{mod}{m}_1,...,x\mathrm{mod}{m}_K)$
is a ring isomorphism. Moreover, it restricts to a group isomorphism
$(\mathbb{Z}/M\mathbb{Z}{)}^{\times }\to (\mathbb{Z}/m_1\mathbb{Z}{)}^{\times }\times ...\times (\mathbb{Z}/m_k\mathbb{Z}{)}^{\times }$

Proof

Well-defined: If $x\in \mathbb{Z}$ then
$x+M\equiv x\mathrm{mod}{m}_k(1\le k\le K)$
We saw that modular arithmetic respects addition and multiplication, so $\psi$ is a ring homomorphism. The classical Chinese remainder theorem defines an inverse function, so $\psi$ is bijective and therefore an isomorphism.
For the second part, note that $x\in \mathbb{Z}/M\mathbb{Z}$ is coprime to $M$ if and only if it’s coprime to each $m_k$. Therefore $\psi$ restricts to a bijection
$(\mathbb{Z}/M\mathbb{Z}{)}^{\times }\to (\mathbb{Z}/m_1\mathbb{Z}{)}^{\times }\times ...\times (\mathbb{Z}/m_k\mathbb{Z}{)}^{\times }$
This is a group homomorphism because $\psi$ is a ring homomorphism. Hence, it’s a group isomorphism.

Recall that an arithmetic function is a function $\mathbb{N}\to \mathbb{C}$ and than an arithmetic function $f$ is multiplicative if $f(mn)=f(m)f(n)$ holds for any coprime positive integers $m$ and $n$.

Corollary 1.5.15

Euler’s totient function is multiplicative

Proof

Apply the algebraic Chinese remainder theorem with $K=2$

Lemma 1.5.16

For $n\in \mathbb{N}$ we have
$\phi (n)=n{\prod }_{p\mid n}(1-\frac{1}{p})$
where the product is over primes dividing $n$.

Proof

Observe that $\phi (1)=1$. Next, suppose $n=p^k$ for some prime $p$ and some $k\in \mathbb{N}$. then $\phi (n)$ is he number of residue classes that aren’t divisible by $p$, which is
$p^k-p^{k-1}=p^k(1-\frac{1}{p})$
Finally, suppose $n=p_1^{k_1}...p_r^{k_r}$, where the $p_i$ are pairwise distinct primes and the $k_i$ are positive integers. Then
$\phi (n)={\prod }_{i\le r}\phi (p^{k_i})={\prod }_{i\le r}{p}^{k_i}(1-\frac{1}{p})=n{\prod }_{p\mid n}(1-\frac{1}{p})$

Lemma 1.5.18 (Totient function identity)

For $n\in \mathbb{N}$, we have
${\sum }_{d\mid n}\phi (d)=n$
where the sum is over the positive divisors of $n$

Proof

There are 2 steps to this proof:
First, we show that the arithmetic function
$f(n)={\sum }_{d\mid n}\phi (d)$
is multiplicative. Let $m$ and $n$ be coprime positive integers. Then the positive divisors of $m$ are the numbers of the form $de$, where $d,e$ are positive divisors of $m,n$ respectively, and $(d,e)=1$. This
$f(mn)={\sum }_{d\mid m}{\sum }_{e\mid n}\phi (de)={\sum }_{d\mid m}{\sum }_{e\mid n}\phi (d)\phi (e)=f(m)f(n)$
So $f$ is multiplicative.
It remains to prove that $f(p^k)=p^k$ for any prime power $p^k$. We compute:
$f(p^k)={\sum }_{j=1}^k\phi (p^j)=1+(p-1)+(p^2-p)+...+(p^k-p^{k-1})=p^k$