A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • one year ago

What exactly is a mutually incongruent solution of a congruence? Can you give an example?

  • This Question is Closed
  1. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    \(1\) and \(6\) are not mutually incongruent in mod \(5\) because \(1\equiv 6\pmod{5}\)

  2. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    \(1\) and \(3\) are mutually incongruent in mod \(5\) because \(1\not\equiv 3\pmod{5}\)

  3. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    incongruent is just an opposite of congruent

  4. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    ok, so two numbers m and n are mutually incongruent mod c means m not congruent n (mod c)

  5. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Yep!

  6. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    For this example: Find a complete set of mutually incongruent solutions of 7x≡5 (mod 11)

  7. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    x = 7, so all solutions are x = 7 + 11k, k an integer

  8. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    the answer should be just \(\{7\}\)

  9. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    why {7} ? and not, say {18} ??

  10. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    sure, you can put any single integer that is congruent to 7

  11. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    but the numbers 0 to n-1 are more convenient and look better

  12. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    But how does the number 7 or any number congruent to 7 mod 11 capture the idea of "mutually incongruent" solution? if 7 not congruent m (mod 11), what numbers play in the role of m according to the definition of mutually incongruent?

  13. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    there are no other integer solutions, it is like asking for all the mutually perpendicular vectors that are solutions, if there is only one vector, you give only that.

  14. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    every other solution is congruent to 7, so there are no other incongruent solutions

  15. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    huhm... ok, let me give another example where it has more than 1 mutually incongruent solution. 9x ≡ 12 (mod 15). Since gcd(9,15) = 3, there will be 3 mutually incongruent solutions

  16. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    looks good

  17. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    no wait, how do you know there exists a solution ?

  18. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    because gcd(9,15) = 3 | 12

  19. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I see x = 3 is one of the solution so all solution is x = 3 + k * 15/gcd(9,15) x = 3 + 5k

  20. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    "If a solution exists", then there will be exactly 3 incongruent solutions

  21. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    consider below congruence : \[9x\equiv 2\pmod{15}\] how many solutions ?

  22. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    none, gcd(9,15) does not divide 2

  23. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    right?

  24. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Yep!

  25. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    so.....???

  26. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    let's get back to 9x ≡ 12 (mod 15). There will be exactly 3 mutually incongruent solutions. And all solutions are x = 3 + 5k

  27. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    what are the mutually incongruent solutions?

  28. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    let k = 0,1,2

  29. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    the incongruent solutions are \(\{3,8,13\}\) they are mutually incongruent in mod \(15\)

  30. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    how do you know to let k = 0,1,2??

  31. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    they are the most convenient ones

  32. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    letting k = 222, 223,224 is technically fine but you're not keeping things simple here

  33. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    ok, let 0 <= <= 10, then x = 3,8,13, 18, 23, 28, 33, 38, 43, 48, 53

  34. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    3 and 18 are not incongruent

  35. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    right. I was trying to understand how to find the incongruent solutions by listing a few solutions

  36. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    what i notice is 3 + 15 = 18 8 + 15 = 23 13 + 15 = 28

  37. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    it's somehow like {3,8,15}, {18,23,28}

  38. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    notice that any integer greater than or equal to 15 is congruent to some integer in the set \(\{0,1,2,\ldots,14\}\)

  39. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    so we don't need to bother about anything greater than 14

  40. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    and we don't need to bother about anything less than 0

  41. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    the set of residues \(\{0, 1, 2, \ldots, n-1\}\) is our most favorite one, when somebody asks you for incongruent solutions, they expect you to give them from this set

  42. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    So {3,8,15} are the set of mutually incongruent because 3 + 5k not congruent 8 + 5s not congruent 15 + 5t, for all integer k,s,t Is this what the incongruent solutions really mean?

  43. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    mod 15 btw

  44. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    {3, 8, 13} right

  45. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    opps yeah. Typo :D

  46. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    3 + 5k not congruent 8 + 5s not congruent 13 + 5t (mod 15), for all integer k,s,t

  47. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    3 + 15k not congruent 8 + 15s not congruent 13 + 15t, for all integer k,s,t in mod 15

  48. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    notice i have changed 5k to 15k

  49. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    3 + 5k refers to mod 5 3 + 15k refers to mod 15

  50. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I think I understand it better now although I still need to do some examples to clear up any confusion. @ganeshie8 thank you :)

  51. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    basically we're "lifting" the solutions from mod5 to mod15, so \(x\equiv 3\pmod{5}\) gives 3 incongruent solutions in mod 15 : \(\{3,8,13\}\)

  52. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    yeah, that's what I noticed earlier when I said 3 + 15 = 18 8 + 15 = 23 13 + 15 = 28

  53. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    so instead of expressing all solutions in the form of 3 + 5k, we can express all solutions in terms of mutually incongruent soltuions. I.e {x | x = 3 + 15k or x = 8 + 15k or x = 13 + 15k }

  54. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    you may simply say, the solutions are \(x\equiv 3\pmod{5}\)

  55. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    you could also say \(x\equiv 3,8,13\pmod{15}\)

  56. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    right right. That's exactly what I was trying to say :D

  57. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    if you're not explicitly asked for the form of solutions, leaving it as \(x\equiv 3\pmod{5}\) looks neat

  58. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    awesome. Thanks

  59. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

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.