Aquí hay una prueba en un estilo diferente, más calculador.
(Estoy asumiendo que todas las variables son enteras, y $\;s,t \geq 0\;$ .)
Tenemos que demostrar una igualdad relacionada con la divisibilidad, por lo que ayuda recordar que cualquier entero no negativo $\;s\;$ y $\;t\;$ son iguales si tienen los mismos divisores: $$(0)\;\;\;s = t \;\equiv\; \langle \forall d :: d|s \equiv d|t \rangle$$
Además, la propiedad clave de $\;\gcd(x,y)\;$ es que sus divisores (y sólo éstos) dividen a ambos $\;x\;$ y $\;y\;$ : $$(1)\;\;\;\langle \forall d :: d|\gcd(x,y) \;\equiv\; d|x \land d|y \rangle$$ (En realidad, ésta podría ser la definición si nos limitáramos a los números no negativos).
Traduciendo la declaración original con $(0)$ y $(1)$ se nos pide que demostremos $$\langle \forall d :: d|x \land d|y \;\equiv\; d|x \land d|(a \cdot x + y) \rangle$$ o de forma equivalente (extrayendo el conjunto común) $$\langle \forall d : d|x : d|y \equiv d|(a \cdot x + y) \rangle$$
Esto último lo podemos demostrar fácilmente, para cualquier $\;d\;$ de la siguiente manera: \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} lo que completa la prueba.