Proof That Euclid s Algorithm Works Now we should prove that this algorithm really does always give us the GCD of the two numbers passed to it First I will show that the number the algorithm produces is indeed a divisor of a and b a q1b r1 where 0 r b b q2 r 1 r 2 where 0 r2 r1 r1 q3r2 r3 where 0 r3 r2 ri qi 2ri 1 ri 2 where 0 ri 2 ri 1 rk 1 qk 1rk From the last equation we know that rk rk 1 So we know that we can express rk 1 crk where c is an integer Now consider the previous equation rk 2 qkrk 1 rk qkcrk rk rk qkc 1 Thus we have that rk rk 2 In our equation previous to that one we have rk 3 qk 1rk 2 rk 1 From here since rk rk 1 and rk rk 2 using our rules of divisibility we have that rk rk 3 As you can see we can continue this process considering each previous equation until we get to the last two where we will find that r k a and rk b Thus we find that Euclid s algorithm indeed gives us a common factor of a and b Now we have one more part to prove and that is to show that the common divisor that Euclid s algorithm produces is the largest possible This proof is going to look similar to the previous one but it is different in that we will start by assuming that a and b have a common factor d and then show that d rk Consider an arbitrary common factor d of a and b If d is a common factor we can rewrite a and b as follows a da b db where d a b are all positive integers Now consider the first equation from Euclid s algorithm a q1b r1 r1 da q1db Substitute for a and b and solve for r1 d a q1b Thus we have that d r1 Now consider the second equation and repeat the steps we did on the first this time solving for r2 Note We will let r1 dr1 where r1 is an integer b q2 r 1 r 2 r2 db q2dr1 d b q2d As you can see we can continue this process through each of the equations until we hit the second to last one where we will have rk 2 qkrk 1 rk rk drk 2 qkdrk 1 d rk 2 qkrk 1 thus d rk But this says that any arbitrary common factor of a and b that we originally picked divides into rk the value that Euclid s algorithm produced Since we know that rk IS a common factor to both a and b this shows that is must be the largest possible common factor or the GCD a b Well Ordering Principle Every non empty subset of Z the positive integers contains a smallest element Essentially the set Z is well ordered Well DUH This sounds like a really useless principle BUT it can be used to show that mathematical induction is a valid technique This is going to be an useful proof technique Here is the basic idea behind mathematical induction The goal of mathematical induction is to prove an open statement s n for all non negative integers n or all positive integers n We can do this in the following manner 1 Show that s 1 the base case is true 2 Show that s k s k 1 for all positive integers k We must show that proving the two above statements is equivalent to proving the open statement for all non negative integers n Now let s assume that these two conditions could hold while the statement s n is NOT true for all positive integers n This means that we can create a set F t Z s t is false that is non empty Since this set is a subset of Z it must contain a smallest element Let that smallest element be w Thus s w is NOT true is our assumption We know that w 1 since that is the first requirement for an inductive proof to hold Thus we know that w 1 which means that w 1 Z But we know that if w 1 Z AND that s w 1 is TRUE because we assumed that w was the SMALLEST value for which s n was NOT true Combining that with the fact that s k s k 1 for all positive integers k then we can plug in k w 1 to get s w 1 s w 1 1 or s w 1 s w implying that s w is true But this contradicts our assumption that s w is false Thus we can conclude that proving the 2 given statements proves the open statement under consideration Mathematical Induction Often times we would like to make a statement about the natural numbers 0 1 2 such as for all natural numbers n the sum of 1 2 3 n n n 1 2 However proving such a statement may be difficult if we are not very creative or proficient with algebra In particular it would be nice if we could prove a given statement without plugging in every possible value of n which would clearly take forever or using terribly clever mathematics Induction makes this possible The induction principle is as follows Let A Z where the following two properties hold 1 1 A 2 k A k 1 A Then we have that A Z In layman s terms the way we will use this principle to prove statements is the following way Given an open statement s n where n is an arbitrary nonnegative integer we must show these two following things to prove the statement for all positive integers n 1 s 1 2 s k s k 1 for all positive integers k Now the first step is relatively simple Since s 1 is a simple statement you must simply plug in 1 into the open statement and assess the validity of the statement The second step must be broken down into two steps Notice that the second statement is vacuously true if s k is false Thus we do NOT care about these cases Instead what we must do is the following 1 Assume that s k is true Now under this assumption we must show that s k 1 is true So that is the following step 2 Show s k 1 using the assumption in the previous step If you happen to do step 2 WITHOUT any assumption from the previous step then your proof is not an inductive one it is merely a direct proof which would have worked if you simply tried to prove s n directly to begin with Real quickly here is how it works symbolically If we have s 1 and s k s k 1 we can plug in k 1 so s 1 s 1 s 2 s 2 Then …
View Full Document
Unlocking...