# Thread: Clarification on gcd proofs

1. ## Clarification on gcd proofs

Hey guys,

So we all (hopefully ) know the definition of gcd. and so if we want to prove that an integer, $\displaystyle d$, is the gcd of two integers, $\displaystyle a$ and $\displaystyle b$, then in general, we must show:

(a) $\displaystyle d \mid a$ and $\displaystyle d \mid b$, and,

(b) If there exists $\displaystyle c$, such that $\displaystyle c \mid a$ and $\displaystyle c \mid b$, then $\displaystyle c \mid d$.

Now, I want clarification on proving (b). My professor last semester always did something like this. In problems where we were working with linear combinations, he would have the equation $\displaystyle d = ma + nb$ for $\displaystyle m,n \in \mathbb{Z}$. No problem. But to show that $\displaystyle d = (a,b)$, he would say: "suppose there is some $\displaystyle c$ such that $\displaystyle c \mid a$ and $\displaystyle c \mid b$. then $\displaystyle a = kc$ and $\displaystyle b = lc$ for $\displaystyle k,l \in \mathbb{Z}$. Thus, $\displaystyle d = ma + nb = (mk)c + (nl)c = c(mk + nl) \implies c \mid d$."

now i always had a problem with that. why does this work? it seems like an underhanded trick to me, and that it could work for $\displaystyle d$'s that are not the gcd.

case in point: lets say i am thinking about (3,2), we know this is 1. and $\displaystyle 1 = 3 + (-1)(2)$, so here $\displaystyle a = 3,~b=2,~m = 1, \text{ and }n = -1$. and i can run the proof above and it works for my $\displaystyle d$ (= 1).

but what if i was really imagining the combination $\displaystyle 2(3) + (-2)(2) = 2$, and so i took $\displaystyle a = 3,~b=2,~m = 2, \text{ and }n = -2$. and i can run the generic proof above for $\displaystyle d = ma + nb$ and conclude that my $\displaystyle d$ (which is 2) is the gcd of 3 and 2.

of course if we know the values of $\displaystyle a,~b, \text{ and } d$, this would be absurd, but a lot of the proofs i am doing are with pure variables. how can i be confident that my linear combination is the optimal one for the gcd and thus can run this proof with a clear conscience.

or am i imagining a problem that really isn't there?

Thanks for listening to my rant... and oh, yeah, the question too,
Jhevon

2. Hello
Originally Posted by Jhevon
Hey guys,

(a) $\displaystyle d \mid a$ and $\displaystyle d \mid b$, and,

(b) If there exists $\displaystyle c$, such that $\displaystyle c \mid a$ and $\displaystyle c \mid b$, then $\displaystyle c \mid d$.

Now, I want clarification on proving (b). My professor last semester always did something like this. In problems where we were working with linear combinations, he would have the equation $\displaystyle d = ma + nb$ for $\displaystyle m,n \in \mathbb{Z}$. No problem. But to show that $\displaystyle d = (a,b)$, he would say: "suppose there is some $\displaystyle c$ such that $\displaystyle c \mid a$ and $\displaystyle c \mid b$. then $\displaystyle a = kc$ and $\displaystyle b = lc$ for $\displaystyle k,l \in \mathbb{Z}$. Thus, $\displaystyle d = ma + nb = (mk)c + (nl)c = c(mk + nl) \implies c \mid d$."

now i always had a problem with that. why does this work? it seems like an underhanded trick to me, and that it could work for $\displaystyle d$'s that are not the gcd.
I think he introduces c more for proving (b) than proving d=gcd(a,b).
Let c be a common divisor of a and b. Thus he must divides gcd(a,b), since it's the least common factor of all common divisors of a and b.

So we proved in (a) that d, the presumed gcd, divides a and b. Thus he divides the gcd. But we proved in (b) that if c is any of a and b's common divisors, then it divides d. So there is no common factor of a and b higher than d !

case in point: lets say i am thinking about (3,2), we know this is 1. and $\displaystyle 1 = 3 + (-1)(2)$, so here $\displaystyle a = 3,~b=2,~m = 1, \text{ and }n = -1$. and i can run the proof above and it works for my $\displaystyle d$ (= 1).

but what if i was really imagining the combination $\displaystyle 2(3) + (-2)(2) = 2$, and so i took $\displaystyle a = 3,~b=2,~m = 2, \text{ and }n = -2$. and i can run the generic proof above for $\displaystyle d = ma + nb$ and conclude that my $\displaystyle d$ (which is 2) is the gcd of 3 and 2.
Does d divide a ?
Plus, as soon as you can simplify the equaion am+bn=..., do it.

of course if we know the values of $\displaystyle a,~b, \text{ and } d$, this would be absurd, but a lot of the proofs i am doing are with pure variables. how can i be confident that my linear combination is the optimal one for the gcd and thus can run this proof with a clear conscience.
Because you make assumptions. It's better having an example right now
By the way, you don't have to care about m and n. Because the gcd divides any linear combination of a and b.
In proofs involving pure variables, you barely need the identity : there exist m and n such that am+bn=gcd(a,b). It is not interesting because it's not a reciprocity... Saying that the gcd divides a and b and any linear combination of them two is more interesting

or am i imagining a problem that really isn't there?
Prove it as it comes in your mind lol. No, I'm serious. There is a lot of intuition in my opinion.

Are there unclear things ? (which wouldn't be surprising... not easy to explain this way )