Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

wednesday09876 Group Title

FAN AND MEDAL WILL BE REWARDED: Solve this system of congruences 2x=5 (mod 7) 3x=4 (mod 8)

  • 11 months ago
  • 11 months ago

  • This Question is Closed
  1. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    i basically only need to know how to make the 2x and 3x into single x's.

    • 11 months ago
  2. pgpilot326 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    not sure how to explain but I got an answer for the first, x must be equivalent to 6 + 7k, k = 0,1,2,...

    • 11 months ago
  3. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    would you happen to know how to make the x's into a workable form, i mean into just x??

    • 11 months ago
  4. pgpilot326 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    for the second, x must be equivalent to 4 + 8m, m = 0, 1, 2, ...

    • 11 months ago
  5. jefftheloveableguy Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    x is 5

    • 11 months ago
  6. jefftheloveableguy Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    lol just learned it online

    • 11 months ago
  7. jefftheloveableguy Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    need explanation?

    • 11 months ago
  8. pgpilot326 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    how is x = 5? 2*5 = 10 = 3 mod 7

    • 11 months ago
  9. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    where do we get 3 mod 7 though?

    • 11 months ago
  10. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    jeff, yeah thanks that would be great.

    • 11 months ago
  11. jefftheloveableguy Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    http://www.math.rutgers.edu/~erowland/modulararithmetic.html

    • 11 months ago
  12. pgpilot326 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    dude, 20 is the first x that works... not 5

    • 11 months ago
  13. jefftheloveableguy Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    basically a ≡ b mod m. means you do a-b=km

    • 11 months ago
  14. jefftheloveableguy Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    idk lol I just solved the system with k and x as variables ok maybe you know it better

    • 11 months ago
  15. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    alright just one sec im gonna try some work real quick

    • 11 months ago
  16. jefftheloveableguy Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    ok 5 doesn't work haha

    • 11 months ago
  17. jefftheloveableguy Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    40 does nice job

    • 11 months ago
  18. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    so i start with 2x-5 = 7 times k?

    • 11 months ago
  19. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    because i cant really solve further than that

    • 11 months ago
  20. jefftheloveableguy Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    1 sec asking friend

    • 11 months ago
  21. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    alright thanks

    • 11 months ago
  22. tkhunny Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Think about equivalence classes 2*0 = 0 (mod 7) 2*1 = 2 (mod 7) 2*2 = 4 (mod 7) 2*3 = 6 (mod 7) 2*4 = 1 (mod 7) -------------- 2*5 = 3 (mod 7) -------------- 2*6 = 5 (mod 7) 3*0 = 0 (mod 8) 3*1 = 3 (mod 8) 3*2 = 6 (mod 8) 3*3 = 1 (mod 8) -------------- 3*4 = 4 (mod 8) -------------- 3*5 = 7 (mod 8) 3*6 = 2 (mod 8) 3*7 = 5 (mod 8) 2x=5 (mod 7) 3x=4 (mod 8)

    • 11 months ago
  23. pgpilot326 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    have a look

    • 11 months ago
  24. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    so then how would i come up with just x though? i meant tkhunny that was great but

    • 11 months ago
  25. jefftheloveableguy Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    x=20mod56 dont ask why

    • 11 months ago
  26. jefftheloveableguy Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    my friend gave a huggge explanation that is like 20 fb messages

    • 11 months ago
  27. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    lol dude i need the work thats most of the points!! haha thanks tho

    • 11 months ago
  28. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    do you think you could like copy the messages??

    • 11 months ago
  29. jefftheloveableguy Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    It's so hard...i dont think its worth it..uses chinese remainder theorem

    • 11 months ago
  30. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    haha nvm then thanks

    • 11 months ago
  31. jefftheloveableguy Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    wed. what class is this for?

    • 11 months ago
  32. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    algebra 2 trig

    • 11 months ago
  33. jefftheloveableguy Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    wait your in algebra 2? Im in calc 3 and diff eq...

    • 11 months ago
  34. tkhunny Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    This is where the thinking I suggested might have take you... With a little luck, there is a multiplicative inverse for each value presented. 2x=5 (mod 7) 2*4 = 1 (mod 7) (Everyone has an inverse (mod 7)) 4*2*x = 4*5 (mod 7) x = 6 mod 7 3x=4 (mod 8) 3*3 = 1 (mod 8) (Only 1, 3, 5, and 7 have inverses of this type (mod 8) -- Think about mutually prime) 3*3*x = 3*4 (mod 8) x = 4 mod 8 And the problem is substantially simplified.

    • 11 months ago
  35. jefftheloveableguy Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    ok dude let me copy the messages. Good job in coming up with a problem no1 knows the answer to

    • 11 months ago
  36. jefftheloveableguy Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    how would you solve 2x=5 (mod 7) 3x=4 (mod8) Here's the catch: division is unique if the modulus is prime; otherwise, it can be multi-valued. So 5 / 2 mod 7 is unique, and equal to... 6, right? what does 5/2 mean? Five divided by two What number, multiplied by 2, yields 5 when operating mod 7? 20? Sure. But 20 = 6 mod 7 Notice that any value you can find which does so is 6 mod 7 That's the easier part. The trickier part is 3x = 4 mod 8. Let's think for the moment: if instead it were 2x = 4 mod 8, then both 2 and 6 would work, right? That's because the 2, from 2x, divides the modulus So division in modulo composite numbers may be multivalued. This led me to a wrong answer on an AIME problem, and I was mad wow Anyway, since 3 does not divide the modulus, 3x = 4 mod 8 has a unique solution, namely 6 what if x were 12? Namely 4*, that was and did you use a ≡ b mod m. a – b = km Here's what we now know (sorry for not using equivalent signs): x = 6 mod 7; x = 4 mod 8 With me? how did you change the 5 to 6 Since 2x = 5 mod 7, x = 5/2 mod 7 = 6 mod 7, as above (5/2 does not mean 2.5, it means "the number, which, upon multiplication by 2, yields 5 in modulo 7") Anyway, we have two different equivalences for x in different moduli. Now comes the key point: the Chinese Remainder Theorem (CRT) It says: if you have a system of equations x = ai mod mi And the mi are relatively prime There there is a unique solution c such that x = c mod (m1*m2*m3*m4*...*mi) It should make a bit of intuitive sense If we know a certain number yields a certain remainder upon division by 3 and 5, say, then we know that it must have a unique remained upon division by 15. right Does this make sense? some thanks though just started mods Okay. So x = c mod (8 * 7), or x = c mod 56 So, can you find a c such that c = 6 mod 7 AND c = 4 mod 8? (and c < 56) Can't find a c List the 6 mod 7 less than 56: 6, 13, 20, 27, 34, 41, 48, 55 List the 4 mod 8 less than 56: 4, 12, 20, 28, 36, 44, 52 Their intersection has exactly 1 element, as predicted by the CRT: 20 nice So c = 20, and our solution is x = 20 mod 56 Note: Although you can solve the original question just by guessing (does ? work, for ? up to 20) The point is, if x = 20 mod 56, then x does not have to be 20 It can be 76 right Or 76 + 56 * z, were z is an integer. All such values will solve your system Sorry to go through this so fast, but that is, in short, how mods work. yea ill have to look into it thanks! Im tired now do u consider mods as easy? Well, you already intuitively know a couple important mods: mod 2 (even/odd) and mod 10 (last digit). And I've been seeing them on math-competition type questions since freshman year, so I'd say they are a bit easier than things like cyclic quadrilaterals They can get hard, however... One sec http://www.artofproblemsolving.com/Wiki/index.php/2013_AIME_I_Problems/Problem_11 I thought mods were easy, but this problem was a pure modular arithmetic one which I messed up somewhere The key to my failure was this: part of the problem involves x = 3 mod 9 And trying to divide out the relevant parts (since x is already a multiple of 3, but unknown which one) Anyway You'll always see modular-type questions. If someone asks you for the last 2 digits of some giant product-like thing, think mod 100, or, by the CRT, mods 4 and 25

    • 11 months ago
  37. jefftheloveableguy Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    yup have fun with that I guess.

    • 11 months ago
  38. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    hey tk, how did you get from 2x=5 (mod 7) to 2*4 = 1 (mod 7)???

    • 11 months ago
  39. tkhunny Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    There is no "from" in there. 2x = 5 (mod 7) is the given problem statement 2*4 = 1 (mod 7) is the demonstration that 2 has a multiplicative inverse (mod 7). The inverse is 4. I then used the multiplicative inverse with the original problem statement. 2x = 5 (mod 7) 4*2*x = 4*5 (mod 7) Giving x = 6 (mod 7)

    • 11 months ago
  40. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    wow is that that hard, or did i miss come questions in between?

    • 11 months ago
  41. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    oh i see it is two of them but \(2x\equiv 5(7)\iff 2x\equiv 12(7)\iff x\equiv 6(7)\)

    • 11 months ago
  42. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    similarly \[3x\equiv4(8)\iff 3x\equiv 12(8)\iff x\equiv 4(8)\]

    • 11 months ago
  43. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    2*4 = 1 (mod 7) is the demonstration that 2 has a multiplicative inverse (mod 7). The inverse is 4. How do you get that? sorry about that just dont really get it

    • 11 months ago
  44. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    it is clear that \(2\times 4=8\) for sure right? and also that \(8\equiv 1(7)\)

    • 11 months ago
  45. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    @wednesday09876 this i think is too much work, although you may need it for something later

    • 11 months ago
  46. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    yeah i got it

    • 11 months ago
  47. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    so what do i do after that

    • 11 months ago
  48. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    as @tkhunny was saying now your job is to find \(x\) so that \[x\equiv 4(\text{ mod }7)\] and also \[x\equiv 4(\text{ mod }8)\]

    • 11 months ago
  49. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    but how did i legally just get it down to the form where there is one x?

    • 11 months ago
  50. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    if it was me, i would multiply \(8\times 7\) and then add 4

    • 11 months ago
  51. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    oh i see what your question is lets go slow

    • 11 months ago
  52. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    what ive been trying to understand is how the 2 and 3 disappeared from behind the x

    • 11 months ago
  53. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    yeah sorry

    • 11 months ago
  54. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    ok i got it lets go real slow and get this for sure

    • 11 months ago
  55. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    you have \[2x\equiv 5( \text{ mod } 7)\] right

    • 11 months ago
  56. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    yeah

    • 11 months ago
  57. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    ok now forget about this mod for a second suppose you just had \(2x=5\) what would you do to solve for \(x\)?

    • 11 months ago
  58. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    divide two over

    • 11 months ago
  59. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    i assume you mean "divide by 2" and yes, that is what you would do but you cannot divide this by 2 can you? because you have to work with whole numbers

    • 11 months ago
  60. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    yeah

    • 11 months ago
  61. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    so here is what we can do to allow us to divide by 2 add \(7\) to \(5\) because \(5( \text{ mod }7)\equiv 12( \text{ mod }7)\) that should be more or less clear both 5 and 12 have a remainder of 5 when divided by 7

    • 11 months ago
  62. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    got it

    • 11 months ago
  63. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    what i really should have written is that \[12\equiv 5(\text { mod } 7)\] but no matter i hope you get the idea

    • 11 months ago
  64. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    so now we have \[2x\equiv 12 ( \text { mod } 7)\]and now we CAN divide by 2

    • 11 months ago
  65. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    k?

    • 11 months ago
  66. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    yeah i got that, but i vaguely recall my teacher saying that when dividing you must divide the mod as well?

    • 11 months ago
  67. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    divide by \(2\) and we get \[x\equiv 6( \text { mod } 7)\]

    • 11 months ago
  68. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    no

    • 11 months ago
  69. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    alright as long as that is not a rule then yeah i got that part

    • 11 months ago
  70. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    lets check that this answer is right, so it is not a mystery

    • 11 months ago
  71. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    suppose \(x=6\) then \(2x=12\) right? and also \(12\equiv 5(\text { mod }7)\) so we know it is right

    • 11 months ago
  72. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    aha got it

    • 11 months ago
  73. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    now lets repeat the process for \(3x\equiv 4(\text { mod }8)\)

    • 11 months ago
  74. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    you cannot divide 4 by 3, so keep adding 8 until you can

    • 11 months ago
  75. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    fortunately for you, this requires only one addition sometimes it takes more

    • 11 months ago
  76. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    yeah i got it

    • 11 months ago
  77. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    since \(8+4=12\) is should be clear that \[12\equiv 4(\text { mod } 8)\] and so now we have \[3x\equiv 12(\text {mod} 8)\] divide by 4 etc etc

    • 11 months ago
  78. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    ah thank you

    • 11 months ago
  79. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    yw

    • 11 months ago
  80. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    course you still have to solve for \(x\)

    • 11 months ago
  81. wednesday09876 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    yeah i got that part, just needed it simplified so i could do the work

    • 11 months ago
  82. satellite73 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    k good

    • 11 months ago
  83. pgpilot326 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    2x = 7m + 5 , m = 0, 1, 2, ... we want just x so we have to multiply everything by the inverse of 2 mod 7, which is 4. => 8x = 7m + 20 => x = 7m + 6 now we sub that in for x in the other congruence => 3(7m+6) = 21m + 18 = 4 mod 8 => 5m +2 = 4 mod 8 => 5m = 2 mod 8 again we want only x so we multiply by the inverse of 5 mod 8, which is 5. => 25m = 10 mod 6 => m = 2 mod 8 => m = 8n + 2 now we sub that into our original equation for x... => x = 7(8n + 2) + 6 = 56n + 14 + 6 = 56n + 20 so x = 20 mod 56. I couldn't let it go until i figured it out so i apologize if this is any sort of a nuisance.

    • 11 months ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.