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?

Question

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?

ganeshie8 · Answer

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

ganeshie8 · Answer

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

anonymous · Answer

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

ganeshie8 · Answer

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 · Answer

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 · Answer

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 · Answer

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

ganeshie8 · Answer

{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 · Answer

that means your list of common divisors is incomplete

anonymous · Answer

@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 · Answer

Ofcourse you need to prove that first before touching gcd

ganeshie8 · Answer

I believe Euclid's lemma is more fundamental than gcd

ganeshie8 · Answer

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

dan815 · Answer

(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 · Answer

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

anonymous · Answer

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

dan815 · Answer

|dw:1437278787059:dw|