Formal MethodsKey to Homework Assignment 3, Part 3February 14, 200799. How many pairs of primes p and q are there such that q − p = 3? Prove your answer.There is one pair: p = 2 and q = 5. So if p is any prime other than 2, then q = p + 3is not prime.Proof. Clearly p = 2 and q = 5 are both primes and q −p = 3. So suppose p is a primegreater than 2. Then p must be odd, because any even number is evenly divisible by 2and if p were even, we would have p = 2k for some k > 1. Since p is odd, there existsan integer m such that p = 2m + 1. So if q is an integer such that q − p = 3, we haveq − (2m + 1) = 3, or q = 2m + 4 = 2(m + 2).So q is even. Furthermore, since q > p > 2, q 6= 2, and hence q is not prime.In summary, then, if p is a prime greater than 2, then p is odd. So if q − p = 3, q iseven, and since q 6= 2, q can’t be prime.101. Prove that if x is any real number greater than 2, then there is a negative number ysuch that x = 2y/(1 + y).If we suppose for the moment that y 6= −1, we can solve the equationx =2yy + 1for y and gety =x2 − x.This suggests the proof.Proof. We assume x is a real number such that x > 2. Since x > 2, 2 − x < 0. So wecan definey =x2 − x.Note that since x > 2, x > 0, and since 2−x < 0, y is negative. Also note that y 6= −1.If it were, we would have−1 =x2 − x, or x − 2 = x, or − 2 = 0.1So we can substitute our value for y into the expression2yy + 1and get2x2−xx2−x+ 1=2x2−xx+2−x2−x=2x2 − x2 − x2= xSo we see that if x is a real number greater than 2, then there is a negative real numbery such thatx =2yy + 1.In fact,y =2x2 − x.102. Prove that if p is an odd integer, then x2+ x − p = 0 has no integer solution.Proof. We prove the contrapositive: Suppose p is an integer and x2+ x − p = 0 hasan integer solution x. Then p is even.The equation x2+ x − p = 0 is equivalent to the equation x2+ x = p, or x(x + 1) = p.If x is even, then x + 1 is odd. So x(x + 1) = p is even. If x is odd, then x + 1 is even.So x (x + 1) = p is even in this case also. So if x2+ x − p = 0 has an integer solution,then p must be even.Alternate Proof. We can also prove this using contradiction. So suppose that p isan odd integer, and x2+ x − p = 0 has an integer solution x. As before, we considertwo cases: x even and x odd. Also as before, we find that in either case p is even, andthis contradicts our assumption that p is
View Full Document
Unlocking...