5.2 : Linear Congruences Revisted

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)$.