Definition:Linear Congruence

Definition

A linear congruence is a polynomial congruence of the form:

$a_0 + a_1 x \equiv 0 \pmod n$

That is, one where the degree of the integral polynomial is $1$.

Also presented as

A linear congruence is frequently encountered in the form:

$a x \equiv b \pmod n$

where $x$ is an unknown integer.

Examples

Example: $2 x \equiv 7 \pmod {18}$

The linear congruence:

$2 x \equiv 7 \pmod {18}$

has no solution in $\Z$.

Example: $15 x \equiv 6 \pmod {18}$

The linear congruence:

$15 x \equiv 6 \pmod {18}$

has $3$ solutions:

$x = 4, 10, 16$

Example: $7 x \equiv 8 \pmod {30}$

The linear congruence:

$7 x \equiv 8 \pmod {30}$

has the unique solution:

$x = 14$

Also see

• Results about linear congruences can be found here.

Sources

• 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): linear congruence
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): linear congruence