Euclidean Algorithm please

I'm not sure what the Euclidean algorithm is, example find gcd(1529,14039) using Euclidean algorithm.

It's a strange sequence of operations you use to find the gcd. Here, let me explain with letter.

Say you have 2 numbers, a and b. Start with the one that is larger. Let's say a is larger. What you want to do is write "a" in terms of some integers plus some remainder.

a = (c_1)b + r_1

Now that you know r, do this SAME process again, but with b and r_1.
b=(c_2)r_1 + r_2

Now again!! but with r_1 and r_2!

r_1 = (c_2)r_2 + r_3

See a pattern?? Now keep doing this until 1 of 2 things happen. Eventually you will end up with a 1 or a 0. If you end up with a 1, both of your numbers are coprime, meaning they have no common factor other than 1. If it is 0, you take the *previous* remainder you had. *That* is your common factor. I'll work out your example:

14039 = (9)1529 + 278
1529 = (5)278 + 139
278 = (2)139 + 0

So greatest common factor is 139.

Euclid's theorem is used to systematically find the greatest common denominator (gcd) of two numbers. It involves recursively subtract one number from the other until one of them is zero, the remaining non-zero number is the gcd.

in this case, 14039 -1529 = 12510, gcd (12510 , 1529 ) = gcd (14039, 1529)
again, 12510 - 1529 = 10981, gcd (10981, 1529) = gcd (14039, 1529)
............ gcd(278, 1529) = gcd(139, 0)

so gcd(14039,1529) = 139

indeed, 14039 = 101*139 and 1529 = 11*139