Even/odd proofs: Practice problems Solutions

1 Math 347 Worksheet on Even/odd HildebrandEven/odd proofs: Practice problemsSolutionsThe problems below illustrate the various proof techniques: direct proof, proof by contraposition, proof bycases, and proof by contradiction (see the separate handout on proof techniques). For each of these prooftechniques there is at least one problem for which the technique is appropriate. For some problems , morethan one approach works; try to find the simplest and most natural method of you areusing a direct proof, state the method of proof you are the proofs you should use only the definitions and assumptions stated above; inparticular, do not use any results or notations from number theory that you may attention to the write-up. In all but the simplest cases, this requires doing some preliminaryscratch work before writing up a formal proof. Specifically, proceed in two stages as follows: Stage 1: Produce outline of with scratch work to come up with a flow chart of the proof, showing the steps involved and their logical connections, with brief justifications foreach step.

2 For this part, you can make liberal use of logical symbols ( , ) and abbreviations( , def. of ). Stage 2: Produce proper write-up:Once you have a step-by-step outline of the argument,convert it to a proper proof, using complete sentences and English words rather than logical sym-bols (such as , , ). Double-check your write-up to make sure that it makes both logical andgrammatical and products of Even/odd the following statements:(a) Ifnandmare both odd, thenn+mis even .(b) Ifnis odd andmis even , thenn+mis odd.(c) Ifnandmare both even , thenn+mis even .(d) Ifnandmare both odd, thennmis odd; otherwise,nmis give a proof for the first statement, (a); the other statements, (b) (d), can be proved in an analogousway.(a) Proof of nandmodd n+meven :As usual, in order to better show the structure of the proof, we writeeach step on a separate line. (A pro-style proof would consist of a single continuous paragraph, but this makes itharder to parse the argument.)

3 Supposenandmare odd integers. Thenn= 2k+ 1andm= 2l+ 1for somek, l Z, by the definition of an odd integer. Thereforen+m= (2k+ 1) + (2l+ 1) = 2(k+l+ 1). Sincekandlare integers, so isk+l+ 1. Hencen+m= 2pwithp=k+l+ 1 Z. By the definition of an even integer, this shows thatn+mis even . squares:Prove the following:(a) Letnbe an integer. Ifn2is odd, thennis odd.(b) Letnbe an integer. Ifn2is even , thennis even .(c) Letnbe an integer. Thenn2is odd if and only ifnis 347 Worksheet on Even/odd of (a):We proof the statement in (a) by contraposition. Since the negation of even is odd , the contra-positive of the statement (a) is is:(a) Letnbe an integer. Ifnis even , thenn2is of (a) : Assumenis an even integer. Thenn= 2kfor somek Z, by the definition of an even integer. Squaring both sides, we getn2= (2k)2= 4k2= 2(2k2). Sincekis an integer, so is2k2. Hencen2= 2pwithp= 2k2 Z. Thereforen2is even , by the definition of an even integer. (b) can be proved in the same way as (a).

4 Proof of (c):Here we have an if and only if statement, which breaks into the following two implications:(i)Letn Z. Ifn2is odd, thennis odd.(ii)Letn Z. Ifnis odd, thenn2is , (i) is the same as (a), while (ii) is the contraposition of (b), and hence equivalent to (b). Thus, (c) is a consequenceof (a) and (b). application I: Sums of odd perfect a sum of two perfect squares be anotherperfect square? Sure; for example, 32+ 42= 52, 52+ 122= 132, 62+ 82= 102, 72+ 242= , no matter how much you try, you won t find any examples in which the two perfect squareson the left are both odd. Your task is to prove this, :Prove that a sum of two odd perfect squares is never a perfect square.(An interesting consequence of this result is that in any right triangle in which all sides have integerlength at least one of the two shorter sides must be of even length.)Proof:The argument given below makes use of the results of problems 1 and 2. Without using these results, theproof would become a bit longer.

5 One would need to consider separately the cases whenn, m, pbelow have a specifiedparity ( even or odd), and show that in each of these cases a contradiction first restate the result to be proved in a more explicit form:( )Ifsandtare odd perfect squares, thens+tis not a perfect of( ):We use the method of contradiction. Supposesandtare odd perfect squares, and assume thats+tis also a perfect square. Thens=n2,t=m2, ands+t=p2, for somen, m, p Z, by the definition of a perfect square. Since, by assumption,s=n2andt=m2are odd, the integersnandmmust be odd as well (byProblem 2). Hencen= 2k+ 1andm= 2l+ 1for somek, l Z, by the definition of an odd integer. Since the sum of two odd numbers is even (by Problem 1),s+t=p2is even . Hencep, must be even as well (by Problem 2). Thereforep= 2hfor someh Z, by the definition of an even 347 Worksheet on Even/odd Hildebrand Substitutingn= 2k+ 1,m= 2l+ 1, andp= 2hinton2+m2=p2we get(2k+ 1)2+ (2l+ 1)2= (2h)2,4k2+ 4k+ 1 + 4l2+ 4l+ 1 = 4h2,4(k2+k+l2+l) + 2 = 4h2,2(k2+k+l2+l) + 1 = 2h2.

