The version of the Euclidean algorithm that I'm trying to prove is as follows: $$\text{For natural numbers $a$ and $b$ such that $a \geq 1,$ $b \geq 0$ and $a \geq b,$ gcd($a,b$) =} \begin{cases} a, & \text{if $b=0$} \\ \text{gcd($b, a$ mod $b$)}, & \text{otherwise} \end{cases}$$
I've taken a hint for this proof from this answer.
Now, a common divisor (natural number) of two natural numbers $a$ and $b$ such that $a \geq 1,$ $b \geq 0$ and $a \geq b$ can be visualised as the side length (natural number) of equally-sized square tiles which can be used to evenly tile a rectangular area of length $a$ and breadth $b$.
So, the greatest common divisor (gcd) (natural number) of $a$ and $b$ is equal to the largest possible side length (natural number) of equally-sized square tiles which can be used to evenly tile a rectangular area of length $a$ and breadth $b$.
For eg., let $a=4$ and $b=2$.
The following image shows how equally-sized square tiles of side lengths $1$ and $2$ can be used to evenly tile a rectangular area of length $4$ and breadth $2$, which means that $1$ and $2$ are common divisors of $4$ and $2$.
Since there is no other way to tile this rectangular area, therefore $2$ is the gcd of $4$ and $2$.
For $b = 0$, the breadth of the rectangular area becomes $0$. Then, evenly tiling the rectangular area using equally-sized square tiles becomes equivalent to evenly covering a line segment of length $a$ using equally-sized line segments.
For eg., let $a = 4$ and $b = 0$.
The following image shows how equally-sized square tiles of side lengths $1$, $2$ and $4$ can be used to evenly tile a rectangular area of length $4$ and breadth $0$, which means that $1$, $2$ and $4$ are common divisors of $4$ and $0$.
Since there is no other way to tile this rectangular area, therefore $4$ is the gcd of $4$ and $0$.
Now, for every even tiling of a rectangular area of length $a$ and breadth $b$ such that $a \geq 1,$ $b \geq 1$ and $a \geq b$, we can always partition the rectangular area into one or more square subareas of side length $b$ and a remaining rectangular subarea (if any), and every subarea will remain evenly tiled.
This is because for every natural number $c$, if equally-sized line segments of length $c$ can be used to evenly cover a line segment of length $b$, then equally-sized square tiles of side length $c$ can be used to evenly tile a square area of side length $b$.
And, since all of the square subareas remain evenly tiled, therefore the remaining rectangular subarea also remains evenly tiled.
Moreover, the length and breadth of the remaining rectangular subarea (after rotating it by 90 degrees) are $b$ and $a$ mod $b$, respectively.
For eg., let $a = 20$ and $b = 8$.
The following image shows how equally-sized square tiles of side lengths $1$, $2$ and $4$ can be used to evenly tile a rectangular area of length $20$ and breadth $8$, and that the rectangular area can be partitioned into two square subareas of side length $8$ and a remaining rectangular subarea of length $8$ and breadth $20$ mod $8$ = $4$.
This means that every common divisor of $a$ and $b$ such that $a \geq 1$, $b \geq 1$ and $a \geq b$ is also a common divisor of $b$ and $a$ mod $b$.
Now, for every even tiling of the rectangular area GBCH, the square tiles can also be used to evenly tile the square areas AEFD and EGHF.
This is because for every natural number $c$, if equally-sized line segments of length $c$ can be used to evenly cover the line segment BC of length $b$, then equally-sized square tiles of side length $c$ can be used to evenly tile the square areas AEFD and EGHF of side length $b$.
This means that every common divisor of $b$ and $a$ mod $b$ is also a common divisor of $a$ and $b$.
Thus, the set of the common divisors of $a$ and $b$ is equal to the set of the common divisors of $b$ and $a$ mod $b$.
Therefore, the gcd of $a$ and $b$ is equal to the gcd of $b$ and $a$ mod $b$, given that $a \geq 1,$ $b \geq 1$ and $a \geq b$.
The next step is to show that if we keep on using this formula recursively, then the the conditions $a \geq 1,$ $b \geq 0$ and $a \geq b$ will hold at every step, and that $b$ will eventually become equal to $0$, terminating the process.
We start with two natural numbers $a$ and $b$ such that $a \geq 1,$ $b \geq 0$ and $a \geq b$.
If $b \geq 1$, then in the next iteration, $a$ will remain $\geq 1$, as $b$ of the current iteration will become $a$ of the next iteration. Now, since $a$ mod $b$ is equal to the remainder when $a$ is divided by $b$, therefore the value of $a$ mod $b$ will be $\geq 0$, and consequently, $b$ of the next iteration will remain $\geq 0$. Finally, since the remainder when $a$ is divided by $b$ is always less than $b$, therefore $a$ of the next iteration will remain $\geq b$ (actually, it will become $\gt b$).
Else, if $b = 0$, then the process will terminate.
Now, since $b$ of the current iteration will become $a$ of the next iteration, and $b \gt a$ mod $b$ in the current iteration means that $a$ will be $\gt b$ in the next iteration, therefore the value of $b$ will keep strictly decreasing in the successive iterations, which means that $b$ will eventually become equal to $0$, terminating the process.
Finally, we can also see that this algorithm works for all natural numbers $a$ and $b$.
This is because gcd($0$, $0$) will give $0$, which is the commonly accepted answer, and if $a \lt b$, then in the next iteration, $a \geq 1,$ $b \geq 0$ and $a \geq b$ will hold.
The key property is $\operatorname{gcd}(a,b)=\operatorname{gcd}(a+nb,b)$. In terms of these tilings, this says that adjoining (or removing, if $n<0$) $b\times b$ squares to the $a\times b$ rectangle will not change the greatest size of square tiles needed to cover the rectangles. This is true because any square tile that can be used to cover the $a\times b$ rectangle can also cover a $b\times b$ square.