**Theorem.** The binary operation gcd is associative, that is, for any three positve integers a, b and c,

**Strategy.** What do we have to prove? Two gcd's are the same. Where do we start? Let d be one of these gcd's. Let's let d = gcd(gcd(a, b), c). What does this mean? It means (1) d evenly divides gcd(a, b) and c and (2) if d' is any other positive integer that evenly divides gcd(a, b) and c, then d>d'. We must prove d = gcd(a, gcd(b, c)). What does this mean? We must prove two things: (1) d evenly divides a and gcd(b, c) and (2) if d' is some other positive integer that evenly divides a and gcd(b, c), then d>d'.

(1) Since d divides gcd(a, b), d must divide and b. We know d divides c, so d must divide gcd(b, c). So the first part is easy.

(2) Now we suppose d' divides a and gcd(b, c). Then, d' divides b and c, so d' must divide gcd(a, b) too. But then by our assumption, d>d'. And this is all we needed to prove.

**Proof.** Let d = gcd(gcd(a, b), c). Then d divides a, b and c, and hence divides a and gcd(b, c). If d' divides a and gcd(b, c), then d' must divide gcd(a, b) and c, and hence d>d'. Thus d = gcd(a, gcd(b, c)).

q

**Theorem.** If a is an algebraic number and r is a rational number, then a + r is an algebraic number.

**Strategy.** What do we have to prove? a + r is an algebraic number. What does this mean? We must prove that there is a polynomial p(x) with rational number coefficients such that p(a+r) = 0. What is our assumption? We assume (1) a is an algebraic number, that is, there is a polynomial q(x) with rational number coefficients such that q(a) = 0 and (2) r = s/t where s and t are integers. Where do we start? Start with the polynomial we have, q(x), for which q(a) = 0. Can we modify q(x) into a polynomial, p(x), that does what we want: p(a+r) = 0? Yes! Let p(x) = q(x-r). Then p(a+r) = q(a) = 0.

**Proof.** Let q(x) be the nonzero polynomial with rational coefficients for which q(a) = 0. Then p(x) = q(x-r) is also a polynomial with rational coefficients (since r is a rational number) and p(a+r) = 0. Hence a + r is an algebraic number.

q

- The
**least common multiple**of two positive integers a and b, lcm(a, b), is the positive integer m that satisfies the two conditions: (1) a and b evenly divide m and (2) if m' is another positive integer for which a and b divide m', then m < m'. The least common multiple is associative, i.e. for any three positive integers, lcm(lcm(a, b), c) = lcm(a, lcm(b, c)). - If a is an algebraic number and r is a rational number, then the product ra is an algebraic number.

** Next==>**Constructive Versus Existential Proofs

**<==Back To **Mathematical Induction