Linear Congruences

What is a linear congruence?

A linear congruence in the variable x is an equation of the form: $$ ax \equiv b \mod n $$

Here, a and b are integers (a, b ∈ Z), and n is a natural number (n ∈ N).

Why are linear congruences useful?

They are particularly useful because they allow us to solve linear equations using modular arithmetic.

Note: Any linear congruence of the form $$ ax \equiv b \mod n $$ is equivalent to the linear equation $$ ax + ny = b $$

A Practical Example

Consider the following congruence modulo 3:

$$ 4x \equiv 7 \mod 3 $$

This is equivalent to the linear equation:

$$ 4x + 3y = 7 $$

Whether this equation has integer solutions for x and y remains to be seen.

Finding Integer Solutions to a Linear Congruence

When do integer solutions exist?

A linear congruence $$ ax \equiv b \mod n $$ has at least one integer solution if and only if the greatest common divisor of a and n (gcd(a, n)) divides b: $$ \gcd(a, n) \mid b $$

If gcd(a, n) divides b, the congruence is said to be solvable or consistent.

A practical example

Let's go back to the previous congruence:

$$ 4x \equiv 7 \mod 3 $$

The greatest common divisor of (a, n) is 1:

$$ \gcd(4,3) = 1 $$

Since 1 is also a divisor of b = 7:

$$ 1 \mid 7 $$

It follows that the congruence has integer solutions.

For instance, x = 1 is a solution:

$$ 4x \equiv 7 \mod 3 \\ 4(1) \equiv 7 \mod 3 \\ 4 \equiv 7 \mod 3 \\ 1 \equiv 1 \mod 3 $$

Since the congruence is consistent, the corresponding linear equation $$ 4x + 3y = 7 $$ also has integer solutions.

Once we find a solution to the congruence, we can determine the integer solutions of the linear equation.

Note: The linear congruence $$ 4x \equiv 7 \mod 3 $$ is equivalent to the equation $$ 4x + 3y = 7 $$. Since we know that x = 1 is a solution to the congruence, we can solve for y in the equation: $$ 4(1) + 3y = 7 \\ 3y = 7 - 4 \\ y = 1 $$ Thus, the equation has an integer solution at x = 1 and y = 1. $$ 4x + 3y = 7 \\ 4(1) + 3(1) = 7 $$

How many integer solutions are there?

A solvable congruence $$ ax \equiv b \mod n $$ has exactly d = gcd(a, n) distinct integer solutions modulo n, given by: $$ x_0 + k \frac{n}{d} $$ where k is an integer ranging from 0 to d-1.

Here, \( x_0 \) is a particular solution to the congruence \( ax_0 \equiv b \).

All other integer solutions are congruent to these d solutions modulo n.

Note: If \( \gcd(a, n) = 1 \), then the congruence has exactly one solution.

Example

Consider the following linear congruence:

$$ 24x \equiv 21 \mod 9 $$

First, we simplify the coefficients modulo 9:

$$ 6x \equiv 3 \mod 9 $$

Note: The coefficient 6 comes from the remainder of 24 divided by 9, while 3 comes from the remainder of 21 divided by 9.

The congruence has integer solutions because the greatest common divisor \( \gcd(6,9) = 3 \) divides \( b = 3 \).

$$ \gcd(6,9) = 3 \mid 3 $$

Since \( \gcd(6,9) = 3 \), the congruence has three distinct solutions.

The first integer solution, \( x_0 \), is \( x = 2 \):

$$ 6x \equiv 3 \mod 9 \\ 6(2) \equiv 3 \mod 9 \\ 12 \equiv 3 \mod 9 \\ 3 \equiv 3 \mod 9 $$

Note: The congruence \( 12 \equiv 3 \mod 9 \) holds because 12 divided by 9 leaves a remainder of 3.

Once we find \( x_0 \), we use the formula with \( k = 1 \) to determine the second solution, \( x_1 = 5 \):

$$ x_1 = x_0 + k \frac{n}{d} \\ x_1 = 2 + 1 \frac{9}{3} \\ x_1 = 2 + 3 \\ x_1 = 5 $$

Verification: Substituting \( x = 5 \) into the congruence: $$ 6x \equiv 3 \mod 9 \\ 6(5) \equiv 3 \mod 9 \\ 30 \equiv 3 \mod 9 \\ 3 \equiv 3 \mod 9 $$

Now, increasing \( k \) to 2, we find the third solution, \( x_2 = 8 \):

$$ x_2 = x_0 + k \frac{n}{d} \\ x_2 = 2 + 2 \frac{9}{3} \\ x_2 = 2 + 6 \\ x_2 = 8 $$

Verification: Substituting \( x = 8 \) into the congruence: $$ 6x \equiv 3 \mod 9 \\ 6(8) \equiv 3 \mod 9 \\ 48 \equiv 3 \mod 9 \\ 3 \equiv 3 \mod 9 $$

Since \( k = d - 1 \), where \( d = 3 \) is the gcd, we stop here.

The distinct solutions to the congruence \( 6x \equiv 3 \mod 9 \) are:

$$ x_0 = 2 \\ x_1 = 5 \\ x_2 = 8 $$

These solutions are distinct because they yield different remainders when divided by 9:

$$ 2 \mod 9 \neq 5 \mod 9 \neq 8 \mod 9 $$

These distinct solutions allow us to determine the integer solutions of the linear equation corresponding to the congruence:

$$ 6x + 9y = 3 $$

Verification: Substituting \( x = 2 \), we find \( y = -1 \): $$ 6x + 9y = 3 \\ 6(2) + 9y = 3 \\ 12 + 9y = 3 \\ y = -1 $$ Substituting \( x = 5 \), we find \( y = -3 \): $$ 6x + 9y = 3 \\ 6(5) + 9y = 3 \\ 30 + 9y = 3 \\ y = -5 $$ Substituting \( x = 8 \), we again find \( y = -5 \): $$ 6x + 9y = 3 \\ 6(8) + 9y = 3 \\ 48 + 9y = 3 \\ y = -5 $$

Of course, there are infinitely many integer solutions for \( x \), but they are all congruent to the first three.

Verification: Another solution to \( 6x \equiv 3 \mod 9 \) is \( x = 11 \) with \( k = 3 \): $$ x_3 = x_0 + k \frac{n}{d} \\ x_3 = 2 + 3 \frac{9}{3} \\ x_3 = 2 + 9 \\ x_3 = 11 $$ However, 11 is congruent to 2 modulo 9: $$ 11 \equiv 2 \mod 9 \\ 2 \equiv 2 \mod 9 $$ because 11 divided by 9 leaves a remainder of 2.

And so on.