Discrete Mathematics and Probability Theory Fall 2009 Satish Rao, David Tse Note 2


 Loren Stewart
 5 years ago
 Views:
Transcription
1 CS 70 Discrete Mathematics and Probability Theory Fall 2009 Satish Rao, David Tse Note 2 Proofs Intuitively, the concept of proof should already be familiar We all like to assert things, and few of us like to say things that turn out to be false A proof provides a means for guaranteeing such claims Proofs in mathematics and computer science require a precisely stated proposition to be proved But what exactly is a proof? How do you show that a proposition is true? Recall that there are certain propositions called axioms or postulates, that we accept without proof (we have to start somewhere) A formal proof is a sequence of statements, ending with the proposition being proved, with the property that each statement is either an axiom or its truth follows easily from the fact that the previous statements are true For example, in high school geometry you may have written twocolumn proofs where one column lists the statements and the other column lists the justifications for each statement The justifications invoke certain very simple rules of inference which we trust (such as if P is true and Q is true, then P Q is true) Every proof has these elements, though it does not have to be written in a tabular format And most importantly, the fact that each step follows from the previous step is so straightforward, it can be checked by a computer program A formal proof for all but the simplest propositions is too cumbersome to be useful In practice, mathematicians routinely skip steps to give proofs of reasonable length How do they decide which steps to include in the proof? The answer is sufficiently many steps to convince themselves and the reader that the details can easily be filled in if desired This of course depends upon the knowledge and skill of the audience So in practice proofs are socially negotiated During the first few weeks of the semester, the proofs we will write will be quite formal Once you get more comfortable with the notion of a proof, we will relax a bit We will start emphasizing the main ideas in our proofs and sketching some of the routine steps This will help increase clarity and understanding and reduce clutter A proof, for the purposes of this class, is essentially a convincing argument Convincing to whom? First, to you, the author, second, to your classmates, third, to your professor and your TA In this lecture you will see some examples of proofs The proofs chosen are particularly interesting and elegant, and some are of great historical importance But the purpose of this lecture is not to teach you about these particular proofs (and certainly not for you to attempt to memorize any of them!) Instead, you should see these as good illustrations of various basic proof techniques You will notice that sometimes when it is hard to even get started proving a certain proposition using one proof technique, it is easy using a different technique This will come in handy later in the course when you work on homework problems or try to prove a statement on your own If you find yourself completely stuck, rather than getting discouraged you might find that using a different proof technique opens doors that were previously closed We now begin with a few definitions pertaining to proofs A theorem, informally speaking, is a true proposition that is guaranteed by a proof If you believe that a statement is true but can t prove it, call it a conjecture, essentially an educated guess A concept useful for writing up complicated proofs is that of a lemma, which is a little theorem that you use in the proof of a bigger theorem A lemma is to proofs what a subroutine is to programming CS 70, Fall 2009, Note 2 1
2 An axiom is a statement we accept as true without proof There are many different types of proofs, as we shall see The basic structure of these different types of proofs is best expressed in terms of propositional logic Direct Proof Let us start with a very simple example Theorem: If x is an odd integer, then x + 1 is even Following the notation introduced in the previous Note, this statement is equivalent to ( x Z)(x is odd = x + 1 is even) (Here Z denotes the set of all integers) For each x, the proposition that we are trying to prove is of the form P(x) = Q(x) A direct proof of this starts by assuming P(x) for a generic value of x and eventually concludes Q(x) through a chain of implications: Direct Proof of P = Q Assume P Therefore Q Let us proceed with a direct proof of the simple example given above: Proof: Assume x is odd Then by definition, x = 2k + 1 for some k Z Adding one to both sides, we get x + 1 = 2k + 2 = 2(k + 1) Therefore, by definition, x + 1 is an even number Before turning to our next example, we recall that integer d divides n (denoted d n) iff there exists some integer q such that n = dq For the following, let n be a postive integer less than 1000 Theorem: If the sum of the digits of n is divisible by 9, then n is divisible by 9 Note: The theorem is true for arbitary n We re just doing the three digit case here to keep the notation from getting distracting As in the previous example, this statement is equivalent to ( n Z + )(sum of n s digits divisible by 9 = n divisible by 9) (Here Z + denotes the set of positive integers, {1,2,}) So once again we start by assuming, for a generic value of n, that the sum of n s digits is divisible by 9 Then we perform a sequence of steps to conclude that n itself is divisible by 9 Here is the proof Proof: Suppose we have n such that the sum of the digits of n is divisible by 9 Let a be the hundred s digit of n, b the ten s digit, and c the one s digit Then n = 100a + 10b + c Now suppose that the sum of the digits of n is divisible by 9 Then, a + b + c = 9k,k Z CS 70, Fall 2009, Note 2 2
3 Adding 99a + 9b to both sides of the equation, we get So n is divisible by 9 100a + 10b + c = n = 9k + 99a + 9b = 9(k + 11a + b) In this case the converse of the theorem is also true: If n is divisible by 9, the sum of its digits is divisible by 9, too In other words, the sum of the digits of n is divisible by 9 if and only if 1 n is divisible by 9 In general, to prove P Q, you have to do two proofs: You must show that P = Q and then, separately, you must also show that Q = P Theorem: n is divisible by 9 if and only if the sum of the digits of n is divisible by 9 Proof: We already proved above that if the sum of the digits of n is divisible by 9 then n is divisible by 9 So we only need to prove the converse We use the same notation for the digits of n as we used in the previous proof: n is divisible by 9 = n = 9l,l Z = 100a + 10b + c = 9l = 99a + 9b + (a + b + c) = 9l = a + b + c = 9l 99a 9b = a + b + c = 9(l 11a b) = a + b + c = 9k, k = l 11a b Z = a + b + c is divisible by 9 Note that, in this simple example, the proof of Q = P is essentially the same as the proof of Q = P run backwards In such a case, you may be able to get away with proving both of the implications at the same time (using the symbol at every step of the proof) However, be very careful if you do this: for the proof to be legitimate, the steps have to make just as much sense backwards as forwards! (Go back and read the last proof again, starting with the last line and ending with the first, and convince yourself that it also works backwards) To avoid potential pitfalls, it is recommended that you always prove a statement of the form P Q using two separate proofs This will in any case be necessary in more interesting examples, where the proofs of P = Q and of Q = P might look very different Proof by Contraposition In the last lecture, we learned that a statement of the form P = Q is logically equivalent to its contrapositive: Q = P This means that proving an implication is equivalent to proving the contrapositive A proof by contraposition of P = Q is just a direct proof of its contrapositive Q = P: Proof by Contraposition of P = Q Assume Q Therefore P So Q = P P = Q 1 The phrase if and only if is often abbreviated to iff CS 70, Fall 2009, Note 2 3
4 Sometimes proving the contrapositive of a statement is easier than proving the statement directly Here is an illustrative example Let n be an integer and let d divide n Theorem: If n is odd then d is odd Proving this directly would be difficult We would assume n is odd but what then? Proving the contrapositive of the statement, however, is very straightforward The contrapositive is: If d is even then n is even Proof: Suppose d is even, then (by definition) d = 2k for some k Z Because d n, n = dl, for some l Z Combining these two statements, we have n = dl = (2k)l = 2(kl) So n is even So if d is even then n is even Therefore if n is odd then d is odd Proof by contraposition is a very common technique When proving implications (P = Q) the contrapositive gives us a second option for how to approach the problem As a warning, do not confuse the contrapositive with the converse! To give some intuition using English, consider the statement If it is sunny, then it is daytime The contrapositive is If it is nighttime, then it is not sunny, and the converse is If it is daytime, then it is sunny We know the original statement is true, and its contrapositive is also true However the converse is simply false (for example, a summer afternoon in San Francisco!) Proof by Contradiction Proof by contradiction is also called reductio ad absurdum (reduction to an absurdity) The idea is to assume the opposite of what one is trying to prove and then show that this leads to something that is clearly nonsensical: a contradiction Proof by Contradiction of P Assume P R R Contradiction Therefore P Before proceeding to an example, let us try to understand the logic behind a proof by contradiction We assume P, and then prove both R and R But for any proposition R, R R False So we have shown that P = False The only way this implication can be true is if P is false ie, P is true Our first example of a proof by contradiction dates back more than 2000 years to Euclid (Note that it is not of the form P = Q so contraposition is not an option) Theorem: There are infinitely many prime numbers Proving this directly would be difficult How do we construct infinitely many prime numbers? But, as we will see, bad things happen when we assume that this statement is false: that there are only finitely many primes Before we prove the theorem, we will state a simple lemma that we ll use without proof We will CS 70, Fall 2009, Note 2 4
5 prove it next week when we learn about induction Lemma: Every natural number greater than one is either prime or has a prime divisor (greater than one) Now for the proof of the theorem Proof: Suppose (in order to get a contradiction) that there are only finitely many primes Then, we can enumerate them: p 1, p 2, p 3,, p k (Here k is the total number of primes) Consider the number q = p 1 p 2 p 3 p k + 1, the product of all the primes plus one Note that q cannot be prime because it is strictly larger than all the primes Thus, by the lemma, it has a prime divisor, p (This will be our statement R, or, more precisely R is the assertion that p > 1) Because p 1, p 2, p 3,, p k are all the primes, p must be equal to one of them, so p is a divisor of their product So we have that p divides p 1 p 2 p 3 p k, and p divides q, but that means p divides their difference, which is 1 Therefore, p 1 (this is R) Contradiction Therefore there are infinitely many primes Note that in the proof, q need not be prime, tempting as it might be to say so It s certainly not the case that a product of primes plus one must always be prime (think of ) When writing a proof, it is important to carefully think through each step, ensuring that it s logically justified The most important part of learning mathematics is learning a habit of thinking clearly and precisely Let s look at another classic proof by contradiction A rational number is a number that can be expressed as the ratio of two integers For example, 2 3, 3 5, and 9 16 are all rational numbers In fact, any number with a finite or recurring decimal representation is a rational [Exercise: Can you prove this?] Numbers that cannot be expressed as fractions are called irrational Theorem: 2 is irrational Proof: Assume (for the sake of contradiction) that 2 is rational By the definition of rational numbers, there are integers a and b with no common factor other than 1, such that 2 = a/b (This will be our assertion R) For any numbers x and y, we know that x = y = x 2 = y 2 Hence 2 = a 2 /b 2 Multiplying both sides by b 2, we have a 2 = 2b 2 b is an integer, hence b 2 is an integer, hence a 2 is even (by the definition of evenness) Hence, a is even (by the lemma below) Therefore, by the definition of evenness, there is an integer c such that a = 2c Hence 2b 2 = 4c 2, hence b 2 = 2c 2 Since c is an integer, c 2 is an integer, hence b 2 is even Thus, b is even (by the lemma below) Thus a and b have a common factor 2, contradicting the assertion that a and b have no common factor other than 1 This shows that the original assumption that 2 is rational is false, and hence that 2 must be irrational Lemma: If a 2 is even, then a is even Can you prove this lemma? First try a direct proof? How would you proceed? Now try a proof by contraposition CS 70, Fall 2009, Note 2 5
6 Proof by Cases Sometimes we don t know which of a set of possible cases is true, but we know that at least one of the cases is true If we can prove our result in each of the cases, then we have a proof The English phrase damned if you do and damned if you don t sums up this proof method Here s a nice example: Theorem: For some irrational numbers x and y, x y is rational Proof: This is our first example in this Note of a theorem that is existentially quantified ( for some ) In other words, the statement may be written as ( x)( y)(x is irrational y is irrational x y is rational) Thus to prove the theorem we only need to prove the existence of at least one example of values x,y that satisfy the claim (For this reason, proofs of existentially quantified statements are often but not always a little easier than proofs of universally quantified ones) Consider the case x = 2 and y = 2 Clearly, either (a) 2 2 is rational; or (b) 2 2 is irrational In case (a), we have shown irrational numbers x and y such that x y is rational, so we are done In case (b), consider the new values x = 2 2 and y = 2 We have x y = ( 2) 2 2 = by the axiom (x y ) z = x yz = 2 2 = 2 Hence we have again shown irrational numbers x and y such that x y is rational Since one of cases (a) and (b) must be true, and since in both cases we have exhibited irrational numbers x and y such that x y is rational, we can conclude that such numbers must always exist Notice that even after the proof, we still don t know which of the two cases is true, so we can t actually exhibit any irrational numbers satisfying the theorem This is an example of a nonconstructive proof: one in which an existential theorem is proved without constructing an explicit example Nonproof Failure to logically structure a proof or note the justification for each step can lead easily to nonproofs Consider the following examples Theorem: (not!) 2 = 2 Proof: Assume 2 = 2 Squaring both sides, we get ( 2) 2 = 2 2, or 4 = 4 which is true Therefore, 2 = 2 The theorem is obviously false, so what did we do wrong? Our arithmetic is correct, and it seems like each step follows from the previous step The problem with this proof does not lie in the arithmetic, but rather the logic We assumed the very theorem we were trying to prove was true! As you can see, logical soundness and structure are extremely important when proving propositions CS 70, Fall 2009, Note 2 6
7 The next proof is incorrect for a different reason Theorem: (not!) 1 = 1 Proof: 1 = 1 = ( 1)( 1) = 1 1 = 1 2 = 1 This proof appears to be logically sound, so the error lies elsewhere Since we have concluded a falsehood, at least one of these steps must be false Indeed, it is simply untrue that xy = x y If you think carefully through each step of your proofs, you can avoid such missteps Other classic errors: Dividing both sides of an equation by a variable For example: ax = bx hence a = b The axiom to which this step implicitly appeals is false, because if x = 0, the claim a = b is not necessarily true So in this case, either x = 0 or a = b (consider writing the above as x(a b) = 0) Some extra work may be needed to prove x 0 Dividing both sides of an inequality by a variable This is even worse! For example: ax < bx hence a < b Here the claim a < b is false if x < 0, and unproven if x = 0 More generally, forgetting about 0 Forgetting to account for the possibility of variables being zero causes lots of headaches (including the above) Style and substance in proofs We conclude with some general words of advice First, get in the habit of thinking carefully before you write down the next sentence of your proof If you cannot explain clearly why the step is justified, you are making a leap and you need to go back and think some more In theory, each step in a proof must be justified by appealing to a definition or general axiom In practice the depth to which one must do this is a matter of taste For example, we could break down the step, Since a is an integer, (2a 2 + 2a) is an integer, into several more steps [Exercise: what are they?] A justification can be stated without proof only if you are absolutely confident that (1) it is correct and (2) the reader will automatically agree that it is correct Notice that in the proof that 2 is irrational, we used the result, For any integer n, if n 2 is even then n is even, twice This suggests that it may be a useful fact in many proofs A subsidiary result that is useful in a more complex proof is called a It is often a good idea to break down a long proof into several lemmas This is similar to the way in which large programming tasks should be divided up into smaller subroutines Furthermore, make each lemma (like each subroutine) as general as possible so it can be reused elsewhere The dividing line between lemmas and theorems is not clearcut Usually, when writing a paper, the theorems are those propositions that you want to export from the paper to the rest of the world, whereas the lemmas are propositions used locally in the proofs of your theorems There are, however, some lemmas (for example, the Pumping Lemma and the Lifting Lemma) that are perhaps more famous and important than the theorems they were used to prove Finally, you should remember that the point of this lecture was not the specific statements we proved, but the different proof strategies, and their logical structure Make sure you understand them clearly; you will be using them when you write your own proofs in homework and exams CS 70, Fall 2009, Note 2 7
Handout #1: Mathematical Reasoning
Math 101 Rumbos Spring 2010 1 Handout #1: Mathematical Reasoning 1 Propositional Logic A proposition is a mathematical statement that it is either true or false; that is, a statement whose certainty or
More informationBasic Proof Techniques
Basic Proof Techniques David Ferry dsf43@truman.edu September 13, 010 1 Four Fundamental Proof Techniques When one wishes to prove the statement P Q there are four fundamental approaches. This document
More informationThe last three chapters introduced three major proof techniques: direct,
CHAPTER 7 Proving NonConditional Statements The last three chapters introduced three major proof techniques: direct, contrapositive and contradiction. These three techniques are used to prove statements
More informationElementary Number Theory and Methods of Proof. CSE 215, Foundations of Computer Science Stony Brook University http://www.cs.stonybrook.
Elementary Number Theory and Methods of Proof CSE 215, Foundations of Computer Science Stony Brook University http://www.cs.stonybrook.edu/~cse215 1 Number theory Properties: 2 Properties of integers (whole
More information3. Mathematical Induction
3. MATHEMATICAL INDUCTION 83 3. Mathematical Induction 3.1. First Principle of Mathematical Induction. Let P (n) be a predicate with domain of discourse (over) the natural numbers N = {0, 1,,...}. If (1)
More informationCS 103X: Discrete Structures Homework Assignment 3 Solutions
CS 103X: Discrete Structures Homework Assignment 3 s Exercise 1 (20 points). On wellordering and induction: (a) Prove the induction principle from the wellordering principle. (b) Prove the wellordering
More information8 Divisibility and prime numbers
8 Divisibility and prime numbers 8.1 Divisibility In this short section we extend the concept of a multiple from the natural numbers to the integers. We also summarize several other terms that express
More informationCHAPTER 3. Methods of Proofs. 1. Logical Arguments and Formal Proofs
CHAPTER 3 Methods of Proofs 1. Logical Arguments and Formal Proofs 1.1. Basic Terminology. An axiom is a statement that is given to be true. A rule of inference is a logical rule that is used to deduce
More informationWRITING PROOFS. Christopher Heil Georgia Institute of Technology
WRITING PROOFS Christopher Heil Georgia Institute of Technology A theorem is just a statement of fact A proof of the theorem is a logical explanation of why the theorem is true Many theorems have this
More informationMathematical Induction
Mathematical Induction (Handout March 8, 01) The Principle of Mathematical Induction provides a means to prove infinitely many statements all at once The principle is logical rather than strictly mathematical,
More informationMathematical Induction. Mary Barnes Sue Gordon
Mathematics Learning Centre Mathematical Induction Mary Barnes Sue Gordon c 1987 University of Sydney Contents 1 Mathematical Induction 1 1.1 Why do we need proof by induction?.... 1 1. What is proof by
More informationMATH10040 Chapter 2: Prime and relatively prime numbers
MATH10040 Chapter 2: Prime and relatively prime numbers Recall the basic definition: 1. Prime numbers Definition 1.1. Recall that a positive integer is said to be prime if it has precisely two positive
More informationAn Innocent Investigation
An Innocent Investigation D. Joyce, Clark University January 2006 The beginning. Have you ever wondered why every number is either even or odd? I don t mean to ask if you ever wondered whether every number
More informationWHAT ARE MATHEMATICAL PROOFS AND WHY THEY ARE IMPORTANT?
WHAT ARE MATHEMATICAL PROOFS AND WHY THEY ARE IMPORTANT? introduction Many students seem to have trouble with the notion of a mathematical proof. People that come to a course like Math 216, who certainly
More informationThe Prime Numbers. Definition. A prime number is a positive integer with exactly two positive divisors.
The Prime Numbers Before starting our study of primes, we record the following important lemma. Recall that integers a, b are said to be relatively prime if gcd(a, b) = 1. Lemma (Euclid s Lemma). If gcd(a,
More informationContinued Fractions and the Euclidean Algorithm
Continued Fractions and the Euclidean Algorithm Lecture notes prepared for MATH 326, Spring 997 Department of Mathematics and Statistics University at Albany William F Hammond Table of Contents Introduction
More informationMath 3000 Section 003 Intro to Abstract Math Homework 2
Math 3000 Section 003 Intro to Abstract Math Homework 2 Department of Mathematical and Statistical Sciences University of Colorado Denver, Spring 2012 Solutions (February 13, 2012) Please note that these
More informationCHAPTER 5. Number Theory. 1. Integers and Division. Discussion
CHAPTER 5 Number Theory 1. Integers and Division 1.1. Divisibility. Definition 1.1.1. Given two integers a and b we say a divides b if there is an integer c such that b = ac. If a divides b, we write a
More informationSECTION 102 Mathematical Induction
73 0 Sequences and Series 6. Approximate e 0. using the first five terms of the series. Compare this approximation with your calculator evaluation of e 0.. 6. Approximate e 0.5 using the first five terms
More information8 Primes and Modular Arithmetic
8 Primes and Modular Arithmetic 8.1 Primes and Factors Over two millennia ago already, people all over the world were considering the properties of numbers. One of the simplest concepts is prime numbers.
More informationIntroduction. Appendix D Mathematical Induction D1
Appendix D Mathematical Induction D D Mathematical Induction Use mathematical induction to prove a formula. Find a sum of powers of integers. Find a formula for a finite sum. Use finite differences to
More information26 Integers: Multiplication, Division, and Order
26 Integers: Multiplication, Division, and Order Integer multiplication and division are extensions of whole number multiplication and division. In multiplying and dividing integers, the one new issue
More informationAnswer Key for California State Standards: Algebra I
Algebra I: Symbolic reasoning and calculations with symbols are central in algebra. Through the study of algebra, a student develops an understanding of the symbolic language of mathematics and the sciences.
More informationChapter 3. Cartesian Products and Relations. 3.1 Cartesian Products
Chapter 3 Cartesian Products and Relations The material in this chapter is the first real encounter with abstraction. Relations are very general thing they are a special type of subset. After introducing
More informationCOMP 250 Fall 2012 lecture 2 binary representations Sept. 11, 2012
Binary numbers The reason humans represent numbers using decimal (the ten digits from 0,1,... 9) is that we have ten fingers. There is no other reason than that. There is nothing special otherwise about
More information3. Logical Reasoning in Mathematics
3. Logical Reasoning in Mathematics Many state standards emphasize the importance of reasoning. We agree disciplined mathematical reasoning is crucial to understanding and to properly using mathematics.
More informationThe Fundamental Theorem of Arithmetic
The Fundamental Theorem of Arithmetic 1 Introduction: Why this theorem? Why this proof? One of the purposes of this course 1 is to train you in the methods mathematicians use to prove mathematical statements,
More informationMath 4310 Handout  Quotient Vector Spaces
Math 4310 Handout  Quotient Vector Spaces Dan Collins The textbook defines a subspace of a vector space in Chapter 4, but it avoids ever discussing the notion of a quotient space. This is understandable
More information3 0 + 4 + 3 1 + 1 + 3 9 + 6 + 3 0 + 1 + 3 0 + 1 + 3 2 mod 10 = 4 + 3 + 1 + 27 + 6 + 1 + 1 + 6 mod 10 = 49 mod 10 = 9.
SOLUTIONS TO HOMEWORK 2  MATH 170, SUMMER SESSION I (2012) (1) (Exercise 11, Page 107) Which of the following is the correct UPC for Progresso minestrone soup? Show why the other numbers are not valid
More informationINCIDENCEBETWEENNESS GEOMETRY
INCIDENCEBETWEENNESS GEOMETRY MATH 410, CSUSM. SPRING 2008. PROFESSOR AITKEN This document covers the geometry that can be developed with just the axioms related to incidence and betweenness. The full
More informationChapter 11 Number Theory
Chapter 11 Number Theory Number theory is one of the oldest branches of mathematics. For many years people who studied number theory delighted in its pure nature because there were few practical applications
More informationMathematical Induction
Mathematical Induction In logic, we often want to prove that every member of an infinite set has some feature. E.g., we would like to show: N 1 : is a number 1 : has the feature Φ ( x)(n 1 x! 1 x) How
More information5544 = 2 2772 = 2 2 1386 = 2 2 2 693. Now we have to find a divisor of 693. We can try 3, and 693 = 3 231,and we keep dividing by 3 to get: 1
MATH 13150: Freshman Seminar Unit 8 1. Prime numbers 1.1. Primes. A number bigger than 1 is called prime if its only divisors are 1 and itself. For example, 3 is prime because the only numbers dividing
More informationHomework until Test #2
MATH31: Number Theory Homework until Test # Philipp BRAUN Section 3.1 page 43, 1. It has been conjectured that there are infinitely many primes of the form n. Exhibit five such primes. Solution. Five such
More informationUndergraduate Notes in Mathematics. Arkansas Tech University Department of Mathematics
Undergraduate Notes in Mathematics Arkansas Tech University Department of Mathematics An Introductory Single Variable Real Analysis: A Learning Approach through Problem Solving Marcel B. Finan c All Rights
More information5.1 Radical Notation and Rational Exponents
Section 5.1 Radical Notation and Rational Exponents 1 5.1 Radical Notation and Rational Exponents We now review how exponents can be used to describe not only powers (such as 5 2 and 2 3 ), but also roots
More informationInteger Operations. Overview. Grade 7 Mathematics, Quarter 1, Unit 1.1. Number of Instructional Days: 15 (1 day = 45 minutes) Essential Questions
Grade 7 Mathematics, Quarter 1, Unit 1.1 Integer Operations Overview Number of Instructional Days: 15 (1 day = 45 minutes) Content to Be Learned Describe situations in which opposites combine to make zero.
More informationQuotient Rings and Field Extensions
Chapter 5 Quotient Rings and Field Extensions In this chapter we describe a method for producing field extension of a given field. If F is a field, then a field extension is a field K that contains F.
More informationMath Workshop October 2010 Fractions and Repeating Decimals
Math Workshop October 2010 Fractions and Repeating Decimals This evening we will investigate the patterns that arise when converting fractions to decimals. As an example of what we will be looking at,
More informationNUMBER SYSTEMS. William Stallings
NUMBER SYSTEMS William Stallings The Decimal System... The Binary System...3 Converting between Binary and Decimal...3 Integers...4 Fractions...5 Hexadecimal Notation...6 This document available at WilliamStallings.com/StudentSupport.html
More informationLogic is a systematic way of thinking that allows us to deduce new information
CHAPTER 2 Logic Logic is a systematic way of thinking that allows us to deduce new information from old information and to parse the meanings of sentences. You use logic informally in everyday life and
More informationGREATEST COMMON DIVISOR
DEFINITION: GREATEST COMMON DIVISOR The greatest common divisor (gcd) of a and b, denoted by (a, b), is the largest common divisor of integers a and b. THEOREM: If a and b are nonzero integers, then their
More informationJust the Factors, Ma am
1 Introduction Just the Factors, Ma am The purpose of this note is to find and study a method for determining and counting all the positive integer divisors of a positive integer Let N be a given positive
More informationWelcome to Math 19500 Video Lessons. Stanley Ocken. Department of Mathematics The City College of New York Fall 2013
Welcome to Math 19500 Video Lessons Prof. Department of Mathematics The City College of New York Fall 2013 An important feature of the following Beamer slide presentations is that you, the reader, move
More information6 3 4 9 = 6 10 + 3 10 + 4 10 + 9 10
Lesson The Binary Number System. Why Binary? The number system that you are familiar with, that you use every day, is the decimal number system, also commonly referred to as the base system. When you
More informationa 11 x 1 + a 12 x 2 + + a 1n x n = b 1 a 21 x 1 + a 22 x 2 + + a 2n x n = b 2.
Chapter 1 LINEAR EQUATIONS 1.1 Introduction to linear equations A linear equation in n unknowns x 1, x,, x n is an equation of the form a 1 x 1 + a x + + a n x n = b, where a 1, a,..., a n, b are given
More informationSession 7 Fractions and Decimals
Key Terms in This Session Session 7 Fractions and Decimals Previously Introduced prime number rational numbers New in This Session period repeating decimal terminating decimal Introduction In this session,
More informationPYTHAGOREAN TRIPLES KEITH CONRAD
PYTHAGOREAN TRIPLES KEITH CONRAD 1. Introduction A Pythagorean triple is a triple of positive integers (a, b, c) where a + b = c. Examples include (3, 4, 5), (5, 1, 13), and (8, 15, 17). Below is an ancient
More information1 if 1 x 0 1 if 0 x 1
Chapter 3 Continuity In this chapter we begin by defining the fundamental notion of continuity for real valued functions of a single real variable. When trying to decide whether a given function is or
More informationSo let us begin our quest to find the holy grail of real analysis.
1 Section 5.2 The Complete Ordered Field: Purpose of Section We present an axiomatic description of the real numbers as a complete ordered field. The axioms which describe the arithmetic of the real numbers
More informationMath Review. for the Quantitative Reasoning Measure of the GRE revised General Test
Math Review for the Quantitative Reasoning Measure of the GRE revised General Test www.ets.org Overview This Math Review will familiarize you with the mathematical skills and concepts that are important
More informationCHAPTER 5 Roundoff errors
CHAPTER 5 Roundoff errors In the two previous chapters we have seen how numbers can be represented in the binary numeral system and how this is the basis for representing numbers in computers. Since any
More informationStudent Outcomes. Lesson Notes. Classwork. Discussion (10 minutes)
NYS COMMON CORE MATHEMATICS CURRICULUM Lesson 5 8 Student Outcomes Students know the definition of a number raised to a negative exponent. Students simplify and write equivalent expressions that contain
More informationLecture 13  Basic Number Theory.
Lecture 13  Basic Number Theory. Boaz Barak March 22, 2010 Divisibility and primes Unless mentioned otherwise throughout this lecture all numbers are nonnegative integers. We say that A divides B, denoted
More informationMathematics for Computer Science/Software Engineering. Notes for the course MSM1F3 Dr. R. A. Wilson
Mathematics for Computer Science/Software Engineering Notes for the course MSM1F3 Dr. R. A. Wilson October 1996 Chapter 1 Logic Lecture no. 1. We introduce the concept of a proposition, which is a statement
More information6.080/6.089 GITCS Feb 12, 2008. Lecture 3
6.8/6.89 GITCS Feb 2, 28 Lecturer: Scott Aaronson Lecture 3 Scribe: Adam Rogal Administrivia. Scribe notes The purpose of scribe notes is to transcribe our lectures. Although I have formal notes of my
More informationThis asserts two sets are equal iff they have the same elements, that is, a set is determined by its elements.
3. Axioms of Set theory Before presenting the axioms of set theory, we first make a few basic comments about the relevant first order logic. We will give a somewhat more detailed discussion later, but
More informationA Second Course in Mathematics Concepts for Elementary Teachers: Theory, Problems, and Solutions
A Second Course in Mathematics Concepts for Elementary Teachers: Theory, Problems, and Solutions Marcel B. Finan Arkansas Tech University c All Rights Reserved First Draft February 8, 2006 1 Contents 25
More informationSYMBOL AND MEANING IN MATHEMATICS
,,. SYMBOL AND MEANING IN MATHEMATICS ALICE M. DEAN Mathematics and Computer Science Department Skidmore College May 26,1995 There is perhaps no other field of study that uses symbols as plentifully and
More informationWorking with whole numbers
1 CHAPTER 1 Working with whole numbers In this chapter you will revise earlier work on: addition and subtraction without a calculator multiplication and division without a calculator using positive and
More information6 EXTENDING ALGEBRA. 6.0 Introduction. 6.1 The cubic equation. Objectives
6 EXTENDING ALGEBRA Chapter 6 Extending Algebra Objectives After studying this chapter you should understand techniques whereby equations of cubic degree and higher can be solved; be able to factorise
More informationCONTINUED FRACTIONS AND PELL S EQUATION. Contents 1. Continued Fractions 1 2. Solution to Pell s Equation 9 References 12
CONTINUED FRACTIONS AND PELL S EQUATION SEUNG HYUN YANG Abstract. In this REU paper, I will use some important characteristics of continued fractions to give the complete set of solutions to Pell s equation.
More informationFACTORING POLYNOMIALS IN THE RING OF FORMAL POWER SERIES OVER Z
FACTORING POLYNOMIALS IN THE RING OF FORMAL POWER SERIES OVER Z DANIEL BIRMAJER, JUAN B GIL, AND MICHAEL WEINER Abstract We consider polynomials with integer coefficients and discuss their factorization
More informationMATH 537 (Number Theory) FALL 2016 TENTATIVE SYLLABUS
MATH 537 (Number Theory) FALL 2016 TENTATIVE SYLLABUS Class Meetings: MW 2:003:15 pm in Physics 144, September 7 to December 14 [Thanksgiving break November 23 27; final exam December 21] Instructor:
More information11 Ideals. 11.1 Revisiting Z
11 Ideals The presentation here is somewhat different than the text. In particular, the sections do not match up. We have seen issues with the failure of unique factorization already, e.g., Z[ 5] = O Q(
More informationMath 319 Problem Set #3 Solution 21 February 2002
Math 319 Problem Set #3 Solution 21 February 2002 1. ( 2.1, problem 15) Find integers a 1, a 2, a 3, a 4, a 5 such that every integer x satisfies at least one of the congruences x a 1 (mod 2), x a 2 (mod
More informationPlaying with Numbers
PLAYING WITH NUMBERS 249 Playing with Numbers CHAPTER 16 16.1 Introduction You have studied various types of numbers such as natural numbers, whole numbers, integers and rational numbers. You have also
More informationNotes on Factoring. MA 206 Kurt Bryan
The General Approach Notes on Factoring MA 26 Kurt Bryan Suppose I hand you n, a 2 digit integer and tell you that n is composite, with smallest prime factor around 5 digits. Finding a nontrivial factor
More informationCosmological Arguments for the Existence of God S. Clarke
Cosmological Arguments for the Existence of God S. Clarke [Modified Fall 2009] 1. Large class of arguments. Sometimes they get very complex, as in Clarke s argument, but the basic idea is simple. Lets
More informationk, then n = p2α 1 1 pα k
Powers of Integers An integer n is a perfect square if n = m for some integer m. Taking into account the prime factorization, if m = p α 1 1 pα k k, then n = pα 1 1 p α k k. That is, n is a perfect square
More informationDIVISIBILITY AND GREATEST COMMON DIVISORS
DIVISIBILITY AND GREATEST COMMON DIVISORS KEITH CONRAD 1 Introduction We will begin with a review of divisibility among integers, mostly to set some notation and to indicate its properties Then we will
More informationdef: An axiom is a statement that is assumed to be true, or in the case of a mathematical system, is used to specify the system.
Section 1.5 Methods of Proof 1.5.1 1.5 METHODS OF PROOF Some forms of argument ( valid ) never lead from correct statements to an incorrect. Some other forms of argument ( fallacies ) can lead from true
More informationToday s Topics. Primes & Greatest Common Divisors
Today s Topics Primes & Greatest Common Divisors Prime representations Important theorems about primality Greatest Common Divisors Least Common Multiples Euclid s algorithm Once and for all, what are prime
More informationMATHEMATICAL INDUCTION. Mathematical Induction. This is a powerful method to prove properties of positive integers.
MATHEMATICAL INDUCTION MIGUEL A LERMA (Last updated: February 8, 003) Mathematical Induction This is a powerful method to prove properties of positive integers Principle of Mathematical Induction Let P
More informationCircles in Triangles. This problem gives you the chance to: use algebra to explore a geometric situation
Circles in Triangles This problem gives you the chance to: use algebra to explore a geometric situation A This diagram shows a circle that just touches the sides of a right triangle whose sides are 3 units,
More informationFOUNDATIONS OF ALGEBRAIC GEOMETRY CLASS 22
FOUNDATIONS OF ALGEBRAIC GEOMETRY CLASS 22 RAVI VAKIL CONTENTS 1. Discrete valuation rings: Dimension 1 Noetherian regular local rings 1 Last day, we discussed the Zariski tangent space, and saw that it
More informationStanford Math Circle: Sunday, May 9, 2010 SquareTriangular Numbers, Pell s Equation, and Continued Fractions
Stanford Math Circle: Sunday, May 9, 00 SquareTriangular Numbers, Pell s Equation, and Continued Fractions Recall that triangular numbers are numbers of the form T m = numbers that can be arranged in
More informationDiscrete Mathematics and Probability Theory Fall 2009 Satish Rao, David Tse Note 10
CS 70 Discrete Mathematics and Probability Theory Fall 2009 Satish Rao, David Tse Note 10 Introduction to Discrete Probability Probability theory has its origins in gambling analyzing card games, dice,
More informationCubes and Cube Roots
CUBES AND CUBE ROOTS 109 Cubes and Cube Roots CHAPTER 7 7.1 Introduction This is a story about one of India s great mathematical geniuses, S. Ramanujan. Once another famous mathematician Prof. G.H. Hardy
More informationMath 223 Abstract Algebra Lecture Notes
Math 223 Abstract Algebra Lecture Notes Steven Tschantz Spring 2001 (Apr. 23 version) Preamble These notes are intended to supplement the lectures and make up for the lack of a textbook for the course
More informationThe Division Algorithm for Polynomials Handout Monday March 5, 2012
The Division Algorithm for Polynomials Handout Monday March 5, 0 Let F be a field (such as R, Q, C, or F p for some prime p. This will allow us to divide by any nonzero scalar. (For some of the following,
More informationInteger roots of quadratic and cubic polynomials with integer coefficients
Integer roots of quadratic and cubic polynomials with integer coefficients Konstantine Zelator Mathematics, Computer Science and Statistics 212 Ben Franklin Hall Bloomsburg University 400 East Second Street
More informationMath 115 Spring 2011 Written Homework 5 Solutions
. Evaluate each series. a) 4 7 0... 55 Math 5 Spring 0 Written Homework 5 Solutions Solution: We note that the associated sequence, 4, 7, 0,..., 55 appears to be an arithmetic sequence. If the sequence
More informationObjective. Materials. TI73 Calculator
0. Objective To explore subtraction of integers using a number line. Activity 2 To develop strategies for subtracting integers. Materials TI73 Calculator Integer Subtraction What s the Difference? Teacher
More informationJobTestPrep's Numeracy Review Decimals & Percentages
JobTestPrep's Numeracy Review Decimals & Percentages 1 Table of contents What is decimal? 3 Converting fractions to decimals 4 Converting decimals to fractions 6 Percentages 6 Adding and subtracting decimals
More informationTom wants to find two real numbers, a and b, that have a sum of 10 and have a product of 10. He makes this table.
Sum and Product This problem gives you the chance to: use arithmetic and algebra to represent and analyze a mathematical situation solve a quadratic equation by trial and improvement Tom wants to find
More informationSYSTEMS OF PYTHAGOREAN TRIPLES. Acknowledgements. I would like to thank Professor Laura Schueller for advising and guiding me
SYSTEMS OF PYTHAGOREAN TRIPLES CHRISTOPHER TOBINCAMPBELL Abstract. This paper explores systems of Pythagorean triples. It describes the generating formulas for primitive Pythagorean triples, determines
More informationVieta s Formulas and the Identity Theorem
Vieta s Formulas and the Identity Theorem This worksheet will work through the material from our class on 3/21/2013 with some examples that should help you with the homework The topic of our discussion
More information. 0 1 10 2 100 11 1000 3 20 1 2 3 4 5 6 7 8 9
Introduction The purpose of this note is to find and study a method for determining and counting all the positive integer divisors of a positive integer Let N be a given positive integer We say d is a
More informationRegular Languages and Finite Automata
Regular Languages and Finite Automata 1 Introduction Hing Leung Department of Computer Science New Mexico State University Sep 16, 2010 In 1943, McCulloch and Pitts [4] published a pioneering work on a
More information1. The Fly In The Ointment
Arithmetic Revisited Lesson 5: Decimal Fractions or Place Value Extended Part 5: Dividing Decimal Fractions, Part 2. The Fly In The Ointment The meaning of, say, ƒ 2 doesn't depend on whether we represent
More informationProperties of Real Numbers
16 Chapter P Prerequisites P.2 Properties of Real Numbers What you should learn: Identify and use the basic properties of real numbers Develop and use additional properties of real numbers Why you should
More informationPage 331, 38.4 Suppose a is a positive integer and p is a prime. Prove that p a if and only if the prime factorization of a contains p.
Page 331, 38.2 Assignment #11 Solutions Factor the following positive integers into primes. a. 25 = 5 2. b. 4200 = 2 3 3 5 2 7. c. 10 10 = 2 10 5 10. d. 19 = 19. e. 1 = 1. Page 331, 38.4 Suppose a is a
More informationThe Chinese Remainder Theorem
The Chinese Remainder Theorem Evan Chen evanchen@mit.edu February 3, 2015 The Chinese Remainder Theorem is a theorem only in that it is useful and requires proof. When you ask a capable 15yearold why
More informationNormal distribution. ) 2 /2σ. 2π σ
Normal distribution The normal distribution is the most widely known and used of all distributions. Because the normal distribution approximates many natural phenomena so well, it has developed into a
More informationUnit 1 Number Sense. In this unit, students will study repeating decimals, percents, fractions, decimals, and proportions.
Unit 1 Number Sense In this unit, students will study repeating decimals, percents, fractions, decimals, and proportions. BLM Three Types of Percent Problems (p L34) is a summary BLM for the material
More informationEvery Positive Integer is the Sum of Four Squares! (and other exciting problems)
Every Positive Integer is the Sum of Four Squares! (and other exciting problems) Sophex University of Texas at Austin October 18th, 00 Matilde N. Lalín 1. Lagrange s Theorem Theorem 1 Every positive integer
More informationA Few Basics of Probability
A Few Basics of Probability Philosophy 57 Spring, 2004 1 Introduction This handout distinguishes between inductive and deductive logic, and then introduces probability, a concept essential to the study
More informationMATH10212 Linear Algebra. Systems of Linear Equations. Definition. An ndimensional vector is a row or a column of n numbers (or letters): a 1.
MATH10212 Linear Algebra Textbook: D. Poole, Linear Algebra: A Modern Introduction. Thompson, 2006. ISBN 0534405967. Systems of Linear Equations Definition. An ndimensional vector is a row or a column
More informationNotes on Determinant
ENGG2012B Advanced Engineering Mathematics Notes on Determinant Lecturer: Kenneth Shum Lecture 918/02/2013 The determinant of a system of linear equations determines whether the solution is unique, without
More information