Originally Posted by

**emakarov** Sorry for hijacking.

Linear combination is useful because you can factor things out. If $\displaystyle c\mid m$ and $\displaystyle c\mid n$, then for any integers $\displaystyle s, t$, you can factor out $\displaystyle c$ from $\displaystyle sm + tn$. Let's call this fact C).

For B), the problem statement suggests proving that both sides divide each other. By C), $\displaystyle c\mid m$ and $\displaystyle c\mid n$ implies $\displaystyle c\mid (n-qm)$. So, using A), we have $\displaystyle d\mid\gcd(m, n-qm)$. Conversely, we need $\displaystyle \gcd(m, n-qm)\mid d$. Obviously, $\displaystyle \gcd(m, n-qm)\mid m$ and $\displaystyle \gcd(m, n-qm)\mid (n-qm)$. By C), this implies that $\displaystyle \gcd(m, n-qm)\mid n$ because $\displaystyle n$ is a linear combination of $\displaystyle m$ and $\displaystyle n-qm$. So, again by A), $\displaystyle \gcd(m, n-qm)\mid d$.

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 $\displaystyle (n, m)$ and $\displaystyle (m, n - qm)$ have the same set of common divisors (at least when $\displaystyle n - qm \ge 0$ 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 $\displaystyle \gcd(n,m)$ is a linear combination of $\displaystyle n$ and $\displaystyle m$, one uses Euclid's algorithm for computing GCD. The algorithm repeatedly changes a pair $\displaystyle (n, m)$ into $\displaystyle (m, n - qm)$ and applies C) or B). Each step preserves the set of common divisors of the pair. We stop when $\displaystyle (d, 0)$ is reached. Why is $\displaystyle d$ 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 $\displaystyle (d, 0)$, i.e., a divisor of $\displaystyle d$, and vice versa.

Am I missing something in this reasoning?