Can y'all please explain Euclid's Algorithm and proove how it works???

Question

Please proove it I already know what it is. So please don't waste your time.

Answer 1

Let us suppose that when a is divided by b, the remainder is r. Then:

a=kb+r for some integer k.

Now let us suppose that a and b both are divided evenly by some number, d. Then a=pd and b=qd for some integers p and q. So:

pd=kqd + r

Which implies that:

(p-kq)d = r

Which means that r is also an exact multiple of d. Now suppose that d is the greatest common divisor of a and b. By the previous, it is clearly also a divisor of r. To show that it is the greatest common divisor of b and r, suppose b and r had a common divisor, d' > d. Then a = p'd' + q'd' = (p'+q')d', and so d' is a divisor of a, and thus a common divisor of both a and b greater than d, which is a contradiction. Therefore, the greatest common divisor of b and r is the same as the greates common divisor of a and b, which establishes the correctness of the recursive step of Euclid's algorithm. Q.E.D.

Answer 2

You've seen a formal proof. You can think of it this way: starting with two positive integers a1 > a2, how to pin down their greatest common divisor GCD(a1, a2)? The key observation is that, when you subtract the smaller number from the larger one, the GCD stays the same:

GCD(a1, a2) = GCD(a1-a2, a2).

Now keep subtracting a2 from the first number (getting a1-a2-a2, and so on) until you can't do it anymore because the current first number has gone down below a2. This is, of course, the remainder from dividing a1 by a2. Call it a3. Note that

GCD(a1, a2) = GCD(a1-a2, a2) =...= GCD(a3, a2) = GCD(a2, a3).

Now you've got another pair of numbers, a2 > a3, to work with. Do the same as done before for the pair a1 > a2. You arrive at an a4 < a3 with

GCD(a2, a3) = GCD(a3, a4).

The numbers keep getting smaller, and after N rounds you arrive at a(N+2) = 0. This means that the penultimate number a(N+1) divides aN exactly, so

a(N+1) = GCD(aN, a(N+1)) = ... = GCD(a1, a2).

(since the GCD stays the same all along). Thus we've found the GCD.

Advantages of Euclid's algorithm:
1. It finds the GCD very quickly even for large numbers -- unlike the method based on factorization which requires a vast amount of computation.
2. The algorithm can be used to express the GCD as a linear combination of the two original numbers:

GCD(a1, a2) = t1*a1 + t2*a2

for some signed integers t1 and t2 (and this is very useful). To do this, use the relationship a(n+2) = an - qn*a(n+1), where qn is how many times a(n+1) was subtracted from an (that is, the n-th quotient). This allows you to substitute back all the way along the sequence (starting with the GCD = a(N+1), keep expressing the farthest term of the sequence in terms of the two previous ones until there is nothing left but multiples of a1 and a2).
3. The algorithm extends to polynomials (because in the division process the degree of the remaider keeps going down).