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