Is the following True of False? Provide a proof if true or a counterexample if false:
Let a,b be two integers (not both zero), then the gcd(a,b) divides ay+bx for all for x,y ∈ Z.
I tried with several cases such as gcd(5,10) = 5 and then multiplied by various integers and could not find a counterexamaple. I do not know how to prove this formally. (or if you see a counterexample) 
 A: Among other things, $d=\gcd(a,b)$ is a common divisor of both $a$ and $b$.  Hence there are integers $a',b'$ such that $a=a'd, b=b'd$.  For any $x,y\in\mathbb{Z}$, we have $ay+bx=a'dy+b'dx=d(a'y+b'x)$.  Hence $d$ divides $ay+bx$.
A: Consider the set $I=\{ax+by|x,y\in\mathbb{Z}\}\subset\mathbb{Z}$. This is an ideal in $\mathbb{Z}$, which is a PID, and so is generated by a single element $d=ra+sb$. It is easy to check that $d=gcd(a,b)$. So every element of the ideal $I$ is an integer multiple of $d$.
A: Let $(a,b)=d$ and $\displaystyle \frac aA=\frac bB=d\implies (A,B)=1$
$ax+by= A\cdot d\cdot x+B\cdot d\cdot y=d(A\cdot x+B\cdot y)$
A: $$\begin{align}
  & d = \gcd(a,b) ~ \rightarrow ~ d \mid a \text{ and } d \mid b\\
  & a \mid b \text{ and } a \mid c ~ \rightarrow ~ a \mid (bx + cy)\text{ for all } x,~y \in \mathbb{Z}
\end{align}$$
A: Consider the set S of all linear combinations of a and b: {ax + by}
The set is non-empty, as the set must contain |a| and |b| (substitute 1 or -1 for x or y, and making the other 0), and thus has at least one positive element (only one of a and b can be 0).
By the well ordered principle (the intersection of all positive integers and a non-empty set containing positive integers has a smallest positive integer), this set has a smallest positive element. Let us call it d. d = ax' + by', for some x' and y'.
We will now show that d divides a.
By the remainder theorem, a = d*q + r, where q and r are both integers and 0 <= r < d.
Substituting in for d, we get a = (ax' + by')*q + r
r = (ax' + by')*q - a
r = ax'q + by'q - a
r = ax'q -a + by'q
r = a(x'q - 1) + by'q
By definition of S, r is an element of S. However, we know d is the smallest positive element of S, and r < d. Thus, r must be zero, and thus d divides a. By symmetry, d also divides b.
We have shown d is a common divisor of a and b, and because d is the smallest element of S, d also divides all other elements of S. Proof:
a = d*m, for some integer m (d divides a)
b = d*n, for some integer n (d divides b)
Let e = a*o + b*p
By substitution, e = d*m*o + d*n*p = d(m*o + n*p), and thus d divides e.
Now we must show d is the greatest common divisor of a and b.
Assume, by contradiction, it is not and that d' > d and d' divides a and b. d' is positive.
d = ax' + by'
As d' divides a, a = d'*f (for some integer f)
As d' divides b, b = d'*g (for some integer g).
By substitution, d = d'fx' + d'gy' = d'(fx' + gy').
Thus, d' divides d, and must be less than or equal d (as d is positive), and a contradiction is reached (where we assumed d'> d).
Thus, d is the greatest common divisor of a and b, and we have already shown divides all linear combinations of a and b.
A: Here is a calculational proof.
Using the fact (definition) that $\;\gcd(a,b)\;$ is the unique non-negative integer such that
$$
(0) \;\;\; \langle \forall d :: d | \gcd(a,b) \;\equiv\; d | a \;\land\; d | b \rangle
$$
where $\;d\;$ ranges over the integers, we can calculate as follows:
\begin{align}
& \gcd(a,b) | (a \cdot y + b \cdot x) \\
\equiv & \;\;\;\;\;\text{"property of $\;|\;$ -- so that we can use $(0)$"} \\
& \langle \forall d \;:\; d | \gcd(a,b) \;:\; d | (a \cdot y + b \cdot x) \rangle \\
\equiv & \;\;\;\;\;\text{"definition $(0)$"} \\
& \langle \forall d \;:\; d | a \;\land\; d | b \;:\; d | (a \cdot y + b \cdot x) \rangle \\
\end{align}
This last line is easily proved: for all $\;d\;$,
\begin{align}
& d | (a \cdot y + b \cdot x) \\
\Leftarrow & \;\;\;\;\;\text{"weaken: a divisor of all summands also divides the sum"} \\
& d | (a \cdot y) \;\land\; d | (b \cdot x) \\
\Leftarrow & \;\;\;\;\;\text{"weaken: a divisor of a factor also divides the product"} \\
& d | a \;\land\; d | b \\
\end{align}
This completes the proof.
