V Adamchik 1 Integer Divisibility Victor Adamchik Fall of 2005 Lecture 3 out of seven Plan 1 Methods of Proofs review 2 Geometry of divisors 3 The greatest common divisor 4 Euclidean Algorithm Methods of Proofs The most theorems you want to prove are in the form P Q where P and Q are some statements Direct Proofs A direct proof is a flow of implications beginning with P and ending with Q Proofs by Contradiction In this method of proof we negate the result we need to prove namely statement Q Therefore we assume P and Not Q denote as Q In the proof flow we must arrive to some conclusion that either contradicts our assumptions or is something obviously not true P Q False Theorem If x is integer and x2 is even then x is even V Adamchik 21 127 Concepts of Mathematics x2 is even x x is even Proof x2 is even x Given x2 2 k and x 2n x is odd False 1 Combine them together 2k 2n 1 2k 4 n2 4n 2 k 2 n2 2n 2 1 1 Proofs by Contrapositive In this method of proof we reverse the logical implication Q P In the method of Contrapositive the goal of your proof is clear you must prove P Theorem If x and y are two integers whose product is odd then both must be odd x y x y is odd x y are odd Proof either x Given x 2 k and y y is even x y is even 2 n Combine them together Proofs by Mathematical Induction This proof technique can be stated as P0 kPk Pk 1 nP n First we prove that the theorem is true in the initial case Then we prove that if it is true for any given case it is true for the next case This will prove that it is true for all positive integers V Adamchik 3 Counting divisors Theorem For any positive integer p1 e1 x p2 e2 pn em the number of divisors is given by e1 1 e2 1 23 32 em 1 Example 72 has 12 divisors 72 The positive divisors of an integer are pictured in a Hasse diagram as follows two divisors a and b are connected by a path going up if a is a divisor of b V Adamchik 21 127 Concepts of Mathematics Exercise Draw a Hasse diagram for pk where p is prime How does the diagram help us to do algebra It can be used to compute GCD and LCM Observe that each element in the diagram generates a downward cone of divisors and upward code of multiples Therefore the intersection of downward cones gives the GCD of two numbers and the intersectionof two upward cones gives the LCM Problem A CMU football team has 100 lockers that initially closed Student 1 opens all lockers Student 2 closes all even lockers Student 3 changes the status of each locker multiple of 3 And so on student k changes the status of each locker multiple of k Which lockers are open after all 100 students have done their job Solution Think about what it takes to make a locker to end up open It takes an odd number of changes Which means an odd number of divisors Integer x Thus e1 p1 e1 p2 e2 pn em has e1 1 e2 1 em 1 e2 1 em 1 divisors 1 is odd or each factor is odd Therefore each ek is even So x must be a perfect square Open lockers are those which are 1 4 9 16 25 Exercise How many positive integers less than 100 have exactly 6 divisors V Adamchik 5 GCD Definition Suppose a and b are integers A greatest common divisor GCD is defined as gcd a b max d P d a d b Definition Integers a and b are relatively prime or coprime iff gcd a b 1 It is clear from the definition that gcd a b 1 gcd a b gcd a b min a b Exercise Prove that gcd a b gcd b a b Given a pair of numbers Does a GCD always exist Does it unique Let us prove it for positive integers Theorem a b d that is the GCD of a and b Proof Let S n a m b n m n a m b 0 Set S has a least element Let us call it d We need to prove that d is a gcd First we prove that d exists in other words that d a and d b By contradiction on minimality of d Assume that d a Using the division algorithm a r We see that r S and r a qd a q na mb qd r where 0 1 qn a r d qm b d Contradiction on minimality of d Next we prove that d is a greatest Assume that there is c such that c a and c b Therefore c divides their linear combination c n a m b c d V Adamchik 21 127 Concepts of Mathematics Finally we prove that d is unique Let d1 and d2 be gcds of a and b Suppose d1 is a greatest and d2 is a common divisor Then from the previous paragraph we see that d2 then d2 d1 Therefore d1 d1 Reversing rules d2 QED Corollary gcd a b n a m b where n m gcd 56 24 8 56 1 24 2 Euclidean Algorithm Given a pair of numbers a and b Find gcd a b Find such n m that gcd a b n a m b A useful lemma that is used in an algorithm for finding gcd Lemma Let a bq r then gcd a b gcd b r Proof Denote d1 d2 Since d1 gcd a b d1 Conversely since d2 d1 r gcd a b gcd b r d1 divides both r and b therefore d1 gcd b r d2 a d2 d2 divides both a and b therefore d2 d1 Hence d2 QED Theorem Euclidean Algorithm The algorithm computes a GCD of two positive integers a b We apply the division algorithm a b q1 r 1 0 r1 b b r1 q2 r 2 0 r2 r1 r1 r2 q3 r 3 0 r3 r2 0 rk rk rk rk 2 1 rk 1 qk rk qk 1 r k 0 1 V Adamchik 7 The last non zero remainder is GCD gcd a b rk Proof Let r1 r2 rk S Set S contains a least element This means that the above division will definitely terminate Next gcd a b gcd b r1 gcd r1 r2 gcd rk 1 rk gcd rk 0 rk QED Example Let us trace the algorithm to find GCD 203 91 203 91 21 2 91 21 4 21 7 3 7 0 Question When does the worst performance of the Euclidean Algorithm occur Let us run the algorithm for GCD 21 13 21 13 8 5 3 2 1 1 1 1 1 2 13 8 5 …