# 5.2 : Linear Congruences Revisted

$$\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}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

The following theorem we stated in Chapter 4:

##### Theorem $$\PageIndex{1}) Let \(m \in \mathbb{Z}_+$$ and  $$a,b \in \mathbb{Z}$$, with $$a$$ be non-zero. Then

$$ax \equiv b(mod\, m)$$ has a solution if and only if $$\gcd(a,m) |b$$. Moreover, if $$x=x_0$$ is a particular solution to this congruence, then the set of all solutions is $$\{x \in \mathbb{Z} | x \equiv x_0(mod\, m)\}=\{x_0, x_0+\dfrac{m}{d}, x_0+\dfrac{2m}{d},\ldots, x_0+\dfrac{(d-1)m}{d}\}$$, where $$d=\gcd(a,m).$$

Let us learn how to use the theorem to solve linear congruence. Let $$m \in \mathbb{Z}_+$$ and  $$a,b \in \mathbb{Z}$$, with $$a$$ be non-zero. Consider the  linear congruence $$ax \equiv b(mod\, m)$$. Which is equivalent to $$m \mid ax- b \implies ax-b=my,\mbox{ for some} y \in \mathbb{Z} .$$ Thus solving linear congruence is equivalent to solving the linear Diophantine equation $$ax+my=b$$, for $$x, y \in \mathbb{Z}.$$

##### Example $$\PageIndex{1}$$

If possible,  solve $$2x \equiv 2 ( mod \,4 )$$.

###### Solution

Since $$\gcd(2,4)=2$$ and $$2\mid 2$$, $$2x \equiv 2 ( mod \,4 )$$  has a solution. Moreover, the set of all solutions is given by $$\{x\in \mathbb{Z}|x\equiv x_0 ( mod \,4 )\}$$ . To find a particular solution we consider the corresponding Diophantine equation $$2x+4y=2.$$ Since $$2(-1)+4(1)=2,$$ one particular solution is given by $$x_0=-1.$$  Then all the solutions to the Diophantine equation $$2x+4y=2$$ are of the form $$x=-1+2k, y=1-4k, k\in \mathbb{Z}.$$

Thus $$x ( mod\,4)=-1,1$$.

Since $$(-1)(mod \,4)\equiv 3$$ and $$1 (mod \,4)\equiv 1$$, the set of all solutions are all integers  $$x$$ such that $$x \equiv 3 (mod \,4)$$ or $$x \equiv 1 (mod \,4)$$.

This page titled 5.2 : Linear Congruences Revisted is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Pamini Thangarajah.