Results 1 to 3 of 3

Math Help - Modular Arithmetic

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    USA
    Posts
    2

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,417
    Thanks
    1330

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,689
    Thanks
    617

    Re: Modular Arithmetic

    Hello, Patriotx121

    Here is an algebraic (very primitive) solution.


    \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\}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 8th 2011, 10:45 AM
  2. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 21st 2011, 03:40 AM
  3. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: June 29th 2010, 07:51 PM
  4. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 28th 2010, 05:08 AM
  5. Modular arithmetic
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: September 20th 2008, 09:08 AM

Search Tags


/mathhelpforum @mathhelpforum