This is indeed so because no number (b, in particular) may have a divisor greater than the number itself (I am talking here of non-negative integers.)
If a = bt + r, for integers t and r, then gcd(a, b) = gcd(b, r).
Indeed, every common divisor of a and b also divides r. Thus gcd(a, b) divides r. But, of course, gcd(a, b)|b. Therefore, gcd(a, b) is a common divisor of b and r and hence gcd(a, b)gcd(b, r). The reverse is also
true because every divisor of b and r also divides a.
For any pair a and b, the algorithm is bound to terminate since every new step generates a similar problem (that of finding gcd) for a pair of smaller integers. Let Eulen(a,b) denote the length of the Euclidean algorithm for a pair a,b. Eulen(2322, 654) = 6,Eulen(30, 6) = 1. I'll use
this notation in the proof of the following very important consequence of the algorithm:
For every pair of whole numbers a and b there exist two integers s and t such that as + bt = gcd(a, b).
Example
2322×20 + 654×(-71) = 6.
Proof
Let a > b. The proof is by induction on Eulen(a, b). If Eulen(a, b) = 1, i.e., if b|a, then a = bu for an integer u. Hence, a + (1 - u)b = b = gcd(a, b). We can take s = 1 and t = 1 - u.
Assume the Corollary has been established for all pairs of numbers for which Eulen is less than n. Let Eulen(a, b) = n. Apply one step of the algorithm: a = bu + r.Eulen(b, r) = n - 1. By the inductive assumption, there exist x and y such that bx + ry = gcd(b,r) = gcd(a,b). Express r as r = a - bu. Hence, ry = ay - buy;bx + (ay - buy) = gcd(a, b). Finally, b(x - uy) + ay = gcd(a, b) and we can take s = x - uy and t = y.
If two numbers, multiplied by one another make some number, and any prime number measures
the product, then it also measures one of the original numbers.
Let a prime p divide the product ab. Assume pa. Then gcd(a, p) = 1. By Corollary,
ax + py = 1 for some x and y. Multiply by b: abx + pby = b. Now, p|ab and p|pb. Hence, p|b.
Proposition VII.30 immediately
implies the Fundamental Theorem of Arithmetic although Euclid has never stated it explicitly. The first time it
was formulated in 1801 by Gauss in his Disquisitiones arithmeticae.
Any integer N can be represented as a product of primes. Such a representation is unique up to the
order of prime factors.
Since, by definition, a number is composite if it has factors other than 1 and itself, and
these factors are bound to be smaller than the number, we can keep extracting the factors until only prime factors
remain. This shows existence of the representation: N = pqr..., where all p, q, r,... are prime. To prove
uniqueness, assume there are two representations: N = pqr... = uvw... We see that p divides uvw...
By Corollary, it divides one of the factors u,v,w,... Cancel them out. We can go on chipping away on the factors left and
right until no factors remain.
gcd(b, r).
a. Then 
