### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# DISCRETEMATHEMATICS MATH245

SDSU

GPA 3.61

### View Full Document

## 18

## 0

## Popular in Course

## Popular in Mathematics (M)

This 67 page Class Notes was uploaded by Camryn Rogahn on Tuesday October 20, 2015. The Class Notes belongs to MATH245 at San Diego State University taught by Staff in Fall. Since its upload, it has received 18 views. For similar materials see /class/225273/math245-san-diego-state-university in Mathematics (M) at San Diego State University.

## Reviews for DISCRETEMATHEMATICS

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/20/15

Math 245 Discrete Mathematics Elementary Number Theory and Methods of Proof Direct Proof and Counterexample Lecture 5 Peter Blomgren Department of Mathematics and Statistics San Diego State University San Diego CA 921827720 blomgrenterminus SDSU EDU http terminus SDSU EDU 51d lecturetexv 110 20060926 224459 blomgren Exp 5 Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Countexexempie e p 153 introduction We have spent quite some time and effort building up our toolbox of logic reasoning We are now ready to apply that toolbox to something the prop erties of integers rational and real numbers We are going to try to establish the truth or falsity of mathematical statements Let the floor ofx denoted 22 be the integer part ofz eg in 3 Consider the two statements 1 VxelR lxiljlzj71 2 VxelRVy lR lxiyll vlclyl It turns out statement 1 is true and 2 is false We are going to look at methods for proving this Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Countexexempie e p 253 Basic Building Blocks Definitions Mathematicians define terms very carefully and precisely most of the time every word and symbol in a definition is there for a reason We are going to start from a few definitions and use our logic toolbox to evaluate the truth or falsity of mathematical statements Definition Even and Odd Integers An integer n is even if and only if n 2k for some integer k An integer n is odd if and only if n 2k 1 for some integer k Symbolically ifn E Z then H is even ltgt 3k 6 Z such that n 2k nisodd lt2 3k Zsuchthatn2k1 Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Countexexempie e p 353 Deductions Now If we know Then we can deduce n has the form 2k 71 has the form 2k 1 a particular integer n is even a particular integer n is odd a particular integer n has the form 2k 71 is even a particular integer n has the form 216 1 n is odd We can now answer the following questions lsOeven Yes 02 0 Is e301 odd Yes e301 2 e151 1 If a E Z and b E Z is 611212 even Yes 6112b 2 3112b lfaEZandbEZi510a8b1odd Yes 10a8b125a4b1 Here we have also use the fact that sums and products of integers are integers Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Countexexempie e p 453 Prime Numbers Definition Prime Composite Integers An integer n is prime if and only if n gt 1 and for all positive integers r and s ifn r s then r 1 or s 1 An integer n is composite if and only if n r s for some positive integers r andswithry landsy l Symbolically if n E N 1 then nisprime ltgt VasENifnrsthenr1ors1 n is composite lt2 3r 3 E N such that n r s andry landsy l Notice that the definitions of prime and composite are negations of each other Hence every integer greater than 1 is either a prime or a composite Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Couhtetexempie e p 553 Writing Proofs Existential Statements There are two ways of proving the statement 32 6 D such that Q2 There is an SDSU student interested in Mathematicsquot 1 Find an 2 E D such that Q2 is true Find an SDSU student interested in Mathematics 2 Give a set of directions for finding such an 2 E D Important The directions must guarantee that we find 2 E D Both these methods are called constructive proofs of existence They tell us something exists and tell us how to find it Elemehtety Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Couhtetexempie e p 653 Nonconstructive Proofs of Existence It is also possible to prove the existence of an 2 E D such that Q2 is true by 1 Showing that the existence of a value of 2 that makes Q2 true is guaranteed by an axiom or a previously proved theorem N Showing that the assumption that there is no such 2 leads to a contradiction These proofs give us no information about how to find such a value hence they are called nonconstructive Clearly if you are looking for a value making Q2 true a non constructive proof is a disadvantage Such a proof is still useful since it tells us there is indeed something to look for Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Couhtetexempie e p 753 Proving Universal Statements Method of Exhaustion The vast majority of mathematical statements to be proved are uni versal basically on the form Va 6 D7 if P2 then The method of exhaustion can be used in two situations 1 When D contains a finite number of elements 2 When there are only a finite number of elements in the truth set of P2 The method of exhaustion will make you exhausted quickly you have to plug in every possible value of 2 E D or from the truth set of and then check P2 a This is sometimes called a brute force method and quickly becomes infeasible Elemehtety Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Couhtetexempie e p 553 A Tool for a Better Method Proving Universal Statements Clearly we would like a method of proving universal statements which works regardless of the size of the domain over which the statement is quantified The underlying idea of the method of generalizing from the generic particular To show that every element of a domain satisfies a certain prop erty suppose 2 is a particular but arbitrarily chosen element of the domain and show that 2 satisfies the property We will use this tool in the Method of Direct Proof Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Countexexempie e p 953 The Method of Direct Proof Method of Direct Proof 1 Express the statement to be proved in the form sz E D if Pz then Qzquot 2 Start the proof by supposing 2 is a particular but arbitrarily chosen element of D for which the hypothesis Pz is true Abbreviated suppose 2 E D and Pzquotl 3 Show that the conclusion Qz is true by using definitions previously established results and the rules for logical infer ence Note The point of selecting 2 arbitrarily is that everything you deduce about a generic element in D will be true for every other element in D Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Countexexempie e p 1053 Let s Try lt Theorem If the sum of two integers is even so is their difference Restatement me E Z if m n is even then m 7 n is even 1 m 11 2k for some k E Z solve for 2 m 2k 7 n substitute into m 7 n 3 m7n2k7n7n2k72n2k7n We re done Sort of Let39s clean it up and make it more readable Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Countexexempie e p 1153 Our First Theorem with Proof Theorem If the sum ofany two integers is even then so is their difference Proof Suppose m and n are integers so that mn is even By definition of even m n 2k for some integer k Subtracting n from both side gives m 2k 7 n then m 7 n 2k 7 n 7 n by substitution 2k 7 2n by combining terms basic algebra 2k by factoring out a 2 basic algebra But k7n is an integer because it is the difference between integers Hence m 7 n equals 2 times an integer and so by the definition of even m 7 n is even D Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Countexexempie e p 1253 How to Write a Proof 1 Write the theorem to be proved 2 Clearly mark the beginning of the proof with the word proof 3 Make your proof self39contained In the body text of the proof identify each variable used in the proof The reader should not have to guess or assume anything 4 Write proofs in complete English sentences This does not mean that you should avoid using symbols and shorthand abbreviations just that you should incorporate then into sentences Your proofs It39s better you are too detailed but don39t be ridiculous Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Couhtexexemple e p 1353 Common Mistakes 1 of 2 1 Arguing from Examples Examples help understanding but special cases do not prove general statements Think of the statement All odd number integers greater than 1 are primequot and the examples 3 5 7 2 Using the same letter to mean two things For instance ifm and n are two even integers don39t say m 2r and n 2r Disaster You39re saying m n Use eg m 2r and n 23 3 Jumping to 8 Conclusion To state that something is true without giving adequate reason quotcuz Isay soquot is not sufficient logical argument Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Couhtexexemple e p 1453 Common Mistakes 2 of 2 4 Begging the Question To assume what it to be proved Usually in a logically equivalent form that looks different 5 Misuse of the Word quotifquot Using the word if instead of since or because Consider Suppose p is a prime pr is prime tnen p cannot be written as a product of two smaller numbersquot and Suppose p is a prime Since p is prime p cannot be written as a product of two smaller numbersquot In the first formulation the primeness ofp seems to be in doubt in the second sentence Such imprecise use of language can cascade through the proof and generate problems later Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Couhtexexemple e p 1553 Comic Relief The Odd Prime Number Theory An engineer a mathematician and a physicist are testing the theory that all odd numbers are prime Physicist 1 is prime 3 is prime 5 is prime 7 is prime 9 must be experimental error 11 is prime 13 is prime That39s enough data points the theory is truequot Mathematician By convention 1 is not prime but 3 is a prime 5 is a prime 7 is a prime 9 is not a prime counterexample claim is false Engineer 1 is prime 3 is prime 5 is prime 7 is prime 9 is prime 11 is prime 13 is prime 15 is prime 17 is prime 19 is prime Hmmm theory appears to be truequot Second Engineer who slept through some early math classes What do you mean 1 is not prime Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Couhtexexemple e p 1653 DispromC By Counterexample Disproving a statement of the form Va 6 D if Pz then amounts to proving that the negation of the statement is true 32 6 D such that Pz and N Qz Disproof by Counterexample To disprove a statement ofthe form sz E D if Pz then Qzquot nd a value of 2 in D for which Pz is true and Qz is false Such an 2 is called a counterexample Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Couhtexexempie e p 1753 Examples Disproofs Bogus Theorem 1 All odd integers greater than 1 are primequot Disproof Since 9 2 4 1 it is odd Further 9 33 which shows that 9 is a composite number hence not a prime Bogus Theorem 2 Va 6 1R 1 6 R if a2 b2 then a b Disproof Let a 1 and b 71 a2 b2 1 but a 75 b Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Couhtexexempie e p 1353 Famous Proofs and Disproofs Fermat39s Last Theorem If n is an integer greater than 2 then the equation 22quot yquot zquot has no solutions where 22 y and z are positive integers Pierre de Fermat lived 1601 1665 Euler s Conjecture a4 b4 c4 d4 has no integer solutions Leonhard Euler lived 1707 1783 Fermat s Last Theorem was nally proved by Andrew Wiles in September 1994 Euler s Conjecture was disproved by Noam Elkie Harvard Uni versity in 1986 One counterexample is 958004 2175194 4145604 42274814 found by Roger Frye of Thinking Machines Corporation Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Couhtexexempie e p 1953 Homework 4 Due 1062006 12noon GMCS587 version 1 3rd Edition l 2nd Edition Problems 31 27 31 37 49 l 31 12 24 35 Please use the 3rd Edition numbering when handing in your solutions Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Couhtexexempie e p 2053 Divisibility and Number Theory introduction Epp 32 skip Divisibility of the central concept of number theory the study of properties of integers Important applications of number theory include keeping your credit card number safe when you hit buy nowquot in your web browser We look at some more statements about integers and prove a few of them Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Countexexemple e p 2153 Divisibility of an integer Definition Divisibility If n and d are integers and cl 73 0 then n is divisible by d if and only if n d k for some integer k Alternatively we say that n is a multiple of cl or cl is a factor of n or d is a divisor of n or d divides n The notation dln is read d divides Symbolically if n and d are integers and d 7f 0 dln ltgt HkEZ ndk Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Countexexemple e p 2253 Divisibility Examples Example 1 Suppose a and b are positive integers and all Is a g 1 Solution all means that b k a for some positive integer k since both a and b are positive Therefore k 2 1 This shows that b k a 2 a by multiplying both sides of the inequality by the positive integer a Hence we can conclude that a g b Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Countexexemple e p 2353 Divisibility Examples Example 2 a If a and b are integers is But 3b divisible by 3 b If k and m are integers is 10km divisible by 5 Solution 8 By basic algebra the distributive law we can write 3a 3b 3a b and since a b is an integer being a sum of integers we have shown that 3l3a 31 b By basic algebra the associative law we can write 10km 5 2km where 2km is an integer being a prod uct of integers We have shown 510km Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Countexexemple e p 2453 Divisibility Primeness and Transitivity We can use the concept of divisibility to define primeness Definition Prime Integer Alternative A positive integer n gt 1 is prime if and only if its only divisors are 1 and n Divisibility is transitive If one number a divides a second number I alb and the second number divides a third number c blc then the first number divides the third ale This is an important fact lets prove it Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Couhtexexemple e p 2553 Proof Divisibility is a Transitive Property Theorem For all integers a b and c if all and bio then ale Proof Suppose a b and c are particular but arbitrarily chosen integers such that all and bio By the definition of divisibility we know that all ltgt b a r for some integer r and bio ltgt c b t for some integer 75 Combining these two we have c b t a r 757 for some integers r and 75 Hence we can write c a r t where r t is an integer which shows that ale D Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Couhtexexemple e p 2653 Does all and bla imply a b Question Is it true that for all integers a and b if all and bla then a 1 Solution Suppose a and b are integers such that all and bla then we must have By substitution barbsr which is true if and only if s r 1 Le both r and s are divisors of 1 The only divisors of 1 are 1 and 71 r s 71 gives us infinitely many counterexamples a 71 thus we conclude all and bla 75 ab Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Couhtexexemple e p 2753 The Unique Factorization Theorem Theorem The Unique Factorization Theorem Given any integer n gt 1 there exists a positive integer k distinct prime numbers 131 p2 pp and positive integers 51 52 5k such that 7119 4932 3919 and any other expression of n as a product of prime numbers is identical to this except possibly for the order in which the factors are written The proof is beyond the scope of this class but the theorem is impor39 tant enough that you should know it If you write the factors such that 131 lt p2 lt lt pk then the form is called the standard factored form Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Couhtexexemple e p 2553 Using the Unique Factorization Theorem Question Suppose m is an integer such that 8765432m1716151413121110 Does 17lm Solution 17 is a prime number Since it is a factor on the right side of the equation it must also be a factor on the left side of the equation by the Unique Factorization Theorem UFT But 17 cannot factor any of the numbers 8 7 6 5 4 3 2 since it is too large Hence it must factor m so 17lm Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Couhtexexemple e p 2953 The Quotient Remainder Theorem Theorem QuotientRemainder Given any integer n and a positive integer cl there exist unique integers q the quotient and r the remainder such that nclqr7 and 0 rltd Example Say you have 10 cookies n 10 and you want to dis tribute as many of them as possible among 3 children cl 3 so that each child receives the same number of cookies of coursel After you have distributed 3 sets q 3 of 3 cookies you have one r 1 remaining By the quotienteremainder theorem you got it right there is only one unique way of solving the problem We are going to need more tools before we can prove this theorem we39ll get to it in a couple of weeks for now we take it as given Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Couhtexexemple e p 3053 Notation div and mod Definition Given a nonvnegative integer n and a positive integer cl we define n div d q the integer quotient obtained when n is divided by d n mod d r the integer remainder obtained when n is divided by d The quotientremainder theorem tells us that nmodde 07177d71 and nmodd0 ltgt dln Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Couhtexexemple e p 3153 Using div and mod Example February 17 2005 was a Thursday What day was it one year earlier Solution 366 days passed since February 17 2004 and each week has seven days Since 366 div 7 527 and 366 mod 7 2 it follows that exactly 52 weeks and 2 days passed between the two dates Thus 2172004 was a Tuesday Elemehtexy Numbex Theoxy ehd Methods of Pxoof Dueot Pxoof ehd Couhtexexemple e p 3253 The Parity of an integer The parity property is the fact that an integer is either even or odd We use the quotient39remainder theorem and and our new operation mod to classify the integers For an integer n If n mod 2 0 then n is even lfnmod 2 1 thenn is odd Elemenmy Numbex Them and Methods 5 Pxoof Dueci Pxoof and ccumexexampie e p 3353 Proof by Dividing into Cases H Theorem Any two consecutive integers have opposite parity Proof Let m and m 1 be two consecutive integers By the parity property m is even or m is odd case 1 m is even case 2 m is odd In this case m 2k for some k E Z and so m 1 2k 1 which is odd by the definition of odd In this case m is even and m1 is odd In this case m 2k 1 for some k E Z and so m 1 2k 2 2k 1 which is even by the definition of even In this case m is odd and m 1 is even It follows that regardless of which case occurs for the particular choice ofm and m 1 one of them is even and the other one is odd Hence we have proved the theorem D Elemeniaxy Numbex Thmy and Methods 5 Pxoof Dueci Pxoof and Counbexexample e p 3453 Homework 4 Due 1062006 12noon GMCS587 version g 3rd Edition 2nd Edition Problems 31 27 31 37 49 l 31 12 2435 33 17 25 26 36a 36b 33 16 24 25 35 Please use the 3rd Edition numbering when handing in your solutions Elemenmy Numbex Them and Methods 5 Pxoof Dueci Pxoof and ccumexexampie e p 3553 Checking the Road Map Where are we Are we lost In chapters 1 and 2 we talked about logic in its purest form learning about logic operator and connectives truth tables compound state ments conditional statements quantified statements predicates Things were pretty good some of y all fell asleep since things were quite cozy and familiar Now in chapter 3 we are talking about different methods of proof where we must use our logic toolbox from chapters 1 and 2 to prove that certain mathematical statements are true We are working in the context of number theory the study of the properties of integers We are introducing both proof39methodologies and number theory at the same time maybe a source of confusion Elemeniaxy Numbex Thmy and Methods 5 Pxoof Dueci Pxoof and Counbexexample e p 3653 Review Proof Techniques The Method of Direct Proof Method of Direct Proof 1 Express the statement to be proved in the form sz E D if Pz then Qzquot 2 Start the proof by supposing 2 is a particular but arbitrarily chosen element of D for which the hypothesis Pz is true Abbreviatedz suppose 2 E D and Pzquot 3 Show that the conclusion Qz is true by using definitions previously established results and the rules for logical infer ence Elemehtexy Number Theory ehd Methods of Proof Dueot Proof ehd Countexexempie e p 3753 Review Proof Techniques Disproof by Counterexample Disproof by Counterexample To disprove a statement of the form sz E D if Pz then Qzquot find a value of 2 in D for which Pz is true and Qz is false Such an 2 is called a counterexample Example Disproof of a4 b4 c4 d4 does not have any positive integer solutions quot Elemehtexy Number Theory ehd Methods of Proof Dueot Proof ehd Countexexempie e p 3353 Review Proof Techniques Division into Cases Proof by Division into Cases Conjectures can often be simplified by dividing a proof into cases When a conjecture is true in all cases it is a theorem If a cone jecture is a theorem a proof by cases may simplify the argument since each case is a simpler form of the conjecture Also if a conjecture is not a theorem an attempted proof by cases may simplify the conjecture and make it easier to understand why the proof is not succeeding Example The successful proof of Any two integers consecutive have opposite parityquot Elemehtexy Number Theory ehd Methods of Proof Dueot Proof ehd Countexexempie e p 3953 Review Number Theory Divisibility Definition Divisibility If n and d are integers and cl 73 0 then n is divisible by d if and only if n d k for some integer k Alternatively we say that n is a multiple of cl or cl is a factor of n or d is a divisor of n or d divides n The notation din is read d divides Symbolically if n and d are integers and d 7f 0 din ltgt HkEZ ndk Elemehtexy Number Theory ehd Methods of Proof Dueot Proof ehd Countexexempie e p 4053 Review Number Theory Primeness Two Definitions Definition Prime Composite Integers An integer n is prime if and only if n gt 1 and for all positive integers r and s ifn r s then r 1 or s 1 An integer n is composite if and only if n r s for some positive integers r andswithr7 1and37 1 Symbolically if n E N 1 then nisprime ltgt VasENifnrsthenr1ors1 n is composite lt2 3r 3 E N such that n r s andr7 1and37 1 Definition Prime Alternative A positive integer n gt 1 is prime if and only if its only divisors are 1 and n Elemehtexy Numbex Theory ehd Methods of Pxoof Dueot Pxoof ehd Countexexemple e p 4153 Review Number Theory Integer Division and Modulus Definition Integer Division and Modulus Given a non39negative integer n and a positive integer cl we define n div d q the integer quotient obtained when n is divided by d n mod d r the integer remainder obtained when n is divided by d Elemehtexy Numbex Theory ehd Methods of Pxoof Dueot Pxoof ehd Countexexemple e p 4253 Review Number Theory Unique Factorization Theorem Theorem The Unique Factorization Theorem Given any integer n gt 1 there exists a positive integer k distinct prime numbers 131 p2 pk and positive integers 51 52 5k such that 7119 vizquot192k and any other expression of n as a product of prime numbers is identical to this except possibly for the order in which the factors are written The proof is beyond the scope ofthis class but the theorem is impors tant enough that you should know it Know the statement and how to use it If you write the factors such that 131 lt 132 lt lt pk then the form is called the standard factored form Elemehtexy Numbex Theory ehd Methods of Pxoof Dueot Pxoof ehd Countexexemple e p 4353 Review Number Theory QuotientRemainder Theorem Theorem QuotientRemainder Given any integer n and a positive integer cl there exist unique integers q the quotient and r the remainder such that nclqr7 and 0 rltd Those are our theoretical toys so far Now lets move forward Elemehtexy Numbex Theory ehd Methods of Pxoof Dueot Pxoof ehd Countexexemple e p 4453 Exercise Representation of integers Modulo 4 Conjecture All integers can be written in one of the forms n4q or n4q1 or n4q2 or n4q3 Solution Let n be an integer We apply the quotienteremainder theorem with d 4 this implies there exists a unique pair of quotient39remainder pair q and r such that n 4qr7 where r 6 071273 This shows that the conjecture is true This seemingly simple result will be useful in a few slides Elemehtexy Number Theory ehd Methods of Proof Dueot Proof ehd Couhtexexemple e p 4553 The Mathematical Let The statement quotLet n be an integerquot means quotSuppose n is a particular but arbitrarily chosen integer quot That is we randomly select an integer from Z The statement may look casual but it means something very specific in the language of mathematics You will see similar statements all over the math39literature o Letp be a prime such thatp 2quot 7 1 for some n E Zquot 0 Let r and s be two real numbers such thatquot Elemehtexy Number Theory ehd Methods of Proof Dueot Proof ehd Couhtexexemple e p 4653 Exercise The form of the Square of an Odd Integer 1 of 2 Conjecture The square of any odd integer has the form 8m 1 for some integer m Solution Let n be an odd integer By the quotient39remainder theoe rem n can be written in one of the forms see previous exercise n4q or n4q1 or n4q2 or n4q3 Now since 12 is odd this reduces the possibilities to the forms n4q1 or n4q3 case1 We have that n 4g 1 for some integer q therefore 2 7 2 7 2 7 2 n e 4q1 716q 8q1782q q1 RH integer Identifying m 2g2 q shows that n2 8m 1 for some integer m end case1 Elemehtexy Number Theory ehd Methods of Proof Dueot Proof ehd Couhtexexemple e p 4753 Exercise The form of the Square of an Odd Integer 2 of 2 case2 We have that n 4g 3 for some integer q therefore 122 4q32 16q224q9 82q23q 11 W integer Identifying m 2g2 Sq 1 shows that n2 8m 1 for some integer m end case2 case1 and case2 shows that given any odd integer 12 whether of the form 4g 1 or 4g 3 its square can be written on the form n2 8m 1 1 for some integer m D Elemehtexy Number Theory ehd Methods of Proof Dueot Proof ehd Couhtexexemple e p 4553 Exercise Making Change The following algorithms gives makes change it determines how many quarters 25c q dimes 10c d nickels 5c and pennies 1c 3 equals 0 the total amount of change Givenc 099 069 083 q c div 25 3 2 3 02 0 mod 25 24 19 8 cl 02 div 10 2 1 0 Cg 02 mod 10 4 9 8 n Cg div 5 0 1 1 p Cg mod 5 4 4 3 Elemenmy Numbex Them and Methods of Pxoof Dnect Pxoof and ccuniexexampie 7 p 4953 Exercise n mod 3 E 0 1 2 Conjecture Any integer n can be written in one of the three forms nSq or nSq1 or nSq2 Solution Let n be an integer By the quotient39remainder theorem with d S there exist unique integers q and r such that nSqr7 where0 rltd This shows that n can be written in one of the forms above D We are now going to use this result to show something a little more complicated Elemeniaxy Numbex Thmy and Methods of Pxoof Duect Pxoof and Counbexexample 7 p 5053 Exercise The Product of Three Consecutive Integers 1 of 2 Conjecture The product of three consecutive integers is divisible by 3 Solution Let n n 1 and n 2 be three consecutive integers By the quotient39remainder theorem see previous exercise n can be written in one of the forms nSq or nSq1 or nSq2 case1 n Sq for some integer q in this case the product Mn 1n 2 3q3q 13q 2 3 939 13q 2 integer which shows that Slnn 1n 2 Elemenmy Numbex Them and Methods of Pxoof Dnect Pxoof and ccuniexexampie 7 p 5153 Exercise The Product of Three Consecutive Integers 2 of 2 case2 n Sq 1 for some integer q in this case the product nn1n2 3q13q23q3 33q 13q 2M 1 integer which shows that Slnn 1n 2 case3 n Sq 2 for some integer q in this case the product nn1n2 3q23q33q4 33q 2M 13q 4 integer which shows that Slnn 1n 2 In all three cases we have Slnn 1n2 thus we have shown that the product of any three consecutive integers is divisible by 3 D Elemeniaxy Numbex Thmy and Methods of Pxoof Duect Pxoof and Counbexexample 7 p 5253 Homework 4 Due 1062006 12noon GMCS587 Final Version 3rd Edition 2nd Edition Problems 31 27 31 37 49 31 12 24 35 33 17 25 26 36a 36b 33 16 24 25 35 34 7 8 9 10 24 29 43 34 7 18 30 Please use the 3rd Edition numbering when handing in your soiutions Writing your name on and stapling your homework is highly rec ommended Elemenmy Numbex Them and Memos of Pxoof Dueci Pxoof and ccuniexexampie 7 p 5353 Math 245 Discrete Mathematics Elementary Number Theory and Methods of Proof Direct Proof and Counterexample Lecture 5 Peter Blomgren Department of Mathematics and Statistics San Diego State University San Diego CA 921827720 blomgrenterminusSDSUEDU httpterminusSDSUEDU Id lecture texv 1 10 20060926 224459 blomgren Exp Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 153 Introduction We have spent quite some time and effort building up our toolbox of logic reasoning We are now ready to apply that toolbox to something the prop erties of integers rational and real numbers We are going to try to establish the truth or falsity of mathematical statements Let the floor ofx denoted be the integer part ofx eg lwl 3 Consider the two statements 1 VxER lx lllxl 1 2 VxERVyER It turns out statement 1 is true and 2 is false We are going to look at methods for proving this Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 253 Basic Building Blocks Definitions Mathematicians define terms very carefully and precisely most of the time every word and symbol in a definition is there for a reason We are going to start from a few definitions and use our logic toolbox to evaluate the truth or falsity of mathematical statements Definition Even and Odd Integers An integer n is even if and only if n 2k for some integer k An integer n is odd if and only if n 2k 1 for some integer k Symbolically if n E Z then n is even ltgt 3k 6 Z such that n 2k nisodd ltgt 3k Zsuchthatn2kL Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 353 Deductions Now If we know Then we can deduce a particular integer n is even 71 has the form 2k a particular integer n is odd n has the form 2k 1 a particular integer n has the form 2k 71 is even a particular integer n has the form 2k 1 n is odd We can now answer the following questions Is 0 even Yes 0 2 0 Is 301 odd Yes 301 2 151 1 If a E Z and b E Z is 6a2b even Yes 6a2b 2 3a2b lfaEZandbEZ is 10a8b10dd Yes 10a8b125a4b1 Here we have also use the fact that sums and products of integers are integers Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 453 Prime Numbers Definition Prime Composite Integers An integer n is prime if and only if n gt 1 and for all positive integers r and 5 if n r 5 then r 1 or s 1 An integer n is composite if and only if n r 3 for some positive integers r andswith r7 1 and s7 1 Symbolically if n E N then nisprime ltgt VrsENifnrsthenr1ors1 n is composite ltgt 3r 3 E N such that n r 3 andr7 1ands7 1 Notice that the definitions of prime and composite are negations of each other Hence every integer greater than 1 is either a prime or a composite Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 553 Writing Proofs Existential Statements There are two ways of proving the statement 3x 6 D such that Qx There is an SDSU student interested in Mathematicsquot 1 Find an a E D such that Qx is true Find an SDSU student interested in Mathematics 2 Give a set of directions for finding such an a E D Important The directions must guarantee that we find a E D Both these methods are called constructive proofs of existence They tell us something exists and tell us how to find it Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 653 Nonconstructive Proofs of Existence It is also possible to prove the existence of an a E D such that Qx is true by 1 Showing that the existence of a value of a that makes Qx true is guaranteed by an axiom or a previously proved theorem 2 Showing that the assumption that there is no such 3 leads to a contradiction These proofs give us no information about how to find such a value hence they are called non constructive Clearly if you are looking for a value making Qx true a non constructive proof is a disadvantage Such a proof is still useful since it tells us there is indeed something to look for Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 753 Proving Universal Statements Method of Exhaustion The vast majority of mathematical statements to be proved are uni versal basically on the form Vx E D if Px then Qx The method of exhaustion can be used in two situations 1 When D contains a finite number of elements 2 When there are only a finite number of elements in the truth set of Px The method of exhaustion will make you exhausted quickly you have to plug in every possible value of a E D or from the truth set of and then check Px gt This is sometimes called a brute force method and quickly becomes infeasible Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 853 Proving Universal Statements A Tool for a Better Method Clearly we would like a method of proving universal statements which works regardless of the size of the domain over which the statement is quantified The underlying idea of the method of generalizing from the generic particular To show that every element of a domain satisfies a certain prop erty suppose a is a particular but arbitrarily chosen element of the domain and show that 3 satisfies the property We will use this tool in the Method of Direct Proof Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 953 The Method of Direct Proof Method of Direct Proof 1 Express the statement to be proved in the form Vx E D if Px then 2 Start the prootc by supposing a is a particular but arbitrarily chosen element of D for which the hypothesis Px is true Abbreviatedz suppose a E D and 3 Show that the conclusion Qx is true by using definitions previously established results and the rules for logical infer ence Note The point of selecting a arbitrarily is that everything you deduce about a generic element in D will be true for every other element in D Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 1053 Let39s Try It Theorem If the sum of two integers is even so is their difference Restatement Vm n E Z if m n is even then m n is even 1 m n 2k for some k E Z solve for 2 m 2k n substitute into m 3 m n2k n n2k 2n2k n We39re done Sort of Let39s clean it up and make it more readable Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 1153 Our First Theorem with Proof Theorem If the sum of any two integers is even then so is their difference Proof Suppose m and n are integers so that m n is even By definition of even m n 2k for some integer k Subtracting n from both side gives m 2k n then m n 2k n n by substitution 2 2k 2n by combining terms basic algebra 2k n by factoring out a 2 basic algebra But k n is an integer because it is the difference between integers Hence m n equals 2 times an integer and so by the definition of even m n is even D Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 1253 How to Write a Proof 1 Write the theorem to be proved 2 Clearly mark the beginning of the proof with the word proof 3 Make your proof selfcontained In the body text of the proof identify each variable used in the proof The reader should not have to guess or assume anything 4 Write proofs in complete English sentences This does not mean that you should avoid using symbols and shorthand abbreviations just that you should incorporate then into sentences Your proofs It39s better you are too detailed but don39t be ridiculous Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 1353 Common Mistakes 1 lof2 Arguing from Examples Examples help understanding but special cases do not prove general statements Think of the statement All odd number integers greater than 1 are prime and the examples 3 5 7 Using the same letter to mean two things For instance if m and n are two even integers don39t say m 2r and n 2r Disaster You39re saying m nlll Use eg m 2r and n 2s Jumping to 3 Conclusion To state that something is true without giving adequate reason cuz say soquot is not sufficient logical argument Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 1453 Common Mistakes 20f2 4 Begging the Question To assume what it to be proved Usually in a logically equivalent form that looks different Misuse of the Word quotifquot Using the word if instead of since or because Consider quotSuppose p is a prime lfp is prime then p cannot be written as a product of two smaller numbers and quotSuppose p is a prime Since p is prime p cannot be written as a product of two smaller numbers In the first formulation the primeness of p seems to be in doubt in the second sentence Such imprecise use of language can cascade through the proof and generate problems later Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 1553 Comic Relief The Odd Prime Number Theory An engineer a mathematician and a physicist are testing the theory that all odd numbers are prime Physicist 1 is prime 3 is prime 5 is prime 7 is prime 9 must be experimental error 11 is prime 13 is prime That39s enough data points the theory is true Mathematician By convention 1 is not prime but 3 is a prime 5 is a prime 7 is a prime 9 is not a prime counterexample claim is false Engineer 1 is prime 3 is prime 5 is prime 7 is prime 9 is prime 11 is prime 13 is prime 15 is prime 17 is prime 19 is prime Hmmm theory appears to be true Second Engineer who slept through some early math classes What do you mean 1 is not prime Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 1653 Disproof By Counterexample Disproving a statement of the form Vx E D if Px then Qx amounts to proving that the negation of the statement is true 3x 6 D such that Px and N Qx Disproof by Counterexample To disprove a statement of the form Vx E D if Px then find a value of x in D for which Px is true and Qx is false Such an a is called a counterexample Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 1753 Examples Disproofs Bogus Theorem 1 All odd integers greater than 1 are prime Disproof Since 9 2 4 1 it is odd Further 9 3 3 which shows that 9 is a composite number hence not a prime Bogus Theorem 2 Va 6 R b E R if a2 b2 then a b Disproof Let a 1 and b 1a2 b2 1 but a 7E b Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 1853 Famous Proofs and Disproofs Fermat s Last Theorem If n is an integer greater than 2 then the equation xquot yquot 2quot has no solutions where x y and z are positive integers Pierre de Fermat lived 1601 1665 Euler s Conjecture a4 b4 c4 d4 has no integer solutions Leonhard Euler lived 1707 1783 Fermat s Last Theorem was finally proved by Andrew Wiles in September 1994 Euler s Conjecture was disproved by Noam Elkie Harvard Uni versity in 1986 One counterexample is 958004 2175194 414 5604 11224814 found by Roger Frye of Thinking Machines Corporation Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 1953 Homework 4 Due 1062006 12noon GMCS587 version i 3 3rd Edition 2nd Edition Problems 31 27 31 37 49 31 12 24 35 Please use the 3rd Edition numbering when handing in your solutions Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 2053 Divisibility and Number Theory Introduction Epp 32 skip Divisibility of the central concept of number theory the study of properties of integers Important applications of number theory include keeping your credit card number safe when you hit buy nowquot in your web browser We look at some more statements about integers and prove a few of them Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 2153 Divisibility of an Integer Definition Divisibility If n and d are integers and d 7E 0 then n is divisible by d if and only if n d k for some integer k Alternatively we say that n is a multiple of d or d is a factor of n or d is a divisor of n or d divides n The notation din is read d divides Symbolically if n and d are integers and d 7E 0 din ltgt EkEZ ndk Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 2253 Divisibility Examples Example 1 Suppose a and b are positive integers and all ls a g b Solution all means that b k a for some positive integer k since both a and b are positive Therefore k 2 1 This shows that b k a Z a by multiplying both sides of the inequality by the positive integer a Hence we can conclude that a g 1 Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 2353 Divisibility Examples Example 2 a If a and b are integers is 3a 3b divisible by 3 b If k and m are integers is 10km divisible by 5 Solution 3 By basic algebra the distributive law we can write 3a 3b 3a b and since a b is an integer being a sum of integers we have shown that 3l3a 3b b By basic algebra the associative law we can write 10km 5 2km where 2km is an integer being a prod uct of integers We have shown 5l10km Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 2453 Divisibility Primeness and Transitivity We can use the concept of divisibility to define primeness Definition Prime Integer Alternative A positive integer n gt 1 is prime if and only if its only divisors are 1 and n Divisibility is transitive If one number a divides a second number I alb and the second number divides a third number 0 bio then the first number divides the third ale This is an important fact lets prove it Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 2553 Proof Divisibility is a Transitive Property Theorem For all integers a b and c if aib and b c then aic Proof Suppose a b and c are particular but arbitrarily chosen integers such that aib and bio By the definition of divisibility we know that aib ltgt b a r for some integer r and bio ltgt c I 75 for some integer 75 Combining these two we have c bt art for some integers r and 75 Hence we can write 0 a r 75 where r 75 is an integer which shows that aic D Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 2653 Does ab and ba imply a b Question ls it true that for all integers a and b if all and bla then a b Solution Suppose a and b are integers such that all and b a then wemusthave ba7 TEZ abs 86 By substitution barbsr which is true if and only if 5 7quot 1 ie both 7 and s are divisors of 1 The only divisors of 1 are 1 and 1 r s 1 gives us infinitely many counterexamples a b thus we conclude all and bla 75gt ab Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 2753 The Unique Factorization Theorem Theorem The Unique Factorization Theorem Given any integer n gt 1 there exists a positive integer k distinct prime numbers p1 p2 pk and positive integers 61 62 6k such that 7119 2932 ka and any other expression of n as a product of prime numbers is identical to this except possibly for the order in which the factors are written The proof is beyond the scope of this class but the theorem is impor tant enough that you should know it If you write the factors such that p1 lt 192 lt lt pk then the form is called the standard factored form Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 2853 Using the Unique Factorization Theorem Question Suppose m is an integer such that 8765432m1716151413121110 Does 17lm Solution 17 is a prime number Since it is a factor on the right side of the equation it must also be a factor on the left side ofthe equation by the Unique Factorization Theorem UFT But 17 cannot factor any of the numbers 8 7 6 5 4 3 2 since it is too large Hence it must factor m so 17lm Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 2953 The QuotientRemainder Theorem Theorem Quotient Remainder Given any integer n and a positive integer d there exist unique integers q the quotient and r the remainder such that ndq l r and 0 rltd Example Say you have 10 cookies n 10 and you want to dis tribute as many of them as possible among 3 children d 3 so that each child receives the same number of cookies of coursel After you have distributed 3 sets q 3 of 3 cookies you have one r 1 remaining By the quotientremainder theorem you got it right there is only one unique way of solving the problem We are going to need more tools before we can prove this theorem we39ll get to it in a couple of weeks for now we take it as given Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 3053 Notation div and mod Definition Given a nonnegative integer n and a positive integer d we define n div d q the integer quotient obtained when n is divided by d n mod d r the integer remainder obtained when n is divided by d The quotientremainder theorem tells us that nmoddE01d 1 and nmodd0 ltgt dln Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 3153 Using div and mod Example February 17 2005 was a Thursday What day was it one year earlier Solution 366 days passed since February 17 2004 and each week has seven days Since 366 div 7 52 and 366 mod 7 2 it follows that exactly 52 weeks and 2 days passed between the two dates Thus 2172004 was a Tuesday Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 3253 The Parity of an Integer The parity property is the fact that an integer is either even or odd but not both We use the quotientremainder theorem and and our new operation mod to classify the integers For an integer n If n mod 2 0 then n is even If n mod 2 1 then H is odd Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 3353 Proof by Dividing into Cases Theorem Any two consecutive integers have opposite parity Proof Let m and m 1 be two consecutive integers By the parity property m is even or m is odd case 1 m is even In this case m 2k for some k E Z and so m 1 2k 1 which is odd by the definition of odd In this case m is even and m1 is odd case 2 m is odd In this case m 2k 1 for some k E Z and so m 1 2k 2 2k 1 which is even by the definition of even In this case m is odd and m 1 is even It follows that regardless of which case occurs for the particular choice of m and m 1 one of them is even and the other one is odd Hence we have proved the theorem D Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 3453 Homework 4 Due 1062006 12noon GMCS587 version 3 3 3rd Edition 2nd Edition Problems 31 27 31 37 49 31 12 24 35 33 17 25 25 36a 36b 33 15 24 25 35 Please use the 3rd Edition numbering when handing in your solutions Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 3553 Checking the Road Map Where are we Are we lost In chapters 1 and 2 we talked about logic in its purest form learning about logic operator and connectives truth tables compound state ments conditional statements quantified statements predicates Things were pretty good some of y39all fell asleep since things were quite cozy and familiar Now in chapter 3 we are talking about different methods of proof where we must use our logic toolbox from chapters 1 and 2 to prove that certain mathematical statements are true We are working in the context of number theory the study of the properties of integers We are introducing both proofmethodologies and number theory at the same time maybe a source of confusion Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 3653 Review Proof Techniques The Method of Direct Proof Method of Direct Proof 1 Express the statement to be proved in the form Vx E D if Px then Qx 2 Start the proorc by supposing a is a particular but arbitrarily chosen element of D for which the hypothesis Px is true Abbreviatedz suppose a E D and 3 Show that the conclusion Qx is true by using definitions previously established results and the rules for logical infer ence Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 3753 Review Proof Techniques Disproof by Counterexample Disproof by Counterexample To disprove a statement of the form Vx E D if Px then find a value of x in D for which Px is true and Qx is false Such an a is called a counterexample Example Dispromc of a4 b4 c4 d4 does not have any positive integer solutions quot Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 3853 Review Proof Techniques Division into Cases Proof by Division into Cases Conjectures can often be simplified by dividing a proof into cases When a conjecture is true in all cases it is a theorem If a con jecture is a theorem a proof by cases may simplify the argument since each case is a simpler form of the conjecture Also if a conjecture is not a theorem an attempted proof by cases may simplify the conjecture and make it easier to understand why the proof is not succeeding Example The successful proof of Any two integers consecutive have opposite parityquot Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 3953 Review Number Theory Divisibility Definition Divisibility If n and d are integers and d 7E 0 then n is divisible by d if and only if n d k for some integer k Alternatively we say that n is a multiple of d or d is a factor of n or d is a divisor of n or d divides n The notation dln is read d divides Symbolically if n and d are integers and d 7E 0 din ltgt EkEZ ndk Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 4053 Review Number Theory Primeness Two Definitions Definition Prime Composite Integers An integer n is prime if and only if n gt 1 and for all positive integers r and 5 if n r 5 then r 1 or s 1 An integer n is composite if and only if n r 3 for some positive integers r andswith r7 1 and s7 1 Symbolically if n E N then nisprime ltgt VrsENifnrsthenr1ors1 n is composite ltgt 3r 3 E N such that n r 3 andr7 1ands7 1 Definition Prime Alternative A positive integer n gt 1 is prime if and only if its only divisors are 1 and n Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 4153 Review Number Theory Integer Division and Modulus Definition Integer Division and Modulus Given a nonnegative integer n and a positive integer d we define n div d q the integer quotient obtained when n is divided by d nmodd ll the integer remainder obtained when n is divided by d Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 4253 Review Number Theory Unique Factorization Theorem Theorem The Unique Factorization Theorem Given any integer n gt 1 there exists a positive integer k distinct prime numbers p1 p2 pk and positive integers 61 62 6 such that 7119 2932 ka and any other expression of n as a product of prime numbers is identical to this except possibly for the order in which the factors are written The proof is beyond the scope of this class but the theorem is impor tant enough that you should know it Know the statement and how to use it If you write the factors such that p1 lt 192 lt lt pk then the form is called the standard factored form Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 4353 Review Number Theory QuotientRemainder Theorem Theorem Quotient Remainder Given any integer n and a positive integer d there exist unique integers q the quotient and r the remainder such that ndq l r and 0 rltd Those are our theoretical toys so far Now lets move forward Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 4453 Exercise Representation of Integers Modulo 4 Conjecture All integers can be written in one of the forms n4q or n4q1 or n4q2 or n4q3 Solution Let n be an integer We apply the quotientremainder theorem with d 4 this implies there exists a unique pair of quotientremainder pair q and r such that n 4qr where 7 E 0123 This shows that the conjecture is true This seemingly simple result will be useful in a few slides Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 4553 The Mathematical Let The statement Let n be an integerquot means Suppose n is a particular but arbitrarily chosen integer quot That is we randomly select an integer from Z The statement may look casual but it means something very specific in the language of mathematics You will see similar statements all over the mathliterature o Letp be a prime such thatp 2quot 1 for some n E Z 0 Let r and s be two real numbers such that Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 4653 Exercise The form of the Square of an Odd Integer 1 of 2 Conjecture The square of any odd integer has the form 8m 1 for some integer m Solution Let n be an odd integer By the quotientremainder theo rem n can be written in one of the forms see previous exercise n4q or n4q1 or n4q2 or n4q3 Now since n is odd this reduces the possibilities to the forms n4q1 or n4q3 case1 We have that n 4g 1 for some integer q therefore 2 2 2 2 n 4q1 16q 8q1 82q q1 W integer Identifying m 2g2 q shows that n2 8m 1 for some integer m end case1 Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 4753 Exercise The form of the Square of an Odd Integer 2 of 2 case2 We have that n 4g 3 for some integer q therefore n24q3216q224q982q23q11 W integer Identifying m 2g2 3g 1 shows that n2 8m 1 for some integer m end case2 case1 and case2 shows that given any odd integer n whether of the form 4g 1 or 4g 3 its square can be written on the form n2 8m 1 for some integer m D Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 4853 Exercise Making Change The following algorithms gives makes change it determines how many quarters 25 q dimes 10 d nickels 5c and pennies 1c p equals 0 the total amount of change Givenc 099 069 083 C C div 25 3 2 3 02 C mod 25 24 19 8 d 62 div 10 2 1 0 03 02 mod 10 4 9 8 n 03 div 5 0 1 1 p 03 mod 5 4 4 3 Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 4953 Exercise 71 mod 3 E 0 1 2 Conjecture Any integer n can be written in one of the three forms 7139 or n3q1 or n3q2 Solution Let n be an integer By the quotientremainder theorem with d 3 there exist unique integers q and r such that n3qr where0 rltd This shows that n can be written in one of the forms above D We are now going to use this result to show something a little more complicated Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 5053 Exercise The Product of Three Consecutive Integers 1 of 2 Conjecture The product of three consecutive integers is divisible by 3 Solution Let n n 1 and n 2 be three consecutive integers By the quotientremainder theorem see previous exercise 71 can be written in one of the forms n3q or n3q l 1 or n3q2 case1 n 3g for some integer q in this case the product nn 1n 2 3q3q 13q 2 3 q3q 13q 2 integer which shows that 3lnn 1n 2 Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 5153 Exercise The Product of Three Consecutive Integers 2 of 2 case2 n 3g 1 for some integer q in this case the product nn1n2 3q13q23q3 33q 13q 2q 1 J integer which shows that 3mm 1n 2 case3 n 3g 2 for some integer q in this case the product nn1n2 3q23q33q4 33q 2q 13q 4 J integer which shows that 3mm 1n 2 In all three cases we have 3mm 1n 2 thus we have shown that the product of any three consecutive integers is divisible by 3 D Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 5253 Homework 4 Due 1062006 12noon GMCS587 Final Version 3rd Edition 2nd Edition Problems 31 27 31 37 49 31 12 24 35 33 17 25 25 36a 36b 33 15 24 25 35 34 7 8 9 10 24 29 43 34 7 18 30 Please use the 3rd Edition numbering when handing in your solutions Writing your name on and stapling your homework is highly rec ommended Elementary Number Theory and Methods of Proof Direct Proof and Counterexample 7 p 5353

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.