Results 1 to 10 of 10

Math Help - Solving Congruences

  1. #1
    Member diddledabble's Avatar
    Joined
    Jul 2009
    Posts
    80

    Solving Congruences

    If you are to solve for x in the congruence 7x=20(mod50)
    What is the easier way to do it without using a calculator or any other type of electronic device. I know you can add 7 to 20 until the number is divisible by 7 and then divide by 7 to reduce it to a solution but that takes a while. I need to figure out how to get it done in just a minute or two. Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    Quote Originally Posted by diddledabble View Post
    If you are to solve for x in the congruence 7x=20(mod50)
    What is the easier way to do it without using a calculator or any other type of electronic device. I know you can add 7 to 20 until the number is divisible by 7 and then divide by 7 to reduce it to a solution but that takes a while. I need to figure out how to get it done in just a minute or two. Thanks.
    You mean 50 (the modulus).

    For small moduli and (a,m) = 1, adding the modulus until cancellation is probably the best way to solve ax \equiv b \ (\text{mod } m). For this particular congruence, add the modulus once to 20 to get: 7x \equiv 70 \ (\text{mod } 50)

    Since (7, 50) = 1, you can 'divide' by 7 to get your solution.

    _____________

    For a more general case where (a,m) \neq 1, as long as (a,m) \mid b, then we can always use the Euclidean algorithm to find one solution modulo \tfrac{m}{(a,m)} and use it to find all solutions modulo m. Here's an example in this wiki entry: Linear congruence theorem
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jul 2009
    Posts
    111
    Thanks
    1

    Thumbs up @dibbledabble

    Well, I guess I have an easier method to solve this congruence equation.

    7x=20(mod50)

    The equation simply means that 7x, a multiple of 7, is 20 more than a multiple of 50 [By modulo logic]

    If we list down numbers which are 20 more than a multiple of 50, we get
    70, 120, 170, 220, 270, 320, 370, 420, and so on... From this which it is quite evident that 70, 420, 770, 1120... etc are multiples of 7 which are 20 more than multiples of 50.

    So, the smallest positive number is 70. 7x = 70 which means x = 10.
    In fact, 350n - 280 would be the general form for the number 7x.
    So, the general solution of x would be 50n - 40 where n can range from 1,2,3,.. and so on.

    Hope it helped,
    MAX
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517

    General theory

    An equation of the form
    ax\equiv b (mod n)
    has a solution if and only if gcd(a,n)|b.

    Here is how you do it in general when these requirements are met.

    Let d=gcd(a,n) and by assumption d|b \Rightarrow b=dk for some integer k. Then by the Euclidean Algorith, there exist integers s and t such that
    as+nt=d.

    We now multiply through by k to get.

    ask+ntk=dk=b

    reduce mod n to see
    a(sk)\equiv b (mod n).

    There is your x, namely, x=sk (mod n).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    7x7=49=-1 (mod 50)

    so -x=140 (mod 50)=-10 (mod 50)

    hence x=...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,654
    Thanks
    598
    Helo, diddledabble!

    Solve: . 7x \:\equiv\:20\text{ (mod 50)}
    Your "brute force" method is tedious, but it is commendable.
    It shows that you understand the congruence statement.
    Here is a primitive method . . .


    We have: . 7x \:\equiv\:20 \text{ (mod 50)}

    This means: . 7x - 20 \:=\:50a\;\text{ for some integer }a.

    Solve for x\!:\quad x \:=\:\frac{50a+20}{7} \quad\Rightarrow\quad x \:=\:7a + 2 + \frac{a+6}{7}

    Since x is an integer, a+6 must be divisible by 7.
    The first time this happens is a = 1.

    So we have: . x \;=\;7(1) + 2 + \frac{1+6}{7}\;=\;10

    Therefore: . x \:\equiv\:10\text{ (mod 50)}

    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jul 2009
    Posts
    111
    Thanks
    1

    Thumbs up @dibbledabble

    Hi,

    I think the solution offered by Soroban is the closest to the perfect procedure for your question. I guess mine was a bit too illustrative.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member diddledabble's Avatar
    Joined
    Jul 2009
    Posts
    80
    So using Soroban's method and a different congruence 35x=20(mod50) I get x=2(mod50) right?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Jul 2009
    Posts
    111
    Thanks
    1

    Smile Yes

    If you haven't checked already, values of 'x' such as 52 and 102 satisfy the equation as, in 52 * 35 = 1820
    = 1800 + 20
    = 36*50 + 20
    Similarly, 102*35 = 3570
    = 3550 +20
    = 71*50 + 50

    MAX
    Follow Math Help Forum on Facebook and Google+

  10. #10
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    Given the congruence ax \equiv b \ (\text{mod } m), if (a,m) \mid b, then there are (a,m) solutions exactly.

    So for the congruence 35x \equiv 20 \ (\text{mod } 50), we can see that there should be 5 solutions modulo 50.

    ___________

    Reduce your congruence: 5 \cdot 7x \equiv 5 \cdot 4 \equiv (\text{mod } 50) \ \Rightarrow \ 7x \equiv 4 (\text{mod } \tfrac{50}{(5, 50)}) \ \Leftrightarrow \ 7x \equiv 4 \ (\text{ mod} 10)

    Quickly by inspection, by adding the modulus to 4, we get: 7x \equiv 14 \ (\text{mod } 10)

    which is satisfied by all integers such that x \equiv 2 \ (\text{mod } 10) \ \ (\star).

    Returning to our original congruence, all 5 solutions are least residues that satisfy (\star). Therefore, modulo 50: 2, 12, 22, 32, 42 are all solutions.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Solving Simultanteous Congruences
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 7th 2010, 03:05 PM
  2. solving linear congruences...please help
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 30th 2010, 02:07 AM
  3. solving cubic congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 27th 2010, 06:18 AM
  4. Solving linear congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 12th 2010, 10:46 PM
  5. Solving congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 31st 2009, 11:16 PM

Search Tags


/mathhelpforum @mathhelpforum