A community for students.
Here's the question you clicked on:
 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?
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

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2iii translates to \(c\mid a\) and \(c\mid b\) \(\implies c\mid \gcd(a,b)\)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2That means every common divisor of \(a\) and \(b\) is also a divisor of \(\gcd(a,b)\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Well yes, I understand what the statement means. Why do we need this criteria so that d is the greatest.

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2if 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\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0you 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?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0huhm.... 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

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2Another equivalent way of writing iii is \(c\mid a\) and \(c\mid b\) \(\implies \) \(c\le d\)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.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

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2that means your list of common divisors is incomplete

anonymous
 one year ago
Best ResponseYou've already chosen the best response.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?

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2Ofcourse you need to prove that first before touching gcd

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2I believe Euclid's lemma is more fundamental than gcd

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2Euclid's lemma : If \(a,b\) are relatively prime and \(a\mid bc\), then \(a\mid c\)

dan815
 one year ago
Best ResponseYou've already chosen the best response.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

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0it doesn't *necessarily* follow that \(a\,\,n\land b\,\,n\implies ab\,\,n\) unless \(\gcd(a,b)=1\)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0since \(18\) is divisible by \(3,9\) but not by \(3\cdot9=27\) :)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2Yes 4, 9 are relatively prime, we don't really need to use the term "gcd" to define "gcd"

dan815
 one year ago
Best ResponseYou've already chosen the best response.1if there is any common divisor between a and b, then that was considered to form your greatest divisor so

dan815
 one year ago
Best ResponseYou've already chosen the best response.1every 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

dan815
 one year ago
Best ResponseYou've already chosen the best response.1as the great common divisor, from that picture u can see is the combination of all the prime factors that divide both a and b

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0suppose 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$$

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0I guess I will have to think about this more. Thanks everyone for answering

dan815
 one year ago
Best ResponseYou've already chosen the best response.1ya sure its good to see multiple explanations for number theory questions, since there are so many ways to look at it
Ask your own question
Sign UpFind more explanations on OpenStudy
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
 Engagement 19 Mad Hatter
 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.