Some important concept about greatest common divisor for

We have proved that

.

The statement above is one way implication. You can not use a linear combination of to imply the greatest common divisor of , unless you can claim the linear combination is the smallest positive integer among that is the set we considered during the proof. We started with let be the smallest element in and then we showed that

Prove that

(The following “wrong” argument could easily happened)

Assume that , then

i.e. . Then .

(The last line above is not necessarily true, unless you can prove presents the smallest positive integer among the positive integers that can be presented by integral linear combination of)