Prove that $\gcd(x, y)=\gcd(x,ax+y)$, would this be the correct reasoning? We know that $\gcd(x, y) = d$ as d divides $x$ and $y$, now suppose there are $x'$ and $y'$ integers such that
$$x = d \cdot x' \implies d|x \\y = d \cdot y' \implies d|y$$
then $a \cdot  x$ would be
$$ a\cdot x = a \cdot d \cdot x'$$
and so $a \cdot x + y$ equals
$$a \cdot d \cdot x' + d \cdot y' = d(a \cdot x' + y')$$
which is divisible by d and we know that $\gcd(x, y) = d$ , therefore $\gcd(x, y) = \gcd(x, ax + y)$
Thanks in advance.
 A: No, this is not correct. 
You showed, that $d|x$ and $d|y$ implies $ d|(ax+y)$. So basically you proven, that $\gcd(x,y)|\gcd(x,ax+y)$. But you still don't know, if $\gcd(x,y)=\gcd(x,ax+y)$. 
Try to prove the other direction by assuming $d|x$ and $d|(ax+y)$. This will imply $\gcd(x,ax+y)|\gcd(x,y)$. 
Then you are done. 
A: Hint : What misses in your proof is to show that  $\gcd(ax'+y',x')=1$. Can you proceed from here?
To show this consider the following reasoning (by contradiction):  Suppose $\gcd(ax'+y',x') \neq 1$ then there exist a natural number $b>1$ such that $b| (ax'+y') $ and $b|x'$. Hence $b|y'$. 
But is this possible if $\gcd(x,y)=d$??   
A: A slightly different way to look at this is as follows:
1) If d|x and d|y, then d|(ax+y) by your argument; so any common divisor of x and y is a common divisor of x and ax+y.
2) Similarly, if d|x and d|(ax+y), then d|y [since x=cd and ax+y=bd gives y=bd-ax=bd-acd=(b-ac)d]; so any common divisor of x and ax+y is a common divisor of x and y.
Since x and y have the same set of common divisors as x and ax+y, 
gcd(x,y)=gcd(x,ax+y).
A: Here is a proof in a different, more calculational style.
(I'm assuming all variables are integers, and $\;s,t \geq 0\;$.)
We have to prove an equality related to divisibility, so it helps to remember that any non-negative integers $\;s\;$ and $\;t\;$ are equal iff they have the same divisors: $$(0)\;\;\;s = t \;\equiv\; \langle \forall d :: d|s \equiv d|t \rangle$$
Also, the key property of $\;\gcd(x,y)\;$ is that its divisors (and only those) divide both $\;x\;$ and $\;y\;$: $$(1)\;\;\;\langle \forall d :: d|\gcd(x,y) \;\equiv\; d|x \land d|y \rangle$$ (Actually, this could be the definition if we were restricting ourselves to non-negative numbers.)
Translating the original statement using $(0)$ and $(1)$, we are asked to prove 
$$\langle \forall d :: d|x \land d|y \;\equiv\; d|x \land d|(a \cdot x + y) \rangle$$
or equivalently (by extracting the common conjunct)
$$\langle \forall d : d|x : d|y \equiv d|(a \cdot x + y) \rangle$$
The latter we can easily prove, for any $\;d\;$, as follows:
\begin{align}
& d|y \;\equiv\; d|(a \cdot x + y) \\
\Leftarrow & \;\;\;\;\;\text{"property of divisibility: numbers are equally divisible if their difference is"} \\
& d|(a \cdot x) \\
\Leftarrow & \;\;\;\;\;\text{"property of divisibility: a divisor of a factor also divides the product"} \\
& d|x \\
\end{align}
which completes the proof.
