1

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?

Bill Dubuque
  • 265,059
  • 37
  • 279
  • 908
Jim
  • 1,581
  • 8
  • 13
  • if $d$ divides $x$ and $y$, then $d$ divides $r=x-qy$ – J. W. Tanner Feb 09 '21 at 17:28
  • @J.W.Tanner: I know that if $d|x$ and $d|y$ then $d|(x - y)$ but I wasn't aware of what you mentioned and I am not clear how to follow the thought for the original question using that – Jim Feb 09 '21 at 17:30
  • 1
    The key idea is that, the gcd of $x$ and $y$ must also be a factor of $(x-y)$, $(x-2y)$, $\dots$, $(x-qy)=r$. As the gcd is a factor of $x$, $y$ and $r$, we can express it using any two of them. – kctong529 Feb 09 '21 at 17:38
  • 2
    if $d|x$ and $d|y$, then $d|x$ and $d|qy$, so $d|x-qy$ – J. W. Tanner Feb 09 '21 at 17:43
  • @PM2Ring: Yes that is the definition of `GCD` i.e. the greatest number that divides both $x$ and $y$. – Jim Feb 09 '21 at 18:51
  • @PM2Ring: That was bad phrasing from my side. It is the smallest number reached from that set of divisions but somehow it is the greatest divider – Jim Feb 09 '21 at 20:56
  • @PM2Ring: None of the decreasing numbers besides $7$ is a divisor of $14441$ though. So how do they retain the factors along the process exactly? – Jim Feb 09 '21 at 21:22
  • Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/119564/discussion-between-pm-2ring-and-jim). – PM 2Ring Feb 09 '21 at 21:24
  • @PM2Ring: Replied there, I am sorry just saw your message – Jim Feb 09 '21 at 22:29
  • By the dupe, the table implies $\,(14441,3565) = (3565,189) = \ldots = (28,21) = (21,7) = (7,0) = 7,\,$ where we use the common notation $\,(x,y):=\gcd(x,y)\ \ $ – Bill Dubuque Feb 10 '21 at 00:13
  • 2
    https://math.stackexchange.com/questions/3379695/why-does-the-euclidean-algorithm-for-finding-gcd-work/3379763#3379763 – Ethan Bolker Feb 10 '21 at 00:16
  • 1
    Since the remainder sequence is strictly decreasing it must eventually reach $0\,$ (by $\Bbb N$ is well-ordered), so the last nonzero remainder (here $7)$ is the gcd. – Bill Dubuque Feb 10 '21 at 00:18

1 Answers1

0

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.

  • 1
    @Jim I would add to S. Dolan's answer that if you examine the chart in your query, you will notice two attributes that will **always** be present, regardless of the initial values of $x$ and $y$ : [1] The numbers in the left hand column are **strictly decreasing** [2] The *bottom row* of the chart will **always** have $r = 0.$ – user2661923 Feb 09 '21 at 17:51
  • @S. Dolan: "Thus $gcd(,)= gcd(−,)$" and where does $r$ come in the picture? – Jim Feb 09 '21 at 18:10
  • If x-y>y then the next step would be x-2y and y . Repeating this as necessary you get x-qy=r. –  Feb 09 '21 at 18:12
  • It seems to me that your answer more focuses on the algorithm, but I still don't get the intuitive idea behind it. I do understand the process – Jim Feb 09 '21 at 19:58
  • 1
    gcd$(x,y)=$ gcd$(x-y,y)$ looks like an intuitive idea to me. –  Feb 09 '21 at 20:22
  • @S.Dolan:So if we have two numbers $x$ and $y$ with $x > y$ we try to see if $y$ divides $x$ evenly. If so then $y$ is the gcd. This is intuitively understood. Now if it does not evenly divide it means we get a remainder $r>0$. I also can intuitively understand that we now can turn our attention to $r$ since if we find that $r$ evenly divides $y$ it is evenly divides $x$ but it is not clear to me at a high level why can't there be some other factor e.g. $z$ inside $y$ where $y>r$ that divides both $x$ and $y$ evenly? Or the intuition is only part of going over the algebraic equalities? – Jim Feb 14 '21 at 16:54
  • $r$ is $x$ minus a multiple of $y$. It would therefore be a multiple of your $z$. –  Feb 14 '21 at 17:07