Linear Congruences

Linear Congruence

Definition

A relation in the form

is called a linear congruence on the variable . A solution to such a linear congruence is an integer such that

Linear Congruence Theorem (LCT)

Theorem

For all integers and , with not zero, the linear congruence:

has a solution if and only if , where .

Moreover, if is a one solution, then the set of all solutions is:

or, equivalently

(See divisibility, GCD, set builder notation, Linear Diophantine Equations)

Proof

From the definitions of congruence and divisibility, is a solution to the congruence where there exists an integer such that such that .
Rearranging slightly, this means that the linear Diophantine equation has the solution and .
is a solution to the linear congruence if and only if there exists an integer such that and is a solution to the linear Diophantine equation .
From LDET 1, with , the congruence has a solution if and only if .

Moreover, if is one particular solution, then by LDET 2, with tells us that the set of all solutions to the congruence is given by

We can also express the elements of is terms of congruence relations modulo , as follows:

Each element can be written uniquely in the form , for some integer .

Now, dividing by , by the division algorithm, we can write uniquely in the form , for some integer quotient and remainder , where .
Hence, we can write uniquely in the form:

where and
For each fixed , the set of in the form , is precisely the set of such that , so we obtain:

Remark

This proof tells us that to find all solutions to the linear congruence relation , we should consider the corresponding linear Diophantine equation

Examples

Example

If possible, solve the linear congruence

Since , and , there is no solution to the equation by LCT.

Example

If possible, solve the linear congruence

Since , and , there is a solution by LCT.

Since , the set of all solutions is given by the set of all integers such that , where is some particular solution to the congruence.
To find a particular, we consider the corresponding linear Diophantine equation .
Applying the Extended Euclidean Algorithm:

			EA

We obtain .
To obtain on the right side, multiply the whole equation by :

thus one particular solution is given by . But , hence the set of solutions to the linear congruence is given by all integers such that

Example

If possible, solve the linear congruence

Since , and , there is a solution by LCT.

Moreover, since , the set of all solutions is given by the set of all integers such that or , where is some particular solution to the congruence.
Since is a small modulus we can simply check all possibilities:

Observe, that when or , .
Hence the solutions are all integers such that or