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.