Formal MethodsKey to Homework Assignment 3, Part 1February 9, 200780. Prove that if x and y are positive real numbers such that x 6= y, then x/y + y/x > 2.Proof. We assume to the contrary that there exist p ositive real numbers x and y suchthat x 6= y andxy+yx≤ 2.Since x and y are positive, we can multiply both sides of this inequality by the positivereal xy and getx2+ y2≤ 2xy,or, equivalently,x2− 2xy + y2= (x − y)2≤ 0.But we know from the proof of 79 that this is a contradiction: the square of a realnumber can’t be negative, and since x 6= y, x − y 6= 0, and hence (x − y)26= 0. So wehave the contradiction that (x − y)2≤ 0 and (x − y)2> 0. So the assumption thatxy+yx≤ 2must be false, and we can conclude that for all positive real numbers x and y such thatx 6= y,xy+yx> 2.82. Let P1, P2, . . . , Pnbe primes. Prove that for each i = 1, 2, . . . , n, P1P2· · · Pn+ 1 is notdivisible by Pi.Proof. Suppose to the contrary that for some integer i, 1 ≤ i ≤ n, PidividesP1P2· · · Pn+ 1. Then there exists an integer k such thatPik = P1P2· · · Pn+ 1.Subtracting P1P2· · · Pnfrom both sides and factoring givesPik − P1P2· · · Pi−1PiPi+1· · · Pn= Pi(k − P1P2· · · Pi−1Pi+1· · · Pn) = 1.In other words, Pidivides 1, which is impossible. So the assumption that some Pidivides P1P2· · · Pn+ 1 must be false, and we conclude that for each i = 1, 2, . . . , n, Pidoes not divide P1P2· · · Pn+ 1.184. Let A, B, and C be integers such that A2+ B2= C2. Prove that at least one of A andB is even.Proof. Suppose to the contrary that both A and B are odd. Then there exist integersm and n such that A = 2m + 1 and B = 2n + 1. Substituting into A2+ B2= C2, gives(2m + 1)2+ (2n + 1)2= 4m2+ 4m + 1 + 4n2+ 4n + 1 = 4m2+ 4m + 4n2+ 4n + 2 = C2.So C2is even, and by number 70 on page 30, it must be the case that C2is divisibleby 4. Say p is an integer such that C2= 4p. Substituting gives4m2+ 4m + 4n2+ 4n + 2 = 4p,and subtracting 4m2+ 4m + 4n2+ 4n from both sides gives2 = 4p − 4m2− 4m − 4n2− 4n = 4(p − m2− m − n2− n).But this last equation implies that 2 is divisible by 4, which is false. So the assumptionthat both A and B are odd must be false, and if A2+ B2= C2, at least one of A andB must be even.88. Is the statement “If n is any prime, then 2n+ 1 is prime” true? If your answer is yes,prove the statement. Otherwise find a counterexample to the statement.This statement is false. Checking n = 3, which is prime, gives 23+ 1 = 9 = 32,which is not prime. It’s hard to find primes n for which 2n+ 1 is prime. For example,25+ 1 = 33 = 3 · 11, 27+ 1 = 129 = 3 · 43, and 211+ 1 = 3 · 683. This suggests aconjecture: if n is an odd positive integer, then 2n+ 1 is divisible by