A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • one year ago

Help with number theory. If a and b are integers, not both zero, then an integer d is called the greatest common divisor of a and b if i) d > 0 ii) d is a common divisor of a and b; and iii) each integer m that is a divisor of a and b is also a divisor of d. explain the third (iii) criteria. How does it capture the idea that d is the greatest among the common divisors?

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

    iii translates to \(c\mid a\) and \(c\mid b\) \(\implies c\mid \gcd(a,b)\)

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

    That means every common divisor of \(a\) and \(b\) is also a divisor of \(\gcd(a,b)\)

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

    Well yes, I understand what the statement means. Why do we need this criteria so that d is the greatest.

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

    if you can divide an integer,\(d\), by set of integers \(c_i\) evenly, then that means \(d\) cannot be less than any of \(c_i\)

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

    you need the criteria so that way \(\gcd(a,b)\) is the *greatest* common divisor; if it doesn't subsume a common divisor \(c\) then tehcnically \(c\cdot\gcd(a,b)\) would be greater than \(\gcd(a,b)\) and then it wouldn't be the greatest common divisor, now would it?

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

    huhm.... That makes sense. But how did we know that d is divisible by all other common factors? I know it's just the definition but, how would we know this won't happen: Suppose {1,3,4,9} are the commons divisor of a and b. 9 is certainly the greatest but 9 isn't divisible by all of the common divisors

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

    Another equivalent way of writing iii is \(c\mid a\) and \(c\mid b\) \(\implies \) \(c\le d\)

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

    {1,3,4,9} 9 is certainly not the gcd in your example Notice that if 4, 9 are common divisors then so is 4*9

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

    that means your list of common divisors is incomplete

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

    @ganeshie8 that's what I'm confused on. It seems like they used some theorems to make a definition. I could as well ask, for example, if 4 and 9 are common divisor of a and b, then why is 4*9 also a common divisor?

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

    Ofcourse you need to prove that first before touching gcd

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

    I believe Euclid's lemma is more fundamental than gcd

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

    Euclid's lemma : If \(a,b\) are relatively prime and \(a\mid bc\), then \(a\mid c\)

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

    (iii) i think a simple way is, if m is a division of a and b, then it is a divisor of d as m can be added to the greatest divisors formation look at picture

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

    it doesn't *necessarily* follow that \(a\,|\,n\land b\,|\,n\implies ab\,|\,n\) unless \(\gcd(a,b)=1\)

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

    since \(18\) is divisible by \(3,9\) but not by \(3\cdot9=27\) :-)

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

    |dw:1437278787059:dw|

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

    Yes 4, 9 are relatively prime, we don't really need to use the term "gcd" to define "gcd"

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

    |dw:1437278905060:dw|

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

    if there is any common divisor between a and b, then that was considered to form your greatest divisor so

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

    every divisor of both a and b,will be the multiplication of some combination of the common divisors of a and b, which all exist in your greatest common divisor

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

    as the great common divisor, from that picture u can see is the combination of all the prime factors that divide both a and b

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

    suppose we represent a number \(a=p_1^{m_1}p_2^{m_2}\dots,b=p_1^{n_1}p_2^{n_2}\dots\). we can then represent the \(gcd(a,b\)) as: $$\gcd(a,b)=p_1^{\min\{m_1,n_1\}}p_2^{\min\{m_2,n_2\}}\dots$$

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

    I guess I will have to think about this more. Thanks everyone for answering

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

    ya sure its good to see multiple explanations for number theory questions, since there are so many ways to look at it

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