Sorry for hijacking.

Linear combination is useful because you can factor things out. If

and

, then for any integers

, you can factor out

from

. Let's call this fact C).

For B), the problem statement suggests proving that both sides divide each other. By C),

and

implies

. So, using A), we have

. Conversely, we need

. Obviously,

and

. By C), this implies that

because

is a linear combination of

and

. So, again by A),

.

Feel free to ignore the rest; I am writing sort of to recall these things for myself.

I prefer proving B) first and then A). B) is easy: by C), the pairs

and

have the same set of common divisors (at least when

to avoid possible problems with the definition of divisors of negative numbers). Therefore, the greatest of those divisors is the same.

To show A), as well as the fact that

is a linear combination of

and

, one uses Euclid's algorithm for computing GCD. The algorithm repeatedly changes a pair

into

and applies C) or B). Each step preserves the set of common divisors of the pair. We stop when

is reached. Why is

the GCD of the original numbers? Because by the described preservation, every common divisor of the original numbers, including the GCD, is a common divisor of

, i.e., a divisor of

, and vice versa.

Am I missing something in this reasoning?