Help with Proofs
Date: 10/16/97 at 14:46:12 From: Tim Subject: Help with Proofs Dear Dr. Math, Could you please help me with the following proofs? I am an Arts student who accidentally enrolled in a course called "Mathematical Thinking." It has been ten years since I have been a university student and I could sure use some assistance. 1. Consider the assertion: If r, s are rationals and s cannot = 0, then r/s is rational. Would I use an indirect proof for this? 2. Show that: (i) If p is a prime and p|n squared, then p|n. I know that the Fundamental Theorem of Arithmetic is involved and so is the prime decomposition of n and that of n squared, but I cannot put them together properly. (ii) Show that the above is not true if p is not prime. Would this again use an indirect proof? (iii) Show that if p is prime and p|ab, then p|a or p|b. Wouldn't p|a and p|b, resulting in p|a or p|b? 3. Prove that if p is prime than the square root of p is irrational. I know that I can adapt the proof from square root of 2 is irrational to this, but am not sure how to do this convincingly. I would genuinely appreciate any time, energy and help you can give me. I am struggling with this course, but am willing to learn. Yours truly, Tim in Montreal
Date: 10/16/97 at 15:47:35 From: Doctor Wilkinson Subject: Re: Help with Proofs >1. Consider the assertion: If r, s are rationals and s cannot = 0, > then r/s is rational. > Would I use an indirect proof for this? No. Usually you use an indirect proof when you want to prove something negative. This question is best approached more directly. About all you have to work with is the definition of rational. So substitute this definition into the given conditions. r is rational, so r = a/b, where a and b are whole numbers. s is rational, so s = c/d, where c and d are whole numbers. You also know that c is not 0, since s is not 0. Now what is r/s? It's just (a/b)/(c/d), which is ad/bc, by the rule for dividing by fractions. But ad and bc are whole numbers since a and and b and c are whole numbers. And that's just what the definition of r/s being rational is. >2. Show that: > (i) If p is a prime and p|n squared, then p|n. > I know that the Fundamental Theorem of Arithmetic is involved > and so is the prime decomposition of n and that of n squared, > but I cannot put them together properly. If you want to prove this from the Fundamental Theorem of Arithmetic, write n as a product of primes, then square this product. You don't get any new primes this way, you just get the each of the old primes twice as often. So if p didn't appear among the prime factors of n, it can't appear among the prime factors of n squared. And you know that the factorization into primes is unique, so you can't find some other funny factorization of n squared in which p will appear. > (ii) Show that the above is not true if p is not prime. > Would this again use an indirect proof? This question is not formulated properly. It's not always true for non-primes, but it's true for some. It's true for 6, for example. Why don't you try p = 4 and look for a number whose square is divisible by 4, but which is not itself divisible by 4? Again, don't use an indirect proof when you're looking for an example of something. Use an indirect proof when you're trying to prove there isn't an example. It seems like you're starting to think "indirect proof" whenever you can't get started on a problem. It's not magic! > (iii) Show that if p is prime and p|ab, then p|a or p|b. > Wouldn't p|a and p|b, resulting in p|a or p|b? Actually this theorem is usually used as a starting point for proving the Fundamental Theorem of Arithmetic, but we can go the other way too. I think you need to think of examples when you work on problems. You seem to be trying to do everything too abstractly. Just look at some small numbers. 2 is a prime, so let's take p = 2, a = 2, b = 3. 2 divides 6, but it doesn't divide both 2 and 3, it just divides 2. This is really similar to the first problem. If you write a as a product of primes and b as a product of primes, and multiply these products together, no new primes appear; you just have the prime factors of a and the prime factors of b. So if p appears in this big product, it must already have appeared in the factorization of a or the factorization of b. Unique factorization tells you there can't be some other factorization of ab in which p might appear. >3. Prove that if p is prime than the square root of p is irrational. > I know that I can adapt the proof from square root of 2 is > irrational to this, but am not sure how to do this convincingly. Well, try it! Don't just say you're not sure how. (Hint: use the result of problem 1). The best advice I can give you is to look at more examples when you work problems, and to go ahead and take the plunge and try something. Even if you try something useless, you'll get some insight. Good luck to you - and try to have some fun with it. -Doctor Wilkinson, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Date: 10/16/97 at 17:01:06 From: Tim Subject: Re: Help with Proofs Dear Dr. Wilkinson, Thank you for your advice and help. Sincerely, Tim
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.