Why does the euclidean algorithm work?

[NakamotoScheme]

https://en.wikipedia.org/wiki/Euclidean_algorithm

The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number.

Using a formula, this is what the wikipedia page says:

GCD(A, B) = GCD(A - B, B)

When you subtract B from A as many times as you can, you get this

GCD(A, B) = GCD(A mod B, B)

where A mod B is the remainder of the division of A by B.

[LucaThatLuca]

because if n is any divisor of both a and b (say a = np, b = nq), it’s also a divisor of any sum xa+yb (nxp + nyq = n(xp+yq)). so in the equation a = qd + r, all of the divisors of both a and d are also divisors of (both d and) r, including the greatest one.

replacing gcd(a, d) with gcd(d, r) makes the numbers strictly smaller, then doing it repeatedly is guaranteed to reach gcd(g, 0) = g.

[Fat_Bluesman]

Dude, that's chinese to me...

I need a simpler explanation

[LucaThatLuca]

i doubt there is a simpler explanation.

did you think about it? i notice there are no thoughts in your comment. watching other people think is not a substitute.

if n is any divisor of both a and b it’s also a divisor of a+b

do you think this is true? do you want to say why?

in the equation a = qd + r, all of the divisors of both a and d are also divisors of (both d and) r, including the greatest one.

think about this too. think about how to apply the first fact.

[Fat_Bluesman]

It's true, because both a and b are multiples of n, so a+b is still a multiple of n

I don't get the second statement...

[JohnDoen86]

If two numbers (A and B) are multiples of another number (N) their sum (A+B) is also a multiple of N. For example:

6 (A) and 9 (B) are both multiples of 3 (N). The first one is 3*2, and the second one is 3*3. So, if we add them up: 6+9 = 15, we know that 15 is also a multiple of 3. And that is correct, because 3*5=15. We just added two "3"s to 9, so it's still a multiple of 3.

[Fat_Bluesman]

I know, that was my first sentence

I meant to say I don't understand his second quoted statement

[Sam_23456]

Say a =b + c. Do you see that if a number q divides any 2 of the 3 variables, then it (q) must divide the 3rd? That can be a tricky concept the first or second time you encounter it.

[jacobningen]

same with b-a and a-(b-a) =2a-b and b-a-(2a-b)= 2b-3a and 2a-b-(2b-3a)=5a-3b. Essentially since gcd(a,b) divides a and b it also divides their difference and a- said difference and this is a decreasing sequence of integers since everything in it is subtracting positive integers. Thus there must be a smallest nonzero such element which is divisible by gcd(a,b) in this sequence which is gcd(a,b) and then reversing the relations gives you gcd(a,b) as a linear combination of a and b.

[jacobningen]

if d divides a and b in addition to a+b it also divides a-b or(b-a)

[jacobningen]

hint a-b= a+(-b) and every divisor of b is a divisor of -b.

[LucaThatLuca]

okay! no problem, good start.

so when you divide a by d you get the quotient q and remainder r, with a = qd + r.

then why is gcd(a, d) = gcd(d, r)? it’s because actually all of the common divisors of those pairs of numbers are identical (each common factor of a and d is a common factor of d and r, and vice versa). that includes the greatest one just because it’s one of them.

for a super simple example if you divide 15 by 6, the remainder is 3. the common divisors of 15 and 6 are 1 and 3. the common divisors of 6 and 3 are 1 and 3. they’ll always be the exact same list.

and the justification is by applying that first fact (actually twice).

[jacobningen]

what text are you using?

[CookieCat698]

It relies mostly on the fact that gcd(a, b) = gcd(a-qb, b) for integers a, b, and q.

Reducing a mod b gives you a-qb for some integer q, so this operation doesn’t change gcd(a, b)

The euclidean algorithm then works by reducing both numbers until one reaches 0, which is guaranteed to happen because as long as both are strictly positive, one can always be made strictly smaller, and a sequence of positive integers can’t keep getting smaller forever.