$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 4.5: Linear Congruences

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

A linear congruence  in one variable $$x$$ is of the  form $$ax \equiv b(mod \, m)$$,  where $$a,b \in \mathbb{Z}$$ and $$m \in \mathbb{Z_+}$$. This form of a linear congruence has at most $$m$$ solutions.

Example $$\PageIndex{1}$$

Solve $$x \equiv 6 ( mod \,11 )$$.

Solution

Possible solutions are $$0, 1,2, \ldots, 10$$. The only solution is $$6$$.

Example $$\PageIndex{2}$$

Solve $$2x \equiv 3 ( mod \,7 )$$.

Solution

The only solution is $$5$$.

Example $$\PageIndex{3}$$

Solve $$3x \equiv 1 ( mod \,8 )$$.

Solution

This congruence has no solution.

Example $$\PageIndex{4}$$

Solve $$2x \equiv 2 ( mod \,4 )$$.

Solution

The solutions are $$1$$ and $$3$$.

The following theorems give a criterion for the solvability of $$ax \equiv b(mod \, m)$$.

Theorem $$\PageIndex{1}$$

If $$\gcd(c,m)=1$$ and $$ac \equiv bc (mod\, m)$$ then $$a \equiv b (mod\, m)$$

Proof

Add proof here and it will automatically be hidden

Theorem $$\PageIndex{2}$$

If $$\gcd(a,m)=1$$ then $$ax \equiv b(mod \, m)$$ has a unique solution.

Proof

Add proof here and it will automatically be hidden

Theorem $$\PageIndex{3}$$

$$ax \equiv b(mod\, m)$$ has a  solution if and only if $$\gcd(a,m) |b$$.

Proof

Add proof here and it will automatically be hidden

## The Chinese Remainder Theorem

Theorem $$\PageIndex{4}$$

Let $$a, b \in \mathbb{Z}$$ and $$n,m \in \mathbb{N}$$ such that $$\gcd(n,m) = 1$$. Then there exists $$x \in \mathbb{Z}$$ such that $$x \equiv a(mod\, n)$$ and $$x \equiv b(mod\, m)$$. Moreover $$x$$ is unique modulo $$mn$$.

Example $$\PageIndex{5}$$

Solve $$x \equiv 2 (mod\, 3)$$ and $$x \equiv 3 (mod\, 5)$$.

Solution

Since $$x \equiv 2 (mod\, 3)$$, the possible solutions are $$2, 5, 8, 11, 15,$$.

Since $$x \equiv 3 (mod\, 5)$$, the possible solutions are $$3, 8, 13,$$.

Then $$x=8$$. Since any $$y$$ such that $$y \equiv 8 (mod\, 15)$$ are also  solutions, we have $$23, 38, \cdots$$