6 In the last equation the left side is an odd integer since it is of the form2j+1, wherej=k2+k+l2+lis an integer. On the other hand, the right side is an even integer since it is of the form2i, wherei=h2is an integer. Since an integer cannot be simultaneously even and odd, we have arrived at a contradiction. Therefore our assumption thats+tis a perfect square is false. Thus, we have shown that ifsandtare odd perfect squares, thens+tcannot be a perfect square. application, II: Quadratic equations with no integer/rational Solutions :(a) Prove the following:Ifa, b, careoddintegers, then the equationax2+bx+c= 0has no integer solution.[This is the equation considered at the beginning of Chapter 2 of the text and it is a niceillustration of the power of parity arguments .Don t look up the solution in the text;try to find it on your the proof, you may use any of the properties of sums andproducts of Even/odd integers established in Problem 1.]

7 ](b) Prove that the above result remains true if integer solution is replaced by rational solution .Proof of (a):We use the method of contradiction. Supposea, b, care odd integers and there exists an integer solutionxto the equationax2+bx+c= 0. Thena= 2h+ 1,b= 2i+ 1,c= 2j+ 1, for someh, i, j Z, by the definition of an odd integer. We now consider separately the casesxeven andxodd: Ifxis even , thenx= 2kfor somek Z, by the definition of an even integer. Therefore,ax+bx+c= (2h+ 1)(2k)2+ (2i+ 1)(2k) + (2j+ 1)= 2[(2h+ 1)2k2+ (2i+ 1)k+j] + +bx+cis of the form2[..] + 1, where the expression[..]is an integer. Thereforeax2+bx+cis an odd integer. Ifxis odd, thenx= 2k+ 1for somek Z, by the definition of an odd integer. Therefore,ax+bx+c= (2h+ 1)(2k+ 1)2+ (2i+ 1)(2k+ 1) + (2j+ 1)= (2h+ 1)(4k2+ 4k+ 1) + 2k(2i+ 1) + 2i+ 1 + 2j+ 1= 4(2h+ 1)(k2+k) + 2h+ 1 + 4ki+ 2k+ 2i+ 1 + 2j+ 1= 2[2(2h+ 1)(k2+k) +h+ 2ki+k+i+ 1] + +bx+cis of the form2[..] + 1, where the expression[.

8 ]is an integer. Thereforeax2+bx+cis an odd integer. Thus, in either case, we obtain thatax2+bx+cis an odd integer and hence cannot be equal to0. Therefore, our assumption that there is an integer solution to the equationax2+bx+c= 0is false,so this equation has no integer Solutions . 1 Hint: Consider the parity ( even or odd) ofax2+bx+ 347 Worksheet on Even/odd HildebrandOutline of proof of (b):This is harder, but the basic idea is the same as for (a). We assume thata, b, care oddintegers and that there exists a rational solutionxto the equationax2+bx+c= 0, and we try to derive a contradictionfrom this. Writingxasx=p/qfor some integerspandq, we get the equationap2+bpq+cq2= 0, which is of asimilar type as the equation considered in (a), and can be handled by considering separately the cases (i)peven andqodd, (ii)podd andqeven, (iii)podd andqodd. (By the FACT( )stated below, we don t need to consider thecase whenpandqare both even .) application, III: Irrationality proofs: Prove that 2 is will prove this result using the followingFACT:2( )Any rational numberxcan be written in the formx=p/q, wherep Z,q 0, andat least one ofpandqis will also use the following result proved in problems 2:( )Letnbe an integer.

9 Thenn2is even if and only ifnis of irrationality of 2: We argue by contradiction and suppose that the statement is false, , that 2isnotirrational. Then 2is rational. By the definition of rational numbers, this means that 2can be written as 2 =p/q, wherepandqare integers withq6= 0. By( )we can further assume that at least one ofpandqis odd. Squaring each side of 2 =p/qand clearing denominators, we get2 =(pq)2=p2q2,2q2=p2. Thusp2is2times an integer, and hence must be even , by the definition of an even integer. By( )it follows thatpmust be even as well. Hencep= 2k, for somek Z, by the definition of an even integer. Substituting this into (1) gives2q2= (2k)2,q2= 2k2. Thusq2is2times an integer, and hence must be even , by the definition of an even integer. Therefore,bothpandqmust be even . This is a contradiction to( ). Hence our assumption that 2is rational was false. Therefore 2must be irrational..2 The part in boldface, at least one ofpandqis odd , is the nontrivial part here.

10 It is intuitively obvious: if you cancelas many factors 2 as possible inp/q, then in the resulting fraction, sayp /q , there are no 2 s left to cancel, so at least oneofp orq is not divisible by 2, and thus must be odd. A fully rigorous proof requires the Well-Ordering Principle , whichwill be covered