Thread: Modular Arithmetic

I need help with the following problem:

Describe the solution set for the following linear congruence:

140x = 133 (mod 301) (That should be the congruence symbol, not equal symbol, just not sure how to put it in.)

I know how to find specific solutions, but only by making a table and the mod is too large to make a table. I know there are 7 solutions because the gcd of (140,301) is 7, but I'm not sure how to describe them.

140x= 133 (mod 301) is the same as saying 140x= 133+ 301n for some integer n. And that is the same as the diophantine equations 140x- 301n= 133. As you say, gcd(140, 301)= 7 so the left side of that equation is a multiple of 7 and that has a solution if and only if the right side is aso divisible by 7. Fortunately it is: 133= 7(19). Dividing the entire equation by 7, 20x- 43n= 19.

Use "Euclid's division algorithm" to solve that equation. 20 divides into 43 twice with remainder 3: 43- 2(20)= 3. 3 divides into 20 six times with remainder 2: 20- 6(3)= 2. 2 divides into 3 once with remainder 1: 3- 2= 1.
Replacing that 2 with "20 - 6(3)", 3- (20- 6(3)= 7(3)- 20= 1. Replacing that 3 with "43- 2(20)", 7(43- 2(20))- 20= 7(43)- 15(20)= 1. Multiplying each part by 19, 133(43)- 285(20)= 19.

That tells us that one solution to 20x- 43n= 19 is n= -133, x= -285. Of course, we want positive solutions, but it is easy to see that n= -133+ 20i, x= -285+ 42i is a solution for any integer i: 20(-285+ 42i)- 43(-133+ 20i)= -5700- 840i+ 5719- 840i= 19 and the "i" terms cancel. 20 divides into 133 between 6 and 7 times- i must be at least 7 to make n positive. 42 divides into 285 between 6 and 7 times also so taking i= 7, x= -285+ 42(7)= -285+ 294= 9. is a solution. Taking i= 8, x= -285+ 42(8)= -285+ 336= 71. As you say, there are 7 solutions. Taking i= 7, 8, 9, 10, 11, 12, 13 will give values of x between 0 and 301.

Hello, Patriotx121

Here is an algebraic (very primitive) solution.

.[1]


. . .

.[2]


. . .

.[3]