![\"24x7](\"https:\/\/www.intmath.com\/includes\/images\/tutor_chat_ad_banner.png\")
<\/a><\/p>\nDifferent Methods to Solve Linear Congruences<\/h2>\n
You can use several methods to solve linear congruences. The most commonly used methods are\u00a0the Euclidean Algorithm Method and the Euler's Method.<\/p>\n
Example:<\/strong>\u00a0Solve the linear congruence ax\u00a0= b (mod m)<\/p>\n Solution:<\/strong>\u00a0ax = b\u00a0(mod m) _____\u00a0(1)<\/p>\n a, b, and m\u00a0are\u00a0integers such that m\u00a0> 0 and c\u00a0= (a, m).<\/p>\n If c\u00a0cannot divide b, the linear congruence\u00a0ax = b\u00a0(mod m) lacks a solution.<\/p>\n If c\u00a0can divide b, the congruences ax = b(mod M) has an incongruent solution for modulo m.<\/p>\n As mentioned, ax = b\u00a0(mod m) is equal to ax - my = b. If we apply Theorem 19, you realize that c\u00a0cannot divide b; thus, it is impossible to get a solution for the equation ax - my = b.<\/p>\n Alternatively, if c\u00a0can divide b, it implies that there are several solutions whose variable is x\u00a0denoted by x\u00a0= x0 + (m\/c)t _____ (2)<\/p>\n Thus, the values of x\u00a0become the solution for the congruence ax = b\u00a0(mod m). You can now easily find the number of all the incongruent solutions.<\/p>\n Assuming the two solutions are incongruent such that:<\/p>\n x0 + (m\/c)t1 = x0 + (m\/c)t2 \u00a0(mod m) _____ (3)<\/p>\n (m\/c)t1 = (m\/c)t2 (mod m) _____ (4)<\/p>\n You now realize that (m, m\/c) = m\/c<\/p>\n Thus t1 = t2 (mod c) _____ (5)<\/p>\n You now have a set of incongruent solutions given by X = X0 + (M\/C)T, where T is given as modulo C.<\/p>\n Mathematically, if C = (A, M) = 1, there is always a definite unique solution for modulo M in the linear congruence AX = B(mod M).<\/p>\n 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\u00a0and b, the d\u00a0divides the reminder (r). This remainder (r) results from dividing the smaller of a\u00a0and b\u00a0into the larger.<\/p>\n The Euclidean Algorithm Method allows you to\u00a0find the middle ground pathways of prime numbers while solving linear congruences.<\/p>\n Example:<\/strong>\u00a0Solve the linear congruence 3x\u00a0= 12 (mod 6)<\/p>\n Solution:<\/strong><\/p>\n 3x\u00a0= 12 (mod 6)<\/p>\n (3, 6) = 3 and 3\/12<\/p>\n Thus, you get three incongruent solutions for mod 6.<\/p>\n You should use the Euclidean Algorithm Method to find the solution for the resultant linear diophantine equation 3x\u00a0- 6y= 12 to give you x0 = 0.<\/p>\n The three incongruent solutions are given by:<\/p>\n x1\u00a0= 6 (mod 6)<\/p>\n x1 = 6+2 = 2 (mod 6)<\/p>\n x2 = 6+4 = 4 (mod 6)<\/p>\n The GCD of 24 and 16 is 8.<\/p>\n Thus;\u00a024 = 1(16) + 8<\/p>\n Therefore the remainder is 8 when you divide 24 by 16, which is divisible by 8.<\/p>\n To better understand how to use the Euclidean Algorithm Method, we will use the equation 11x =\u00a01 mod 23.<\/p>\n Example:<\/strong>\u00a0Solve the Linear Congruence 11x\u00a0= 1 mod 23<\/p>\n Solution:<\/strong>\u00a0Find the Greatest Common Divisor of the algorithm.<\/p>\n 23 = 2(11) +1<\/p>\n 11 = 1(11) + 0<\/p>\n Therefore the GCD is 1.<\/p>\n You can see from the equation that 1 = (1)(23) + (-2)11\u00a0(mod 23)<\/p>\n (-2)(11) =\u00a01 mod 23<\/p>\n Thus, x\u00a0= -2<\/p>\n To write the answer as the value from 0 to 22, you realize that -2 = 21 mod 23; thus, the solution is x = 21.<\/p>\n Example:<\/strong>\u00a0Consider the linear congruence\u00a016x = 5 mod 29<\/p>\n Solution:\u00a0<\/strong><\/p>\n First, solve the congruence 16x = 1 mod 29<\/p>\n 29 = 1(16) +13 (2)<\/p>\n 16 = 1(13) + 3 (3)<\/p>\n 13 = 4(3) + 1 (4)<\/p>\n Hence you get:<\/p>\n 1 = 1(13) + (-4)(3).<\/p>\n Substitute in the equation 1 = 1(13) + (-4)(3) using the fact that from (3), 3 = 16 -1(13) you get:<\/p>\n 1 = 1(13) + (-4)(16-1(13)) = 5(13) + (-4)(16) (5)<\/p>\n You can now use (2) with the knowledge that 13 = 29 -1(16) to substitute for 13 in (5).<\/p>\n 1 = 5(29-1(16)) + (-4)(16) = (-9)(16) +(5)(29)<\/p>\n Therefore the last equation mod 29 results to:<\/p>\n (-9)(16) =\u00a01 modulo 29<\/p>\n The value of x\u00a0is thus -9, which in this case, is congruent to modulo 29 to 30.<\/p>\n It doesn't end here, though.<\/p>\n 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 =\u00a05 modulo 29 is 13.<\/p>\n Lastly, verify that 16(13)-5 will leave a zero remainder when you divide it by 29.<\/p>\n 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.<\/p>\n It is important to note that there exists a close relationship between linear diophantine equations and linear congruences.<\/p>\n 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.<\/p>\n Also, the equation a = b + nt can be converted to modulo n:<\/p>\n a = b + nt<\/p>\n a = b + 0t mod n<\/p>\n Hence a = b mod n<\/p>\n You can easily convert the linear congruence 13x = 4 mod 37 to a diophantine equation 13x = 4 + 37y.<\/p>\n 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.<\/p>\n Solve the following diophantine linear equation.<\/p>\n 23x + 49y = 102<\/p>\n 23x + 49y = 102 _____\u00a0(1)<\/p>\n First, change the diophantine equation into a linear congruence. You realize from the equation that mod 23 is the smallest coefficient.<\/p>\n 49y = 101 mod 23<\/p>\n Now simplify the equation to get:<\/p>\n 3y = 10 mod 23<\/p>\n Now use Euler's Method to change the equation into equality.<\/p>\n 3y +10 + 23a _____\u00a0(2)<\/p>\n Now reduce the equation to congruence mod 3, which is the smallest coefficient.<\/p>\n 0 = 10 + 2a mod 3 or 0 = equiv 1+ 2a mod 3.<\/p>\n Simplify this further to an equation to get:<\/p>\n 0 = 1 + 2a + 3b _____\u00a0(3)<\/p>\n Before we go to the next step, take note of the introduction of a new variable (b).<\/p>\n Next, let us take mode 2 to get:<\/p>\n 0 = 1 +3b mod 2<\/p>\n Simplify further to get:<\/p>\n 0 = 1 + b mod 2<\/p>\n This results in:<\/p>\n b \u22121 mod 2<\/p>\n Now that you have b mod 2 pick any b integer satisfying this congruence, for example, b = -1.<\/p>\n Go back to the x equation (2) to get:<\/p>\n 1 + 2a + 3(\u22121) = 0.<\/p>\n 1 + 2a \u2212 3 = 0<\/p>\n Next, go to the y in equation (2) to get:<\/p>\n 3y = 10 + 23a = 10 + 23 = 33<\/p>\n Therefore y = 11<\/p>\n Go back to the original equation (1) to get:<\/p>\n 23x + 49 11 = 102<\/p>\n 23x = 102 \u2212 539 = 437<\/p>\n x = 19<\/p>\n Therefore the final solution is:<\/p>\n x = 19<\/p>\n y = 11<\/p>\n Understanding the Euclidean Algorithm and Euler's Methods makes solving linear congruences less complicated. The two methods allow us to extend modular arithmetic beyond\u00a0simple addition, multiplication, and subtraction to give room for division. It has cemented a fundamental relationship between integer linear combination of numbers and their GCD.<\/p>\n Take your time to learn the two methods and start solving linear congruences with ease.<\/p>\n <\/p>\nSolving Linear Congruences Using The Euclidean Algorithm Method<\/h3>\n
Illustration<\/h4>\n
Examples<\/h4>\n
<\/a><\/p>\nHow to Solve Linear Congruences Using Euler's Method<\/h3>\n
Example:<\/h4>\n
Example:<\/h4>\n
Solution:<\/h4>\n
Final Thoughts<\/h2>\n