A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • one year ago

Is this problem an application of the cancelation law of congruences? Prove that if bd ≡ bd' (mod p), where p is a prime, and p does not divide b, then d ≡ d' (mod p)

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

    That follows trivially from euclid lemma : \(p\mid mn \implies p\mid m~~\text{or}~~p\mid n\)

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

    \[bd\equiv bd'\pmod{p} \implies p\mid b (d-d')\] since \(p\nmid b\), it must be the case that \(p\mid (d-d')\) which is equivalent to saying \(d\equiv d'\pmod{p}\)

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

    ah.... I see. Is gcd(b,p) = 1 though?

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

    \(p\nmid b ~~\iff~~\gcd(p,b)=1 \)

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

    so in general, m does not divide n if and only if gcd(m,n)=1?

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

    that is correct only if \(m\) is a prime

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

    consider an example : \(m = 4,~ n = 6\) \(4\nmid 6\) but \(\gcd(4,6)\ne 1\)

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

    btw, in this thread \(p\) is assumed to be a prime.

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

    Ah... I see. Thank you :')

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

    So there are two ways to do the problem above. Euclid lemma or cancelation law (since gcd(b,p) = 1)

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

    pretty sure there are many other ways to prove it, as you can see the proof is trivial

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

    right. Thank you :)

  13. 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.