Modular Arithmetic

Printable View

September 19th 2012, 07:29 AM
Patriotx12

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.
September 19th 2012, 08:18 AM
HallsofIvy

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.
September 19th 2012, 11:02 AM
Soroban

Re: Modular Arithmetic

Hello, Patriotx121

Here is an algebraic (very primitive) solution.

Quote:

$\text{Find the solution set for: }\,140x \:\equiv\:133\text{ (mod 301)}$

$\text{We have: }\:140x \:=\:133 + 301a\:\text{ for some integer }a.$

$\text{Solve for }x\!:\;\;x \:=\:\frac{301a + 133}{140} \:=\:2a + \frac{21a + 133}{140} \:=\:2a + \frac{3a+19}{20}$ .[1]

$\text{Since }x\text{ is an integer, }(3a+19)\text{ must be a multiple of 20.}$
. . . $3a + 19 \:=\:20b$

$\text{Solve for }a\!:\;\;a \:=\:\frac{20b-19}{3} \:=\:6b-6+\frac{2b-1}{3}$ .[2]

$\text{Since }a\text{ is an integer, }(2b-1)\text{ must be a multiple of 3.}$
. . . $2b-1 \:=\:3c$

$\text{Solve for }b\!:\;\;b \:=\:\frac{3c+1}{2} \:=\:c + \frac{c+1}{2}$ .[3]

$\text{We see that }c\text{ must be odd: }\,c \:=\:2k-1$

$\text{Substitute into }{\color{blue}[3]}\!:\;b \:=\:(2k-1) + \frac{(2k-1)+1}{2} \quad\Rightarrow\quad b\:=\:3k-1$

$\text{Substitute into }{\color{blue}[2]}\!:\;a \:=\:6(3k-1) - 6 + \frac{2(3k-1)-1}{3} \quad\Rightarrow\quad a \:=\:20k-13$

$\text{Substitute into }{\color{blue}[1]}\!:\;x \:=\:2(20k-13) + \frac{3(20k-13) + 19}{20}\:=\:43k-27$

$\text{Therefore, the solution set is: }\:\big\{\,x\,\big|\,x\:=\:43k\!-\!27,\;k\in I \big\}$