
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.

Re: Modular Arithmetic
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.

Re: Modular Arithmetic
Hello, Patriotx121
Here is an algebraic (very primitive) solution.
.[1]
. . .
.[2]
. . .
.[3]