Euclidean GCD and why does it work? By the dupe, the table implies $\,(14441,3565) = (3565,189) = \ldots = (28,21) = (21,7) = (7,0) = 7\ \ $
I understand that Euclid's algorithm on GCD is based on doing division via subtraction $x = qy + r$. I also understand that the process is keep expressing the quotient in terms of the remainder.
Example to find GCD of $14441$, $3563$:




x    =
q
* y
+  r




14441
4
3565
189


3565
18
189
161


189
1
161
28


161
5
28
21


28
1
21
7


21
3
7
0




So the GCD is $7$.
So basically we try to divide the $2$ original numbers and then try to see if the remainder can express evenly $y$ and keep doing that recursively i.e. try to find the smallest number that divides the remainder.
But I am not sure I understand the intuition behind the idea. Why would that process lead to the smallest number that divides the original $x$?
I also read that a core idea is that $gcd(x,y) = gcd(y,r)$ but I didn't really get that part too.
Could someone please help?

You might find it easier to consider just a single step:
For any two numbers $x$ and $y$ with $y<x$, consider $x$ and $x-y$.
Any divisor of $x$ and $y$ is also a divisor of $x-y$ and $y$. Similarly, any divisor of $x-y$ and $y$ is also  a divisor of $x$ and $y$. Thus gcd$(x,y)=$ gcd$(x-y,y)$.
We have thus reduced the pair of numbers and can repeat this over and over again.
