1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Solve modular equation

  1. May 11, 2009 #1
    1. The problem statement, all variables and given/known data

    Find the integer y with both 0 < y < 144 and 35y = 42(mod 144)

    2. Relevant equations



    3. The attempt at a solution

    Can someone help me get started on this one? I understand that I can reduce it to 5y = 6(mod 144), and then to 5y = 6 + 144... but I'm not sure what to do with that. I mean, can I just do 5y = 150 and then y = 30?
     
  2. jcsd
  3. May 11, 2009 #2

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Re: modulus

    If you plug [tex]y = 30[/tex] into the original equation, is it true? If so, then you're done.

    An interesting question to consider: if instead of 35, the original equation had 36, then your method would fail. Why? Does the equation have a solution in that case?

    A more ambitious question: what is a necessary and condition upon k in order for

    ky = 42 (mod 144)

    to have a solution? Does the answer change if instead of 42 you use some other number between 0 and 143?
     
  4. May 12, 2009 #3
    Re: modulus

    I'm a little confused here. So if I plug my answer into the equation and it doesn't work, it means there are no solutions? And I don't know the answer to the second question
     
  5. May 12, 2009 #4
    Re: modulus

    I have another one here:

    0 < x < 41
    19x = 22(mod 41)

    You're right, my previous method didn't work. What can I do?
     
  6. May 12, 2009 #5

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Re: modulus

    Do you know this theorem:

    ax = b (mod n)

    has a solution if and only if gcd(a,n) divides b.

    In this case, gcd(a,n) = 1 since 19 and 41 are relatively prime. So a solution does exist.

    Any solution to this equation:

    ax + kn = b, where k is any integer

    is also a solution to

    ax = b (mod n)

    There is a well-known algorithm for finding integers x and k that satisfy

    ax + kn = b

    provided that a solution exists. Are you familiar with it?
     
  7. May 12, 2009 #6
    Re: modulus

    No. :(
     
    Last edited: May 12, 2009
  8. May 12, 2009 #7
    Re: modulus

    I'm still stuck on this... can anyone give me a hand?
     
  9. May 12, 2009 #8

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Re: modulus

    Saying 19x= 22 (mod 41) means that 19x= 22+ 41k for some integer k. That is the same as 19x- 41k= 22. 19 divides into 41 2 times with remainder 3 so 41= 2(19)+ 3 or 41- 2(19)= 3. 3 divides into 19 6 times with remainder 1: 19- 6(3)= 1 and then 19- 6(41- 2(19))= 3(19)- 6(41)= 1. Multiplying by 22, 66(19)- 132(41)= 22. Thus one answer is x= 66. That's not the answer you want because it is too big but you should be able find the correct answer.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Solve modular equation
  1. Solving Equations (Replies: 2)

  2. Solve this equation (Replies: 5)

Loading...