A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

science0229

  • one year ago

Number Theory Help!

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

    For positive integers a,b,c,d, if gcd(a,b)=gcd(c,d)=1, then prove that \[\frac{ a }{ b }+\frac{ c }{ d }\notin Z\] \[b \neq d\]

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

    I tried to start this problem by saying that since gcd(a,b)=gcd(c,d)=1, there exist x,y,u,w such that \[ax+by=cu+dv=1\]

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

    Since \[\frac{ a }{ b }+\frac{ c }{ d }=\frac{ ad+bc }{ bd }\], I tried to somehow manipulate the above equation to get this form, but I've failed...

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

    try by contradiction suppose \(\dfrac{a}{b}+\dfrac{c}{d}=n \implies ad+bc= b*d*n\) \(\implies b\mid ad\) and \(d\mid bc\)

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

    since \(\gcd(a,b)=1\), by euclid lemme, \(b\mid ad \implies b\mid d\) similarly \(d\mid b\) together imply \(b=d\), contradiction, ending the proof.

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

    Bravo!

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

    Thank you!

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

    So the key to this problem was using contradiction. Does there happen to be an alternate proof?

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

    sure, but i feel they all are messy... you don't like that divisibility argument is it ?

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

    No. I do like that elegant solution that you provided using contradiction. It's just that I have a feeling that there might be an alternate solution using the Bezout's Identity...

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

    btw the key thing is not contradiction, i think the key thing is noticing that \[m\mid n ~~\text{and}~~n\mid m~~\implies n=\pm m\]

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

    sure, lets try using bezout's identity

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

    Wait. On the other thought, I do have this odd feeling that this will be dirty...

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

    Look at robjohn's reply here http://math.stackexchange.com/questions/1151443/prove-for-positive-integers-a-b-c-and-d-where-b-does-not-equal-d-if-gcda-b

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

    Ah. That's exactly what I wanted! It's not that dirty as I thought it would be.

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

    usually euclid lemma is covered prior to bezout so it is okay to use euclid lemma as it is more fundamental or whatever..

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

    got it. Thank you!

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