How To Solve Linear Congruences

Numbers are congruent if they have a property that the difference between them is integrally divisible by a number (an integer). The number is called the modulus, and the statement is treated as congruent to the modulo. Mathematically, this can be expressed as b = c (mod m)

Generally, a linear congruence is a problem of finding an integer x that satisfies the equation ax = b (mod m). Thus, a linear congruence is a congruence in the form of ax = b (mod m), where x is an unknown integer. In a linear congruence where x0 is the solution, all the integers x1 are x1 = x0 (mod m).

Different Methods to Solve Linear Congruences

You can use several methods to solve linear congruences. The most commonly used methods are the Euclidean Algorithm Method and the Euler's Method.

Example: Solve the linear congruence ax = b (mod m)

Solution: ax = b (mod m) _____ (1)

a, b, and m are integers such that m > 0 and c = (a, m).

If c cannot divide b, the linear congruence ax = b (mod m) lacks a solution.

If c can divide b, the congruences ax = b(mod M) has an incongruent solution for modulo m.

As mentioned, ax = b (mod m) is equal to ax - my = b. If we apply Theorem 19, you realize that c cannot divide b; thus, it is impossible to get a solution for the equation ax - my = b.

Alternatively, if c can divide b, it implies that there are several solutions whose variable is x denoted by x = x0 + (m/c)t _____ (2)

Thus, the values of x become the solution for the congruence ax = b (mod m). You can now easily find the number of all the incongruent solutions.

Assuming the two solutions are incongruent such that:

x0 + (m/c)t1 = x0 + (m/c)t2  (mod m) _____ (3)

(m/c)t1 = (m/c)t2 (mod m) _____ (4)

You now realize that (m, m/c) = m/c

Thus t1 = t2 (mod c) _____ (5)

You now have a set of incongruent solutions given by X = X0 + (M/C)T, where T is given as modulo C.

Mathematically, if C = (A, M) = 1, there is always a definite unique solution for modulo M in the linear congruence AX = B(mod M).

Solving Linear Congruences Using The Euclidean Algorithm Method

The Euclidean Algorithm Method is one of the simplest methods of solving linear congruences. The technique works so that if d is the Greatest Common Divisor of two positive integers, say a and b, the d divides the reminder (r). This remainder (r) results from dividing the smaller of a and b into the larger.

The Euclidean Algorithm Method allows you to find the middle ground pathways of prime numbers while solving linear congruences.

Example: Solve the linear congruence 3x = 12 (mod 6)

Solution:

3x = 12 (mod 6)

(3, 6) = 3 and 3/12

Thus, you get three incongruent solutions for mod 6.

You should use the Euclidean Algorithm Method to find the solution for the resultant linear diophantine equation 3x - 6y= 12 to give you x0 = 0.

The three incongruent solutions are given by:

x1 = 6 (mod 6)

x1 = 6+2 = 2 (mod 6)

x2 = 6+4 = 4 (mod 6)

Illustration

The GCD of 24 and 16 is 8.

Thus; 24 = 1(16) + 8

Therefore the remainder is 8 when you divide 24 by 16, which is divisible by 8.

Examples

To better understand how to use the Euclidean Algorithm Method, we will use the equation 11x = 1 mod 23.

Example: Solve the Linear Congruence 11x = 1 mod 23

Solution: Find the Greatest Common Divisor of the algorithm.

23 = 2(11) +1

11 = 1(11) + 0

Therefore the GCD is 1.

You can see from the equation that 1 = (1)(23) + (-2)11 (mod 23)

(-2)(11) = 1 mod 23

Thus, x = -2

To write the answer as the value from 0 to 22, you realize that -2 = 21 mod 23; thus, the solution is x = 21.

Example: Consider the linear congruence 16x = 5 mod 29

Solution: 

First, solve the congruence 16x = 1 mod 29

29 = 1(16) +13 (2)

16 = 1(13) + 3 (3)

13 = 4(3) + 1 (4)

Hence you get:

1 = 1(13) + (-4)(3).

Substitute in the equation 1 = 1(13) + (-4)(3) using the fact that from (3), 3 = 16 -1(13) you get:

1 = 1(13) + (-4)(16-1(13)) = 5(13) + (-4)(16) (5)

You can now use (2) with the knowledge that 13 = 29 -1(16) to substitute for 13 in (5).

1 = 5(29-1(16)) + (-4)(16) = (-9)(16) +(5)(29)

Therefore the last equation mod 29 results to:

(-9)(16) = 1 modulo 29

The value of x is thus -9, which in this case, is congruent to modulo 29 to 30.

It doesn't end here, though.

Now that you know 16(20) is congruent to 1 mod 29, multiply both sides of the equation by 5 to get 100(16), a congruent to modulo 29. And because 100 is congruent to 13 mod 29, the solution to the linear congruence 16x = 5 modulo 29 is 13.

Lastly, verify that 16(13)-5 will leave a zero remainder when you divide it by 29.

How to Solve Linear Congruences Using Euler's Method

This method applies to solve a linear diophantine equation. A linear diophantine equation is any equation expressed as ax + by = c. Euler's method applies the knowledge of solving linear diophantine equations to solve linear congruences.

It is important to note that there exists a close relationship between linear diophantine equations and linear congruences.

This is so because in the equation a = b (mod n), n divides (a-b) or a-b = nt for some t, or a= b + nt.

Also, the equation a = b + nt can be converted to modulo n:

a = b + nt

a = b + 0t mod n

Hence a = b mod n

Example:

You can easily convert the linear congruence 13x = 4 mod 37 to a diophantine equation 13x = 4 + 37y.

Solving linear congruences using Euler's Method involves changing congruences to equations. You then change the equation to a congruence modulo using the smallest coefficient.

Example:

Solve the following diophantine linear equation.

23x + 49y = 102

Solution:

23x + 49y = 102 _____ (1)

First, change the diophantine equation into a linear congruence. You realize from the equation that mod 23 is the smallest coefficient.

49y = 101 mod 23

Now simplify the equation to get:

3y = 10 mod 23

Now use Euler's Method to change the equation into equality.

3y +10 + 23a _____ (2)

Now reduce the equation to congruence mod 3, which is the smallest coefficient.

0 = 10 + 2a mod 3 or 0 = equiv 1+ 2a mod 3.

Simplify this further to an equation to get:

0 = 1 + 2a + 3b _____ (3)

Before we go to the next step, take note of the introduction of a new variable (b).

Next, let us take mode 2 to get:

0 = 1 +3b mod 2

Simplify further to get:

0 = 1 + b mod 2

This results in:

b −1 mod 2

Now that you have b mod 2 pick any b integer satisfying this congruence, for example, b = -1.

Go back to the x equation (2) to get:

1 + 2a + 3(−1) = 0.

1 + 2a − 3 = 0

Next, go to the y in equation (2) to get:

3y = 10 + 23a = 10 + 23 = 33

Therefore y = 11

Go back to the original equation (1) to get:

23x + 49 11 = 102

23x = 102 − 539 = 437

x = 19

Therefore the final solution is:

x = 19

y = 11

Final Thoughts

Understanding the Euclidean Algorithm and Euler's Methods makes solving linear congruences less complicated. The two methods allow us to extend modular arithmetic beyond simple addition, multiplication, and subtraction to give room for division. It has cemented a fundamental relationship between integer linear combination of numbers and their GCD.

Take your time to learn the two methods and start solving linear congruences with ease.

 

 

Be the first to comment below.