Linear Congruences

linear congruence equations having the form

$ax \equiv b \pmod {n}$

If $x$ is a solution and $x\equiv x' \pmod{n}$, then $ax \equiv ax' \equiv b$ and so $x'$ is also a solution; thus the solution ( if they exist) form a union of congruence classes.Now $ax \equiv b \pmod {n}$ if and only if  $ax-b$ is a multiple of $n$.So $x$ is a solution of this linear congruence if and only if there is integer $y$ such that $x$ and $y$ satisfy the linear Diophantine equation $ax+ny=b$

Theorem:

if $d=gcd(a,n)$ , then the linear congruence 

$$ax \equiv b \pmod {n}$$

has a solution if and only if $d$ divides $b$.if $d$ does divide $b$, and if $x_0$ is any solution, then the general solution is given by

$$x=x_0+\frac{n.t}{d}$$, where $t \in \mathbb{Z}$; in particular, the solutions form exactly $d$ congruence classes (mod n), with representatives

$$x=x_0,x_0+\frac{n}{d},x_0+\frac{2n}{d},\cdots,x_0+\frac{(d-1)n}{d}$$

Example:

Consider the congruence 

$$10x \equiv 6  \pmod{12}$$

$gcd(a,n)=gcd(10,12)=2$

$gcd(a,n)|b=>2|6$, so there are two classes of solutions. We can take $x_0=3$ as a particular solution, so the general solution has the form

$$x=x_0+\frac{nt}{d}=3+\frac{12t}{2}=3+6t$$

where $t \in \mathbb{Z}$. These solutions form two congruence classes $[3]$ and $[9]$ $\pmod{12}$ with representatives $x_0=3$ and $x_0+n/d=9$; equivalently the form a single congruent class $[3] \pmod{6}$

Example:

Consider the congruence $10x \equiv 3 \pmod{12}$. Here $gcd(10,12)=2$ which does not divide 3.So there are no solutions.(This can be seen directly: the elements of the congruence class $[3]$ in $\mathbb{Z}_{12}$ are odd, whereas any elements of $10[x]$ must be even).

Corollary:

if $gcd(a,n)=1$, then the solutions $x$  of the linear congruence $ax \equiv b \pmod{n}$ form a single congruence class $\pmod{n}$

Example:

Consider the congruence

$$7x \equiv 3 \pmod{12}$$

Here $a=7$ and $n=12$ and since $gcd(7,12)=1$, they are coprime and there is a single class of solutions; this is the class $[x]=9$, since $7 \times 9=63 \equiv 3 \pmod{12}$

 Note: In the above examples  $n$ is small and it is feasible to find the all solutions of a congruence $ax \equiv b \pmod{n}$ by inspection: one can simply calculate $ax$ for each of the $n$ elements $x$ of a complete set of residues $\pmod {n}$, and see which of these products are congruent to $b$.When $n$ is larger, however, a more efficient method is needed for solving linear congruences.

Lemma:

1)Let $m$ divide $a$,$b$, and $n$ and let $a'=a/m,b'=b/m$ and $n'=n/m$; then 

$ax \equiv b \pmod {n}$, if and only $a'x \equiv b' \pmod {n'}$

2)Let $a$ and $n$ be coprime, let $m$ divide $a$ and $b$ and let $a'=a/m$ and $b'=b/m$; then

$ax \equiv b \pmod {n}$ if and only if $a'x \equiv b'  \pmod{n}$

Algorithm to Solve Linear Congruence

Step1: We calculate $d=gcd(a,n)$, and see whether $d$ divides $b$.If it does not, there are no solutions, so we stop.If it does, we go on to Step 2.

Step2: Since $d$ divides $a,b$ and $n$, as per lemma 1) implies that, we can replace the original congruence with

$$a'x \equiv b' \pmod {n'}$$

where $a'=a/d, b'=b/d$ and $n'=n/d$

Now $a'$ and $n'$ are coprime , so we can use lemma 2)

Step3:Now as per lemma 2) divide this new congruence through by $m=gcd(a',b')$, giving a congruence 

