The GCD of a pair of positive integers a and b (denoted here as gcd(a, b)) is simply the largest positive integer that divides both a and b. The Euclidean algorithm is a simple way to compute the GCD. The Euclidean algorithm is based on the observation that for any positive integers a and b there exist integers q and r with 0 ≤ r < b such that
a = b × q + r
Note that r is simply the remainder when you divide a by b. From this it is easy to show that u is a common divisor of a and b if and only if u is a common divisor of b and r. Since the set of common divisors are identical, it follows that the greatest common divisors are also identical, i.e.,
gcd(a, b) = gcd(b, r)
To get the Euclidean algorithm, one simply applies the above result recursively to gcd(b, r) until we get to rn-1 and rn such that gcd(rn-1, rn) = 0. When this happens, we can conclude that gcd(a, b) = rn. (We would, of course, use mathematical induction to prove this formally.)
One important property of gcd(a, b) that can be derived from the above is that there exist positive or negative integers k and l such that
gcd(a, b) = k × a + l × b
Using this, the book presents a simple proof of the fundamental theorem of arithmetic. The proof starts by using the above property to show that if a prime p divides a × b then it divides either a or b. One can then easily show that purportedly different prime factorizations of a number are in fact identical.
Finally, the book introduces Euler's function. Two integers a and b are said to be relatively prime if
gcd(a, b) = 1
Euler's function, usually denoted φ(n), is the number of integers from 1 to n that are relatively prime with n. Note, in particular, φ(1) = 1 and φ(p) = p - 1 when p is prime. The book claims that Euler's function is a number-theoretical function of great importance (though it does not expand on this claim immediately).
One interesting property of Euler's function is the generalization of Fermat's little theorem: if n is any integer and a is relatively prime with n then
aφ(n) ≡ 1 (mod n)