Here is the question that I'm working on:
Suppose $d$ is a common divisor to $a$ and $b$. We want to show that $d | (ma+nb) \forall m,n \in \mathbb{Z.}$
What I know so far...
The question does not specify what kind of numbers $a$ and $b$ are, so, for the sake of this problem, let $a,b \in \mathbb{Z}.$ I know that when computing the gcd of two numbers, say $a$ and $b$, I have a list of calculations I need to do and the last non-zero remainder is what yields our gcd. Now, this question is asking us to do a linear combination of some sort and my initial response was to work backwards. What I mean is that for every equation that I got from performing the Euclidian Algorithm, I solve for the remainder and use that value to substitute it into the next equation that follows above and continue the pattern from there until I get a linear combination. I hope that I'm explaining myself well here. Any inputs and inquiries are greatly appreciated.
John.
If $d\mid a$ and $d\mid b$, then you can write $a=a'd$ and $b=b'd$. This means that: $$ma+nb=ma'd+nb'd=(ma'+nb')d$$
So $d\mid ma+nb$.