$$a''x \equiv b'' \pmod {n'}$$

where $a''=a'/m$ and $b''=b'/m$.Now $a''$ is coprime to both $b''$ and $n'$.If $a''=\pm 1$, then $x_0=\pm b''$ is the required solution.Otherwise goto step 4.

Step4:Noting that

$b''\equiv b'' \pm n' \equiv b'' \pm 2n' \equiv \ldots \pmod{ n'}$

we may be able to replace $b''$ with some congruent number $b'''=b''+kn'$such that $gcd(a'',b''')>1$; by applying Step3 to the congruence $a''x \equiv b''' (\mod n')$, we can gain reduce  $|a''|$. An alternative at this stage  is to multiply through by some suitably chosen constant $c$, giving $ca''x \equiv cb'' \pmod {n'}$; if $c$ is chosen so that the least absolute residue $a'''$ of $ca''$ satisfies $|a'''|<|a''|$, then we have reduced $|a''|$ to give a linear congruence $a'''x \equiv b'''x \pmod{n}$ with $b'''=cb''$.

A combination of  the methods in Step 4 will eventually reduce $a$ to $\pm 1$, in which case the solution $x_0$ can be read off; then the general solution can be found.

Example:

Consider the congruence $10x \equiv 6  \pmod {14}$

Step1 gives $gcd(10,14)=2$, which divides 6. So the solution do exist.if $x_0$ is the particular solution then the general solution is $x=x_0+(14/2)t=x_0+7t$, where $t \in \mathbb{Z}$. These form the congruence class $[x_0]$ and $[x_0+7]$ in $\mathbb{z}_{14}$

To find $x_0$ use step 2.divide the congruence by $gcd(10,14)=2$ to give 

$$5x \equiv 3 \pmod {7}$$

Since $gcd(5,3)=1$ step 3 has no effect.so we move on to step 4.Noting that $3 \equiv 10 \: mod( 7)$ ,with 10 divisible by 5, we replace the congruence with

$$5x=10 \pmod {7}$$
and then divide by 5 (which is coprime to 7) to give
$$x =2 \pmod {7}$$

Thus $x_0 = 2$ is a solution, so the general solution has the form
$$c=2+7t (t \in Z)$$

Example:

Consider the congruence

$$4x =13 \pmod {47}$$

Step 1 gives $gcd(4,47) = 1$, which divides 13, so the congruence has solutions.
If $x_0$ is any solution, then the general solution is $x = x_0 + 47t$ where $t \in Z$ forming a single congruence class $[x_0]$ in $\mathbb{Z}_{47}$.

Since $gcd(4, 47) = 1$, step 2 has no effect, so we move on to step 3. 

Since $gcd(4, 13)$ = 1, step 3 also has no effect,so we go to step 4.

We could now employ the method used in the previous example, but as an alternative we will illustrate the other technique described in step 4: 

noting that $$4 \times 12 \equiv 48 \equiv 1 \pmod {47}$$, we multiply by 12 to give 

$$48x \equiv 12 \times  13 \pmod {47}$$

that is,

$$x \equiv 3 \times 4 \times 13 \equiv 3 \times 52 \equiv3 \times 5 \equiv 15 \pmod {47}$$

Thus we can take $x_0 = 15$, so the general solution is $x= 15 + 47t$

Example: Solve the linear congruence $3x \equiv 2 \pmod{7}$.Check if a solution exists: 3 and 7 are coprime, so proceed.

Find the modular inverse: The modular inverse of 3 modulo 7 is 5 since 

$$3 \cdot 5 \equiv 1 \pmod{7}$$

Solve for $x \equiv 2 \cdot 5 \equiv 10 \equiv 3 \pmod{7}$. So, $x_0=3$ is the solution.$x=3+7t$ is the general solution.

Example:

Solve the linear congruence $4x \equiv 6 \pmod{10}$.Check if a solution exists: 4 and 10 are not coprime (they share a common divisor of 2). However, 6 is divisible by 2, so divide both sides by 2: $$2x \equiv 3 \pmod{5}$$

Find the modular inverse: The modular inverse of 2 modulo 5 is 3 since $2 \cdot 3 \equiv 1 \pmod{5}$

Solve for $x \equiv 3 \cdot 3 \equiv 9 \equiv 4 \pmod{5}$. So, $x_0=4$ ,is the solution.$x=4+5t$ is the general solution.