Unwinding Definitions (Getting Started)

One of the most often asked questions of students that are new to proofs is "How do I get started?" The answer is usually simple: Unwind the definitions. First, look at what you are being asked to prove. Does it involve a term that has been defined (in the lecture or in the text or in the problem)? Write out the definition. What about the assumptions? Do they involve definitions? If so, write those out. Sometimes there are Theorems that are relevant to your problem. If so, write those out. Do not be afraid to jot down everything you know about what you are trying to prove.

Example: The Greatest Common Divisor

The greatest common divisor of two positive integers a and b is the number d = gcd(a, b) that satisfies two properties: (1) d evenly divides a and b and (2) if d' is any other positive integer that evenly divides a and b, then d > d'. We can think of the gcd as a binary operation.

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

gcd(gcd(a, b), c) = gcd(a, gcd(b, 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)).

Example: Algebraic Numbers

A real number a is called an algebraic number if there is a nonzero polynomial p(x) whose coefficients are all rational numbers such that p(a) = 0. An example would be the sqrt(2), the square root of 2. If we let p(x) = x² - 2, then p(sqrt(2)) = 0, so sqrt(2) is an algebraic number. Pretty clearly any root of a rational number is an algebraic number.

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.

Exercises

Prove each of the following.

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

Back to Proofs