## 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?

1. ganeshie8

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

2. ganeshie8

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

3. anonymous

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

4. 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$$

5. 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?

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

7. ganeshie8

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

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

9. ganeshie8

that means your list of common divisors is incomplete

10. 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?

11. ganeshie8

Ofcourse you need to prove that first before touching gcd

12. ganeshie8

I believe Euclid's lemma is more fundamental than gcd

13. ganeshie8

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

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

15. anonymous

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

16. anonymous

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

17. dan815

|dw:1437278787059:dw|

18. ganeshie8

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

19. dan815

|dw:1437278905060:dw|

20. dan815

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

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

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

23. 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$$

24. anonymous

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

25. dan815

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