I thought that lemma (*) was $\gcd(a,b) = \gcd(b,r)$ where $a=bq + r, \, 0≤r <b$, and it worked when you divide $a$ by $b$ to get the quotient $q$ and a remainder $0≤r<b$.
But I don't think any of those conditions are even necessary. That is, for every integers $a,b,c,d$ such that $a=bc+d$ where $a$ and $b$ are not both zero (at the same time). Then $\gcd(a,b)= \gcd(b,d)$.
Proof: Let $\gcd(a,b)= g_1$ and $\gcd(b,d)=g_2$ so $g_1 \mid a,b \Rightarrow g_1 \mid a-bc=d$ Hence $g_1$ is a common divisor of $b$ and $d$ so $g_1≤g_2$. Similarly $g_2 \mid b,d \Rightarrow g_2 \mid bc+d = a$ so $g_2 ≤ g_1$. And hence proved.
Is this prove correct? If so, then why is it taught like (*). Is there a special reason for it? What am I missing?
Your argument is correct. But without the inequality on the remainder it's not useful for proving that Euclid's algorithm helps you calculate the greatest common divisor.
See, e.g.:
Why does the Euclidean algorithm for finding GCD work?,
which may help you with your old question at
Why do we eventually end up with $0$ in Euclidean Algorithm?,