anonymous
  • anonymous
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?
Mathematics
chestercat
  • chestercat
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your free account and access expert answers to this
and thousands of other questions

ganeshie8
  • ganeshie8
iii translates to \(c\mid a\) and \(c\mid b\) \(\implies c\mid \gcd(a,b)\)
ganeshie8
  • ganeshie8
That means every common divisor of \(a\) and \(b\) is also a divisor of \(\gcd(a,b)\)
anonymous
  • anonymous
Well yes, I understand what the statement means. Why do we need this criteria so that d is the greatest.

Looking for something else?

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

More answers

ganeshie8
  • ganeshie8
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\)
anonymous
  • anonymous
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?
anonymous
  • anonymous
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
ganeshie8
  • ganeshie8
Another equivalent way of writing iii is \(c\mid a\) and \(c\mid b\) \(\implies \) \(c\le d\)
ganeshie8
  • ganeshie8
{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
  • ganeshie8
that means your list of common divisors is incomplete
anonymous
  • anonymous
@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
  • ganeshie8
Ofcourse you need to prove that first before touching gcd
ganeshie8
  • ganeshie8
I believe Euclid's lemma is more fundamental than gcd
ganeshie8
  • ganeshie8
Euclid's lemma : If \(a,b\) are relatively prime and \(a\mid bc\), then \(a\mid c\)
dan815
  • dan815
(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
  • anonymous
it doesn't *necessarily* follow that \(a\,|\,n\land b\,|\,n\implies ab\,|\,n\) unless \(\gcd(a,b)=1\)
anonymous
  • anonymous
since \(18\) is divisible by \(3,9\) but not by \(3\cdot9=27\) :-)
dan815
  • dan815
|dw:1437278787059:dw|
ganeshie8
  • ganeshie8
Yes 4, 9 are relatively prime, we don't really need to use the term "gcd" to define "gcd"
dan815
  • dan815
|dw:1437278905060:dw|
dan815
  • dan815
if there is any common divisor between a and b, then that was considered to form your greatest divisor so
dan815
  • dan815
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
dan815
  • dan815
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
anonymous
  • anonymous
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$$
anonymous
  • anonymous
I guess I will have to think about this more. Thanks everyone for answering
dan815
  • dan815
ya sure its good to see multiple explanations for number theory questions, since there are so many ways to look at it

Looking for something else?

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