ࡱ> M bjbj== VWW@WPl   R>R>R>8>\>\CbN@A(.A.ADABBBr`t`t`t`t`t`t`$d %f`eBB"BBB`H**.ADAmaHHHB*R.ADAr`HBr`H HO:6T,|"TDAB@ @:R>CbT T b0CblTRfFfTH**** Math 496 Project Report Problem #14 John, Tom, and Ron Professor Curtis Bennett December 4, 2000 Introduction: Fibonacci Numbers and the Euclidean Algorithm Problem #14: The smallest pair of positive integers so that the Euclidean Algorithm when applied to them takes only one step is [1,1]. Similarly, the smallest pair of positive integers so that the Euclidean Algorithm takes only two steps is [3,2]. (Step 1: 3 = 2 1 + 1, Step 2: 2=12 + 0). Find the smallest pair of integers such that the Euclidean Algorithm takes three steps, four steps, etc. State and prove a theorem for the case of n steps. Given a pair of two positive integers, approximate a bound for how many steps the Euclidean Algorithm will take. The Euclidean Algorithm is a very useful algorithm for finding the greatest common divisor of any two given integers. Using the Euclidean Algorithm is a tedious task for pairs of large numbers because the algorithm requires a high number of steps to execute. We figured that if we could approximate the number of steps, and furthermore bound the number of steps then we could easily decide how practical the Euclidean Algorithm would be for the given pair of numbers. The Euclidean Algorithm is defined as follows: Let a and b be positive integers with b e" a. If a divides b, then the greatest common divisor of a and b is a. If a does not divide b, then apply the Division Algorithm repeatedly as follows: aq0 + r0 = b 0 < r0 < a r0q1 + r1 = a 0 < r1 < r0 & The process ends when a remainder of 0 is obtained. This must occur after a finite number of steps; that is, for some integer t: rt-1qt + rt = rt-2 0 < rt < rt-1 rtqt+1 + 0 = rt-1 Then rt, the last nonzero remainder, is the greatest common divisor of a and b. We began our investigation by looking at specific cases involving small integers. When working through the different cases, we noticed that there might be a relation to the Fibonacci sequence, which is defined as the sequence such that  EMBED Equation.3 . We did not have anything specific, but we kept noticing the numbers of that sequence being ones of interest. We noticed that when performing the Euclidean Algorithm on the Fibonacci numbers we seemed to get, after a few steps, down to the cases we were given (that [1,1] is the smallest pair that takes 1 step and that [3,2] is the smallest pair that takes two steps). We then noted that the smallest pair that would take three steps would have to have three as the second number and two as its first remainder thus setting it up to take one more step than the case of [3,2]. So, if this new number gives a remainder of two when performing the Euclidean Algorithm on [a3, 3], then the number  EMBED Equation.3  in order to make  EMBED Equation.3  the smallest integer,  EMBED Equation.3  would have to equal one. So,  EMBED Equation.3  or  EMBED Equation.3 . So the smallest pair that would take 3 steps is [5,3]. Not surprisingly, five is the next Fibonacci number after three. We did more examples using the same idea and found the smallest pair that would take four steps is [8,5] and the smallest for five steps is [13,8]. These are these first seven numbers in the Fibonacci sequence. This led us to state our theorem. Defining Smallest for RON Pairs Until this point we have been dealing with our problem almost entirely from an intuitive standpoint, and a fairly ambiguous one at that. When we use the words smallest with reference to a pair of integers, what precisely is meant? Obviously, we are talking not just about a property of a single pair of integers, but a relation between two pairs; one pair of integers is smaller than another pair. When comparing two integers (rather than two integer pairs), a relationship involving a conception of magnitude is already defined: namely, the greater than and less than relations, denoted symbolically by the symbols < and >. The integers are an ordered set. However, no such ordering has been previously defined for integer pairs. While many number sets have such an ordering, including most familiar ones (e.g. natural numbers, integers, rational numbers, and the real numbers), not every set of numbers is ordered; for example, the complex numbers have no immediate ordering principle2i cannot be said to be less than 3i in the same way that 2 is less than 3. However, complex numbers can be assigned a real number magnitude in the complex plane that in principle could be used to order the set, at least partially. This has direct bearing upon our Euclidean Algorithm integer pairs, since complex numbers involve pairs of real numbers a real coefficient and an imaginary coefficient. One could choose to order the complex numbers based solely on one of these coefficients (the real or the imaginary), or any number of other possibilities. Another analogous situation in geometry is the measurement of perimeter versus area, or surface area as opposed to volume; shapes can be related to one another based on two different computations of magnitude. Each potential ordering would yield different information about a number and its relationship with other numbers, which could be used for different purposes. One could imagine a plurality of such orderings, depending upon the task required for each. What we want to do is to mathematically define our smaller than relationship for integer pairs so that our ordering yields information germane to the task at hand: namely, trying to determine the number of steps the Euclidean Algorithm takes to compute the greatest common divisor of an arbitrary pair of positive integers. Ideally, our definition will reveal our conjecture about the Fibonacci numbers to be true. At the same time we want to retain at least in part the intuitive conception of smaller than that generated this conjecture. Logically, the relation smaller than could be defined in almost any conceivable manner, up to and including the exact contrary of our intuitive idea of smaller, or something almost entirely unrelated. This is pure and original mathematics. The business of mathematicians initially and for the most part is to frame precise concepts corresponding to our intuitive apprehension. From this definitional (or axiomatic) foundation, we then employ similarly precise argumentation to yield original knowledge in the form of logically grounded results. When mathematics is at its best, not only are the axiomatic foundations and definitional supplements clear and the system itself sound, but also new nonintuitive knowledge is gained from these foundations. This affirms the fundamentally creative and synthetic nature of mathematics while maintaining the importance of analytic thought and reasoning from foundational security. From a students perspective, making such conceptual definitions and subsequently proving theorems using those definitions is to not only gain a crucial insight into how mathematics functions beyond the level of the algorithm but to genuinely make a contribution to the body of mathematical knowledge through the exploration of such definitions and their consequences. Upon examination, it becomes apparent that there are many mathematical interpretations for smaller than, each of which possesses a degree of intuitive validity. Regardless of our definition, we certainly want to avoid blatantly counterintuitive conclusions, both for the purposes of our proof and as a general heuristic principle. Thus, for example, [1,2] should be smaller than [1000,1500]. It is clear that our task is greatly simplified if we rely on the less than and greater than relations for the integers, our model for an ordering relation. Each of the examples cited above in some way involve reducing a question of n constants (e.g., length, width, and height) to a question of a single constant (e.g., volume) and then comparing objects using less than, greater than, and equality. Similarly, we want to derive some single number from each pair for the purposes of comparison. Ostensibly, several examples immediately present themselves as sound candidates. One could take the sum of the two integers, or, alternatively, the product. Following geometry and analysis, one could consider the Euclidean norm of a pair of integers; for example, the norm of [3,4] would be  EMBED Equation.3  A wealth of other calculation of norms is available from other branches of mathematics. However, certain cases present problems for these interpretations, which demand consultation of our intuitive understanding of smaller than in the context of the Euclidean Algorithm. Should [4,5] be smaller than [3,6]? The two pairs possess the same sum. The product of [4,5] is greater than the product of [3,6]. Meanwhile the norm of [4,5] is less than the norm of [3,6]. Clearly, then, these definitions are not equivalent. Furthermore, upon inspection they are absolutely false on their face at predicting the number of steps required to compute the greatest common divisor of a pair using the Euclidean Algorithm. So what definition of smaller than provides the most pertinent information for the pairs greatest common divisor? Examining the Euclidean Algorithm, we take note of several facts. First, with respect to the Euclidean Algorithm and greatest common divisors, the pairs themselves are unordered; that is, the pair [a,b] is essentially equivalent to the pair [b,a] where a and b are integers. This is not the case with all pairs of integers, even where the norms are identical; for example, with points in the plane, or lengths and widths of rectangles, the order of the numbers given yields very specific information about the mathematical object being studied. Until this point, we have been speaking very loosely about a pair of integers, and relations between those pair of integers, without defining precisely what we mean by such a pair. This is crucial not only for greater precision in our reasoning, but also, as we shall see, our smaller than ordering relation may well yield different information for equivalent pairs if we do not clarify what we mean by a pair. For example, under some definitions, smaller than could paradoxically state that the pair [3,5] is smaller than the pair [5,3]; two equivalent pairs with respect to their GCDs. In another context, such definitions may actually be highly useful; but for the problem at hand we want to be certain that our pairs or the smaller than relation are defined in such a way that equivalent pairs are seen as such. Until we are ready to make these definitions, however, we will by necessity continue to speak loosely about a pair of integers. Continuing, we note that in the second step of the Euclidean Algorithm, the lesser integer of the pair is retained while the greater integer is discarded. For example, when applying the Euclidean Algorithm on the pair [7,59], while the first step retains the number 59, by the second step, it is discarded: 7 8 + 3 = 59 3 2 + 1 = 7 With the second step, a new Euclidean Algorithm begins, and similarly for each subsequent step until a remainder of zero is reached in this case, the Euclidean Algorithm is essentially used after the second step to determine the GCD of the pair [3,7] by almost any intuitive definition a smaller pair than [7,59]. If we knew the number of steps it took to compute the GCD of [3,7], we could simply add 1 (for the first step) to find the number of steps needed to compute the GCD of [7,59]. Since the remainder (which is carried over to the subsequent step) is always bounded above by the lesser integer of the original pair, the larger number is simply irrelevant for determining a top bound for steps of the Euclidean Algorithm. As the greater number grows larger and larger, it only cycles modulo the lesser number with respect to its remainder; apart from that, its size signifies nothing, since from its magnitude alone (in isolation from the other number) we cannot determine what its remainder will be. Thus we see that the bound for the number of steps of the Euclidean Algorithm can be determined completely from the smaller number with greater precision before actually performing the algorithm than by considering the two together in some combination. Hence in most cases, we want to examine the lesser integer of the pair in order to determine whether or not one pair is smaller than another. The intuitive exception would be in cases where the lesser numbers in each pair were equal to one another; for example, ideally I would want [8,9] to be smaller than [8,13], primarily because this satisfies my intuition that since 9 < 13, [8,9] would be smaller than [8,13], but also since [8,9] takes fewer steps under the Euclidean Algorithm than [8,13]. So, since the Euclidean Algorithm depends almost entirely on the lesser integer of the pair, we will define our pairs and our relation accordingly. We have done the exploratory work needed to determine what we have meant in our casual discourse about pairs of integers and the smaller than relation and properly motivate their definitions. Now we are ready to precisely define these terms and to use them to prove some important facts about the Euclidean Algorithm. --- (1) Definition: A RON Pair is any pair of positive integers [a,b] where a < b. Consequently the set of all RON Pairs is the set S = {(a,b) : a,b  EMBED Equation.3  N, b a  EMBED Equation.3  N }, taking N to be the set of positive integers (assumed here to be known or constructed), and b a  EMBED Equation.3  N to be the customary definition of a < b. Observe that for every ordered pair of positive integers (a,b) in N2 , excepting pairs of the form (a,a), there is a corresponding RON Paireither [a,b] (if a < b ) or [b,a] (if b < a). We are justified in excluding pairs of the form (a,a) since the Euclidean Algorithm on such pairs is essentially redundant; their GCD is automatically a. (2) Definition: For any two RON Pairs [a,b] and [c,d], [a,b] is said to be smaller than [c,d] if one of the following mutually exclusive conditions hold: a < c ; a = c and c < d. In such cases we write [a,b] % [c,d]. In such a case [c,d] is said to be bigger than [a,b]. If a = c and c = d then [a,b] is said to be equal to [c,d], written [a,b] = [c,d]. In a set W of RON pairs, [a,b] is said to be the smallest pair in W if for any other RON pair [e,f] in W, [a,b] % [e,f]. --- Now we observe some facts about the % , or smaller than, relation. We have chosen this symbol primarily to suggest the symbol for the less than relation (<), and many of the following facts rely primarily on facts about the < relation. This is an excellent opportunity to concretely explore some important logical relations seen in algebra, such as transitivity, symmetry, etc. This also foreshadows some important concepts in higher mathematics while reinforcing our apprehension of their presence in logical relations used every day such as the equality relation and the less than relation. (3) Trichotomy. For any two RON Pairs [a,b] and [c,d], exactly one of the following holds: [a,b] % [c,d]; [a,b] is bigger than [c,d]; [a,b] = [c,d]. This follows directly from trichotomy in the integers. Suppose [a,b] and [c,d] are RON pairs. Then a, b, c, d are all positive integers. Hence a < c, a > c, or a = c, and b < d, b > d, or b = d. If a < c, then [a,b] % [c,d] by (2). If a > c, then [a,b] is bigger than [c,d]. If a = c, then we examine b and d. If b < d, then [a,b] % [c,d]. If b > d, then [a,b] is bigger than [c,d]. If b = d, then [a,b] = [c,d]. Since this exhausts all possible cases, our proposition is proven. (4) The relation  equal to is an equivalence relation; i.e., it is reflexive, symmetric, and transitive. This proof similarly follows directly from the properties of the equality relation on the integers and is trivial. (5) The smaller than relation (%) is irreflexive and antisymmetric. Since [a,b] = [a,b], [a,b] is never smaller than [a,b] by trichotomy. Similarly, if [a,b] % [c,d], then [c,d] is greater than [a,b] and consequently [c,d] cannot be less than [a,b]. (6) % is transitive. Consequently if [a,b] % [c,d] and [c,d] % [e,f], then [a,b] % [e,f]. Suppose that [a,b] % [c,d] and [c,d] % [e,f]. Then a < c or a = c and b < d, and c < e or c = e and d < f. Thus we distinguish four cases and proceed as follows: Case One: a < c and c < e. Then since < is transitive, a < e and thus [a,b] % [e,f]. Case Two: a < c, c = e and d < f. Then a < c = e implies that a < e and thus [a,b] % [e,f] Case Three: a = c, b < d, and c < e. Then a = c < e implies that a < e and thus [a,b] % [e,f] Case Four: a = c, b < d, c = e, d < f. Then a = c = e implies that a = e. Also b < d, d < f implies that b < f by transitivity. Thus [a,b] % [e,f]. Since this exhausts all possible cases, % is transitive. Fibonacci Numbers and the JOHN Theorem In the previous section, we made some important definitions that now enable us to deal with an ordering for pairs of positive integers. From this point we made the natural move to examine the properties of the smaller than relation for the set of RON pairs. We could easily extend these definitions further, defining RON n-tuples in the same lexicographic style, and extending the definition of smaller than accordingly. This pure mathematics could conceivably have a number of applications. However, at this point we want to turn to the particular application that motivated our definition of both RON pairs and the smaller than relation: the Euclidean Algorithm. (7) The JOHN Theorem for the Euclidean Algorithm. Let F(k) be the kth number in the Fibonacci Sequence, where F(0) = 1, F(1) = 1, and F(k+1) = F(k) + F(k-1). Then for n e" 2, [F(n), F(n+1)] is the smallest RON pair for which the Euclidean Algorithm takes n steps.  Since the Fibonacci numbers are defined recursively, it seems natural to prove this theorem by induction on n. First, however, we want to observe the following fact about the Euclidean Algorithm on [F(k), F(k+1)]. Since F(k+1) = F(k) + F(k-1) for all k > 1, the Euclidean Algorithm proceeds as follows: F(k) 1 + F(k-1) = F(k+1) F(k-1) 1 + F(k-2) = F(k) F(k-2) 1 + F(k-3) = F(k-1) F(1) 1 + F(0) = F(2) F(0) 1 + 0 = F(1). Thus every step in the Euclidean Algorithm involving consecutive Fibonacci numbers involves more Fibonacci numbersin fact, every Fibonacci number less than or equal to F(k+1). Also, every Fibonacci number is relatively prime to its successor and its predecessor, since the last nonzero remainder is always F(0) = 1. We will use the first observation in our proof repeatedly, but both observations give us some indication as to why the Fibonacci numbers have this particular relationship with the Euclidean Algorithm. Now that we possess the proper tools in terms of our definitions, the proof is disarmingly simple. Proof: By induction on n. For n = 2. [2,3] is the smallest pair of integers for which the Euclidean Algorithm takes 2 steps, and 2 is the 2nd Fibonacci number while 3 is the third. Suppose that for all integers k e" 2 and less than or equal to n, [F(k-1), F(k)] is the smallest pair of integers such that the Euclidean Algorithm takes k-1 steps. We want to show that [F(n), F(n+1)] is the smallest pair of integers such that the Euclidean Algorithm takes n steps. (8) Claim 1: The Euclidean Algorithm on [F(n), F(n+1)] takes n steps. Proof: Since we are dealing with the Fibonacci sequence, by definition F(n+1) = F(n) 1 + F(n-1), where F(n-1) < F(n). (Note: This fact proves that [F(k), F(k+1)] is a RON pair for all k e" 1.) Thus the second step of the Euclidean Algorithm is F(n) = F(n-1) 1 + F(n-2). But by our hypothesis [F(n-1), F(n)] takes n - 1 steps. Thus the Euclidean Algorithm terminates after n - 1 more steps. Therefore, adding only our first equation, we see that [F(n), F(n+1)] takes a total of n steps. (9) Claim 2: [F(n), F(n+1)] is the smallest pair of integers with n steps. Proof: Let [a,b] be a RON pair smaller than [F(n), F(n+1)]. Then a < F(n) or a = F(n) and b < F(n+1). We want to show that the Euclidean Algorithm on [a,b] takes less than n steps. Consider the Euclidean Algorithm on [a,b]. By the Division Algorithm there exist integers q0 and r0 such that (9.0) b = aq0 + r0, where 0 d" r0 < a. Now the second step of the Euclidean Algorithm (if it continues) is (9.1) a = r0q1 + r1, where q1 is an integer and 0 d" r1 < r0. The third step (if it continues) is (9.2) r0 = r1q2 + r2. Case One: a < F(n). Case 1a: r0 d" F(n-1). Then [r0, a] is smaller than [F(n-1), F(n)] and therefore takes less than n - 1 steps. Thus, adding (9.0) as the first step, we see that [a,b] takes less than n steps. Case 1b: r0 > F(n-1). By (9.0) a > r0, such that a = r0 + some positive integer. Therefore q1 e" 1. We will show that r1 < F(n-2). Suppose to the contrary that r1 e" F(n-2). Then by (1) a = r0q1 + r1 > F(n-1) + F(n-2) = F(n), such that a > F(n). But this contradicts our assumption that a < F(k). Therefore r1 < F(n-2). Thus [r1, r0] is smaller than [F(n-2), F(n-1)]. Hence by our induction hypothesis the Euclidean Algorithm on [r1,r0] takes less than n - 2 steps. Adding equations (9.0) and (9.1) as our first and second steps, respectively, we see that [a,b] must take less than n steps. Case Two: a = F(n) and b < F(n+1). Then by substitution F(n) + r0 = a + r0 = b < F(n+1) = F(n) + F(n-1). Hence r0 < F(n-1). Therefore [r0, a] is smaller than [F(n-1), F(n)] and hence the Euclidean Algorithm takes less than n -1 steps. Thus the Euclidean Algorithm on [a,b] takes less than n steps. Therefore [F(n), F(n+1)] is the smallest pair of integers for which the Euclidean Algorithm takes n steps. QED. Approximating a Bound The TOM Algorithm With the previous theorem, we have shown that the smallest RON pair for which the Euclidean Algorithm takes n steps is given by the Fibonacci Numbers [F(n), F(n+1)]. Thus conceivably for any RON pair [a,b], we can bound the number of steps the Euclidean Algorithm takes on [a,b] by the next highest pair of Fibonacci numbers. Since there are infinitely many Fibonacci numbers, for every integer a, there exists a Fibonacci number F(n) such that a < F(n). By the theorem just proven, if a < F(n), then [a,b] is smaller than [F(n), F(n+1)] and thus for any integer b > a, computing the GCD of [a,b] takes less than n steps. If a = F(n), then a takes n or fewer steps: if b < F(n+1), we can guarantee that the Euclidean Algorithm takes less than n steps; if b > F(n+1), it may take up to n steps, and if b=F(n+1), it takes precisely n steps. Can we use the theorem just proven to find a simple computation to bound the number of steps the Euclidean Algorithm takes for an arbitrary RON Pair? Upon examination of the first n Fibonacci numbers for low n, we notice a pattern. There are no more than five Fibonacci numbers with m digits for any positive integer m except for the first 6 Fibonacci numbers, which each have 1 digit. If we could guarantee that there were five Fibonacci numbers for every number of digits m, we could easily determine a bound for the Euclidean Algorithm for [a,b] by finding the number of digits of a and then finding the largest Fibonacci number with the same number of digits. If a has the same number of digits as F(n), where F(n) is the largest such Fibonacci number, then a is clearly less than F(n+1), since F(n+1) has more digits than a. Hence [a,b] is smaller than [F(n+1), F(n+2)] and consequently the Euclidean Algorithm on [a,b] takes n or fewer steps. Upon further observation, it becomes clear that not every set of numbers with m digits contains 5 Fibonacci Numbers. Some contain 4. This is not a damaging consequence, however, since we want to approximate an upper bound. If we were to assume that every such set did contain 5 Fibonacci Numbers, we will actually be overestimating our guess for n, where F(n) is the largest Fibonacci number with m digits. We only need to make sure that there can be no more than 5 Fibonacci numbers with m digits for any m. (10) Lemma: For all Fibonacci numbers F(n), 2F(n) e" F(n+1). Proof: Now for n = 0, clearly 2 e" 1. For n > 0, F(n + 1) = F(n) + F(n-1). Since F(n) e" F(n-1), F(n+1) d" F(n) + F(n) = 2F(n). (11) TOM s Proposition: For any positive integer m, the largest possible Fibonacci number with m digits is less than or equal to F(5m). The proof is by induction on m. First note that the largest Fibonacci number with 1 digit is F(5) = 8. Now assume that for all positive integers k where k d" m, the largest Fibonacci number with k digits is less than or equal to F(5k). We want to show that the largest Fibonacci number with m + 1 digits is less than or equal to F(5(m+1)). Let f1 be the smallest Fibonacci number with m + 1 digits. Then f1 e" 10m+1 , since 10m+1 is the smallest integer with m + 1 digits. Consequently f0, the Fibonacci number immediately preceding f1, must be greater than or equal to 510m. Hence f2 = f1 + f0 e" 10m+1 + 5m = 10m (15). Similarly, f5 = 3f2 + 2f1 e" 3 10m(15) + 2 10m+1 = 10m(65), and f4 e" 10m (40). Consequently f6 = f5 + f4 e" 10m(65) + 10m(40) = 10m(105) = 10m+2 +10m(5). Hence f6 has at least m + 2 digits. So all Fibonacci numbers with m + 1 digits or fewer are less than or equal to f5. Since by our hypothesis f0 d" f(5m), f5 d" f(5m+5) = f(5(m+1)). QED. How can we determine the number of digits of an arbitrary positive integer a? This is easy enough; simply take the integer part of the common logarithm function. This in conjunction with the proposition just proven yields the following algorithm for bounding the number of steps the Euclidean Algorithm takes to find the GCD on an arbitrary RON pair [a,b]: (12) TOMs Algorithm: Let [a,b] be any RON pair. The number of steps for the Euclidean Algorithm on [a,b] is bounded above by 5 Ipart(log10 a), where Ipart(x) is the greatest integer less than or equal to x. This follows directly from the JOHN Theorem and TOMs Proposition. Refining the bound Our second approximation is similar, except it uses the Fibonacci number just greater than or equal to a - Ipart (a/b) " b. This is the first remainder obtained from the first step of the Euclidean Algorithm performed on the pair [a, b]. This provides for a better bound than the smallest number of [a,b] because it accounts for the possibility of the numbers being very large, yet relatively close. For example, suppose we wanted to estimate the number of steps required to perform the Euclidean Algorithm on the pair [38,43]. From our first method we would have gotten that rounding the lower number up to the next Fibonacci number gets us to 55. Since 55 = F(9) from our definition of the Fibonacci numbers earlier, we would estimate it to take nine steps. However, taking the first remainder of this division (5), since 5 = F(4), adding one to account for the first step taken to find this remainder, our new estimate would be 5 steps. This is a much smaller and more precise upper bound than our initial estimate. Our third approximation is to take successive remainders from [a,b] using the Euclidean Algorithm. Using this, we can get a better approximation when [a,b] are large integers, approximately anything over 100 -500. After each step, the RON pairs being studied become smaller and smaller, and consequently the estimate for the bound becomes more and more precise. Furthermore, large pairs with trivial early remainders are weeded out. However, with exceedingly large numbers, the remainders become more and more difficult to calculate. Large numbers will always pose a significant problem for any bound approximation. Examining a logarithmic graph of the Fibonacci numbers (see figure 1 below), it becomes clear that a better logarithmic approximation than the common logarithm probably exists. Our method for the common logarithm is very useful for finding rough bounds for relatively smaller pairs, particularly when the number of digits can simply be observed without computing the logarithm. However, it has a significant drawback: for larger pairs of numbers it increasingly overestimates the number of steps needed. Further exploration with the Fibonacci numbers is required in order to determine a better bound. This is a natural expansion of the work begun here. Everything here, apart from some of the language and imported apparatus of mathematical proofs, relies solely upon knowledge and computations that are possible at the high school level. However, the themes raised by this exploration touch on many important themes in higher level mathematics that could be explored for the first time in a high school setting: the idea of recursive definition, the importance and creativity involved in precise definition of concepts, and the principle of mathematical induction. Students are also introduced to two important and ubiquitous ideas in mathematics: the Euclidean Algorithm and the Fibonacci Sequence. Students can see how seemingly unrelated mathematical ideas can involve one another in interesting and unexpected ways, which then can be used to predict information regarding the greatest common divisor, among other applications. Also, we have laid the groundwork for further exploration when more mathematics can be utilized, such as the generating function for the Fibonacci sequence, which can be used to derive a more accurate bound. But this is beyond the scope of what we have done here. ----  Figure 1. Fibonacci numbers vs. logarithmic graph of the value of the Fibonacci number. Weekly Journal for: JOHN, TOM, and RON Week 1 We got project #14. We did a multitude of plugging and chugging different integers into the Euclidean Algorithm to find the number of steps it took to find the GCD. We saw that the Fibonacci numbers appeared to be related somehow to the solution of the problem. Week 2 We are sure that for each increase in the number of steps of the Euclidean Algorithm that the pairs of subsequent Fibonacci numbers provide the smallest integers for that number of steps. We want to prove this with an induction proof. We are conjecturing that the smaller integer of a pair of successive Fibonacci numbers is a bound for the number of steps the Euclidean Algorithm would take to find the GCD. Work has been started to develop a spreadsheet on Excel to find the GCD. Week 3 We are wondering what the smallest integer means. We realize we can define this at least three different ways. We develop a pre-condition for the problem, that is, we want to be able to distinguish between the pairs (1,1) and (2,1) since both pairs take 1 step each. Week 4 We did not meet as a team this week. We made an Excel workbook to help with our investigations, and hopefully will be used to demonstrate our project to others. The spreadsheets calculate the greatest common divisor (GCD) of two integers, and produce a Fibonacci number corresponding to integer input from one to seventy. We developed a draft theorem which is, "The smallest pair of positive integers (a,b), such that the Euclidean Algorithm takes n steps is the two successive terms of the Fibonacci sequence (F(n+1), F(n)), with n greater than or equal to 2, and F(0) = F(1) = 1." Week 5 We all worked through out the week on our own. We came up with an induction proof for our function. We also came up with a new bound for the case of n steps, that the number of steps for the Euclidean Algorithm is the number of steps that corresponds to the Fibonacci number that is just less than or equal to the remainder when subtracting the original integers. It is not proven. We also noticed that the limit of the function F(n)/F(n+1) is the golden ratio. We dont know how this relates to our problem, but we found it interesting. Week 6 We met with the Professor this week. We decided that the definition of smallest we will use for our proof is the number with the smallest magnitude of a pair of positive integers. Week 7 We outlined the proof of our theorem. The proof is by induction as originally surmised. Week 8 We decided to write a GCD program using the TI-83 because of programming difficulties in Excel. We started the project write up, and made progress with the TI 83 Plus program. The final write up is shaping up as a chronological report, since the chronology corresponds with the proof of the problem. We also have come up with a few different ideas of where we would like to go from here. We have also come up with an idea of using the Euclidean Algorithm for finding the GCD of a larger set of numbers. We have also talked about defining the properties of lexicographical ordering of pairs. Week 9 We worked for a short time on writing up the final report on what we already have. We looked at the case of n-tuples and tried different conjectures on the number of steps it would take to find the GCD of an n-tuple. We looked at two different methods of finding the GCD for a set of numbers greater than two. The first way is by finding the GCD of every successive pair of numbers and the second is by taking the smallest number and finding the GCD of that and every other number in the set. This work intertwined with our approximation of a bound for the number of steps the Euclidean Algorithm will take to find the GCD of a pair of integers. We questioned that our bound isnt close as other options for large numbers. Thus we observed that there are no more than five Fibonacci numbers for any set of numbers within a given length of digits. We tried developing a formula for the relationship between the number of digits of an integer (assuming it is the smallest integer of a set) and the number of steps it would take to use the Euclidean Algorithm to find the GCD of the given set. We didnt come up with that, but did come up with a proof of our observation. This led us to see that a way of finding a Fibonacci number for any given integer can be done by knowing the number of digits in the given number. We continued examining our approximation for a bound and looked at cases with larger numbers and saw that our approximation works better each time we perform the Euclidean Algorithm. Week 10 We made a graph of the first 70 Fibonacci numbers using a logarithmic table in Excel, did some research in the library, and worked with a generating function we found in a book about Fibonacci numbers. This is the first time we used the library for our project. We did this because we felt we had hit a stage where we wanted to answer some questions for ourselves and knew that we couldnt impact the project at this point. We also made progress in developing a TI-83 program to give the GCD of two small integers. We are working on coming up with an approximation for the bound based on the graph of the Fibonacci sequence. We need to start dedicating ourselves to staying focused on writing the report or making a presentation instead of working on different aspects of the problem. If we could continue forging forward with exploring the problem, then we could look at how Fibonacci numbers relate to decimal expansions, and what role the logarithmic graph plays in applications. ATTACHMENT #1 TI - 83 Plus Program Calculating the GCD and # of steps the Euclidean Algorithm takes to find the GCD PROGRAM: GCDLCT :Prompt A,B :ClrList L1 :ClrList L2 :100(dim(L1) :100(dim(L2 ) : :For(X,1,100) :iPart(A/B)(Q :Q(L2 (X) :A - (Q*B)(L1 (X) :B(A :If L1 (X) = 0 :Goto GC :L1 (X)(B :End : :Lbl GC :If X=1 :Then :Output(5,1,GCD= ) :Output(5,8,B) :1(V :Goto GD :Else :X-1(V :End : :Output(5,1,GCD= ) :Output(5,8,L (V):L ) : :Lbl GD :Output(6,1,NUM OF STEPS ) :Output(6,14,V) ATTACHMENT #2 EXCEL Worksheet: Finding the GCD Given (a,b) find the greatest common divisorEuclidean Algorithm: a = bq + rtype any positive integerType in a 2nd (+)integerarranged a arranged bINT(a/b)b*qfinding r1461441461441144214427214401440#DIV/0!#DIV/0!#DIV/0! ATTACHMENT #3 The First 70 Fibonacci Numbers Finding the Fibonacci Number0111Type in n between N221 and 70:3334558 F(n) = 3613721834955108911144122331337714610159871615971725841841811967652010946211771122286572346368247502525121393261964182731781128514229298320403013462693121783093235245783357028873492274653514930352362415781737390881693863245986391023341554016558014141267914296424334944374370140873344113490317045183631190346297121507347480752697648777874204949125862690255020365011074513295128009952533162911735386267571272541.39584E+11552.25851E+11563.65435E+11575.91287E+11589.56722E+11591.54801E+12602.50473E+12614.05274E+12626.55747E+12631.06102E+13641.71677E+13652.77779E+13664.49456E+13677.27235E+13681.17669E+14691.90392E+14703.08062E+14   This definition is taken from the Hungerford Abstract Algebra Text, by Thomas Hungerford, 1997, Saunders College Publishing.  Furthermore, since we have demonstrated the exhaustive mathematical work necessary to motivate these definitions, proving our mettle as mathematicians, we are now justified in naming a few things after ourselves. Project Report MTH 496  DATE \@ "M/d/yy" 8/6/01 -- Page  PAGE 1 --  EMBED Excel.Sheet.8    ".st  +    & ( 4 6 8 : B F J P ^ ` f h t v x z e h i j n o s y ~  jT= CJUV jUH*6] j0JU556CJ OJQJOJQJ5CJOJQJ5CJ OJQJ5CJ I !"./BCDEFGHIbctuvwx$a$Cxyz{|}~ 4 j $a$` ] ^ 0"1"&&2*3*`` p^p`$a$ 78KLMNRSfghi$$&&&&&&**&+)+ j) EHUjn== CJUV5CJ j( EHUjX= CJUV jEHUjX= CJUV j7EHUjX= CJUV jWEHUjlX= CJUV j9EHUjX= CJUV 6H*]6] jU jEHU2)+1+2+7+8+-:.:8:B:C:E:G:O:r:u:}:::::::::::::::::::::::::;; ; ;`;f;g;z;{;|;};~;;;;;;;;;;;<<@<C<I<N<U<¸®H*j@6EHU]jo6EHU]jl= CJUVj6U] jEHUjk= CJUV jU 56\]5\ j0JU6]D3*00I1J1Y1g1h1880:4:=====>&?@ @DDEEEEH & F & F$a$`U<X<^<c<<<<<====(=+=2=5=9=<=L=X=Z=]=========> >4>:>Z>p>t>z>>>>>>>>>>> ??? ?Z?`??????@ @@E E.E4EEEEEEEEEEEEExF~FFFFFG$G(G2GNNO4PPPQQ`RRVSXSSSsVtVXXZZZZ$a$``PjPtPPPPPPPPPQ"Q(Q4QDQVQvQ|QQQQQQQRR6R@RPRlRRRRRRRVSSxVVVVWWXXYY]]]]]]^^^^N`O`\`c`````cczc|c&d'd4d;dsdtd|ddddddddddeeYe\eeeeeeH*5\ 5CJ \6]_ZZ[[]]]]_W`X```7a/d0d|ddeffXgzggghhi$j^$a$eeeeeeeeffffffffffffffgg&g(ggggggggggggg$h&h*h,hhh,i2iViXi|i~iiiiiiiii&j,j^j`jjjjjjjjjjjHkJkkkkkllllllmlolplllllmmPmQmYmZmmmmmH*6]c$jjrk mHmym=n>nnnnn&r'ruuwwFxxLyNygh^`mmmn!n4n5nnnnnoooohpipppppqq.q1qPqQq_q`q|q}qqqrrrrEsFsgshsttKtNttt&u'uguhuruuuuuuu2v3vAwBwLwMwtwuwwwwwwwwwFxPxfxhxxxXybydyzyyy zzVzXzzz{{{{{{5\ 5CJ \6]`{2|4||||}}}}}}}}}6~8~~~~~~~ (*46^`jlvx  *,>@RThnvxlnKLadmσ҃ CJ 5\H*H*6]_ oprt`$a$ rx̊ϊ%(yԚ՚ 06QXw!"'(-.45:;YZ^_`apqrsz{hvwB*OJQJhphOJQJmHnHu mHnHu jmHnHuH*5CJ5 jU6]O /07PQYu$a$uê #0>@N\fx}ѫ$a$ѫ-/7TdefghvwǬȬɬʬˬ $$Ifa$$Ifˬ̬ͬ e_e_$If$$Ifֈ\OA4&"&z4 a $$Ifa$ ԭklC]^pqwx jUjX= UV jU0JmHnHu0J j0JUCJmHnHu jCJUCJ j0JU B*hphOJQJB*OJQJhphB*H*OJQJhph! &2=FJTUYUdL $$Ifa$$$If֞_ \OA4&"&} 4 a$IfY]aegkmnopRH$$If֞_ \OA4&"&} 4 a $$Ifa$ ptvy}R$$If֞_ \OA4&"&} 4 a $$Ifa$ IGG$$If֞_ \OA4&"&} 4 a $$Ifa$ $$Ifa$ҭӭԭ j$$If\}pbY4 a $$Ifa$$If(*+-/x|rrxHr$If}$$Ifr}pbY4 a $$Ifa$ /012357 xxxxx $$Ifa$}$$Ifr}pbY4 a789:;=? xxxxx $$Ifa$}$$Ifr}pbY4 a?@Y[\^a{rrrr $$Ifa$$If}$$Ifr}pbY4 aabcdegj$xxxxx $$Ifa$}$$Ifr}pb    Y4 ajklmnpstuvwy|}$xxxxx$xxxxx( $$Ifa$}$$Ifr}pbY4 a }~x,x,}$$Ifr}pbY4 a $$Ifa$ x,x,}$$Ifr}pbY4 a $$Ifa$ x,x0}$$Ifr}pbY4 a $$Ifa$ Įɮʮˮ̮ͮЮծ֮׮خٮܮx0x0}$$Ifr}pbY4 a $$Ifa$ ܮx0x4}$$Ifr}pbY4 a $$Ifa$  4xxxxx4xxxxx4 $$Ifa$}$$Ifr}pbY4 a !"#$%(./0x4x8}$$Ifr}pbY4 a $$Ifa$ 0125<=>?@CJKLMx8x8}$$Ifr}pbY4 a $$Ifa$ MNQXYZ[\_fghijx8x8}$$Ifr}pbY4 a $$Ifa$ jmtuvwx{x<x<}$$Ifr}pbY4 a $$Ifa$ x<x<}$$Ifr}pbY4 a $$Ifa$ <xxxxx $$Ifa$}$$Ifr}pbY4 aï̯ͯЯ4xx14xG$$If0- Y4 a $$Ifa$}$$Ifr}pbY4 aЯٯگݯ!+,4488888G$$If0- Y4 a $$Ifa$,/9:=HILWX[fgjuvy<<<<<@G$$If0- Y4 a $$Ifa$İŰȰ԰հذ@@@@@@@ $$Ifa$G$$If0- Y4 a$%(458DEHTUXde@@@@@@@G$$If0- Y4 a $$Ifa$ehtuxıűȱԱ@@@@@@G$$If0- Y4 a $$Ifa$ԱձرkBCTyz@$If $$Ifa$G$$If0- Y4 a 1h/ =!"#$%`!'y9`Giҥ6coQBT';xŜ UU>aa3j#~HpB?!_4L13,&FMŔQ^MI))#AJ2d3ébJ2_J)y`<1RJHS-)⤌rHbRBJI R⤘RRF8)Ό0;yBUWg䁆I))#AwB1%eCBRJH'Ť22bgB1L=%3߱6h1 .䒨65kV=3QSSSyh֭ѫ޽{G{{j\Y%0[ E̦Zm%(v[oor[-uߧ!qc(}3UR -;5_npt;t$+̓zupN2)~v,W5宇W?ϛ;{bI+_xI 5vK1_O;w?T꘱?v49>:w)=v(Tٸdz,\>Z[hJvgZ eqciW9ƙVqU|1δO:ƙV=pci v3qciU/8ƙVnv3_v3>WL1δzp3[q;1δL}8j|gZəVAci:ƙV۠cip3@?8j3gZmqs01δ;ƙV)g渲ZQ['9ƙVkd8ӪNs33L5pci8ƙVqUs3VEqr1δZ 9ƙVq"1δZW;ƙVaci59ƙV \gZ5t38j.u3qlht3f]q 01δqci59ƙVci5V9f|$w'p oԹm nax+ώY6L>ܟ߹El.9 L:213 NkT _xB g/9k! 6 >gwA%tfjbe g|\s6l-ALU%k@m-=J0UA 䌏}Q*:Z hl_ g|s[胿Scc@1`lG= =O`6f|ASXS= 0U=6rgv>gy0U043>9{lSU1 r}60UF ϵ}^sm`"|!3>9{>WT!n@xv6_9{Tٸ/3s[M 䌯%_o۸'3s[{aU1aL^9ks>g봽0Uob㌯uנ3]v83NsViih^ٸ=3ZsAw4UArl}zҞRNApg|:W[9>g踧?t&qW}Ύhgl_9h6ӹF;Q9B%0g9>gyT=Onals( yrx|ΪD4U)Tٸ.3sv Mzn@~ _FSFu9; 3TSm|,3sv&TNqM g|\ _AS8e@>\磩Zٸ*3suloZ _)3's6W7T l\ߙ9x4UMp9>gRMmrw}.apr ]h6. 䌟X9Uh۸ 3~njZl'3~zl*΃Z4U56 䌟!9 M|I g$u3T̓?Os3lT%S9z|fb=FS7X?[sv nESlE g 8'3~ Ά_ qv g 9`@37x܃j6i oާop܇j&̳qF g@)@78BSUm?}ka%Ak9'"OTxMtXn@ M7x FSU M6^s؝?/>0Wt܎~GҶ<$\m߯_G $ +?VB/FO.&ꇓ/0ZA_cI9铜C:L L{)-oxP?CzC _&^Uȍ=U'bcG4va~Ъ.;젱 ?hc ]>o?M[z~pMIo?0t_9׹߆Gj_ {Vu3ZFε?٪3׶?lD?Ugkv#[}Rݪ?Ͷ?v.N)\[f跂v; 'w]V}|'1a$<[џ&Uм+x=z^}5D Go`Z.oZ-\rǭtahK\Yy[DW秼{^Zyyɽg#kU~>fzv3~_w; y֣ULSOlb'K>لOKhx^)snim' S&NvstQv<8ዢ`آ HO"ŌOgqp$BMN1LLJ%} V7`DdhP  S A? "2zHI1 "jEV}`!NHI1 "jE.@x |xcdd``gd``beV dX,XĐ Ɂ A?d-vg@P5< %! `fjvF+B2sSRs@.si#l Fp>3o 5Q?&2n}, Mp>#dL2@penR~̅.[ R $%υp k.p|zv0o8+KRs!Fv=3X0Q@DdhP  S A? "2<MT:LMg `!MT:LMg d@H|xڅPQ=36HDQHЩ>P,' V'*^;M&wf9'\BpNUؓ*2vKbcnTM)ExH̕Q$2_;J%BKRaO'F@Oq F.p \7Ȃ{B*LRB}XN7uj I#YssclcG( 7CDdhP  S A? "2=mwtF3Re{`!mwtF3Red@H|xڅPQ=3$66 AM(#+~jЩzkXZ7ܙ眜s :`T`OFaۥH7ݴS.W>_,]#[B ƒ|( .UH0E fd:xo.d? vhΖ:i{^{Yp;Q__@SMBh'{t\m~~̺hR{$7DdhP  S A? "2lb^7IRH\`!@b^7IR@@8 |xcdd``fgd``beV dX,XĐ ɁɁMRcgb xl πjx|K2B* R. `W01d++&10|D(-YA|}fjbMd<0I9 L0A3]"R ï$ъ' \{Zv0o8+KRs!Dv-3XkLDdhP  S A? "2] i`FWxq9l `!1 i`FWxq@@|xcdd`` @bD"L1JE `xX,56~) M @ kԈg@P5< %! `fjvF+B2sSRsD(-AM&('F>Mzdv5[P 27)? ~FKbF]hғ +.pxu;LLJ%W!GuDd<J  C A? "2A(Ljh);zm `!A(Ljh);z` yxڍR;KP/Р8.bGQt]++Xw\DAu'cK:''"aJAHa*T' tA!*"!c+Эn`MMO[&AOzB.[ %:y~E{*:toB:Z:HȽC ċofgfgi v(FB2_D"PQ ѬmȲO>U-   !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ Root EntryO Fѧ[Data $WordDocumentNVObjectPoolQ @dѧ_1037259799F@d@dOle CompObjfObjInfo #&).36789:;<=>?@BCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz|}~ FMicrosoft Equation 3.0 DS Equation Equation.39q`ĀII a n =a n"1 +a n"2 FMicrosoft Equation 3.0 DS EqEquation Native |_1037260970 F@d@dOle CompObj fuation Equation.39q@mIȃI a 3 =3q 0 +2 FMicrosoft Equation 3.0 DS Equation Equation.39qObjInfo Equation Native  \_1037260908F@d@dOle  CompObj fObjInfoEquation Native 8_1037260933F`Ol`OlI`uI a 3 FMicrosoft Equation 3.0 DS Equation Equation.39qI@I q 0C FMicrosoft Equation 3.0 DS EqOle CompObjfObjInfoEquation Native 8_1037260993F`Ol`OlOle CompObjfObjInfouation Equation.39q,InI a 3 =3+2 FMicrosoft Equation 3.0 DS Equation Equation.39qEquation Native H_1037261033'F`Ol`OlOle CompObj fObjInfo!Equation Native  @_1037385070$F wu wuOle !$  3 2 +4 2 =5.CompObj#%"fObjInfo&$Equation Native %a_1037396874",)F wu wuOle 'CompObj(*(fObjInfo+*Equation Native +) FMicrosoft Equation 3.0 DS Equation Equation.39qD | " FMicrosoft Equation 3.0 DS Equation Equation.39q_10373971241.F@}@}Ole ,CompObj-/-fObjInfo0/Equation Native 0)_10374308723 F@@Ole 1CompObj252bD | " FMicrosoft Excel ChartBiff8Excel.Sheet.89q²0* pHd VBAProject4@j = r 9 J< rstdole>stdole f%\*\G{00020430-C 0046}#2.0#0#C:\WINNT\System32\StdOleObjInfo4Workbook4LK_VBA_PROJECT_CUR"E@@VBA;@@ Ba= ThisWorkbook =t"8X1Arial1Arial1Arial1Arial1rArial16Arial16Arial16Arial1rArial16Arial16Arial16Arial"$"#,##0_);\("$"#,##0\)!"$"#,##0_);[Red]\("$"#,##0\)""$"#,##0.00_);\("$"#,##0.00\)'""$"#,##0.00_);[Red]\("$"#,##0.00\)7*2_("$"* #,##0_);_("$"* \(#,##0\);_("$"* "-"_);_(@_).))_(* #,##0_);_(* \(#,##0\);_(* "-"_);_(@_)?,:_("$"* #,##0.00_);_("$"* \(#,##0.00\);_("$"* "-"??_);_(@_)6+1_(* #,##0.00_);_(* \(#,##0.00\);_(* "-"??_);_(@_)                + ) , *   Chart1"Sheet1)(Sheet2S@Sheet3# remainder;ZR3  @@  ]#"abINT(a/b) remainderGCD=count= If(match) =' DimRange Macro$' Macro written 8/31/95 by Dan Clark'Sub DimRange() Sheets("Ranking").Select cnt = 2 For I = 0 To 35" CheckPrevSeg = Cells(cnt, "v")0 If CheckPrevSeg = "0" Then GoTo stopcounting cnt = cnt + 1 Next I 'ncnt = cnt + 1 'For n = 0 To 35+ 'CheckNotPrevSeg = Cells(ncnt, "v")8 'If CheckNotPrevSeg = "0" Then GoTo stopcounting 'ncnt = ncnt + 1 'Next n stopcounting:7 Set PrevSeg = Range(Cells(2, "A"), Cells(cnt, "U"))> 'Set NotPrevSeg = Range(Cells(cnt, "A"), Cells(ncnt, "U")) 'Sheets("RANKING").Select2 'Range("A5:D6,A10:D11,A15:D16,A19:D20").Select* 'Range("PrevSeg", "NotPrevSeg").Select Range("PrevSeg").Select End Sub"v h\3h_ Plereap Fw$ĕ BdȊ$0DXXL[XX0+5e(Н0JXXNLwwTmw#e(wazp0::35eC0w0w!!LwS04t00}%@%?ۗB?vALB@: R:BAXDCBB_ZpBC@BD0=BEژ&Be> Eژ   dMbP?_*+%"??UT0      wG0000{ a bINT(a/b) remainder /@%B@ @@$?DDA(@DDD GCD=%@D@D@D$?DDA(@DDD @ D@D$?DDA(?DDD If(match) =?@)%B@ B@D?D$@DDA(DDD ?DD$DDA(DDDcount=#@ %BDD$DDA( DDD   D  D$  D D A(  D D D  ^ HDDD  $)DDD  $"B   D   D $  D D A(  D D D    D  IO D $  D D A(  D D D   IO D   D $  D D A(  D D D    D  UW< D $  D D A( D D D  UW<D 4aD $DDA(DDD 4aD}lD$DDA(DDD (DDD(DDD(DDD(DDD(DDD(DDD(DDD(DDD(DDD(DDD(DDD(DDD8 ,,,,,,,,,,,>@ Sheet1   dMbP?_*+%"??UFT0     GwGw{T0TT0T~ ?~ ?~ @!@ DD!@ DD! @ DD!*@ DD!5@ DD!A@ DD! K@ DD! @V@ D D! b@ D D !  m@ D D ! w@ D D !@ D D !؎@ DD !@ DD!0@ DD!U@ DD!m@ DD!a@ DD!K@ DD!@@ DD!@ DD!Q@ DD!@ DD!A DD!eA DD!bA DD!Pd)A DD!݊4A DD!@A DDDl%%%%%%%%%%%%%%%%%%%%%%%%%%%% T0!"#$%&'()*+,-./0G123w45G6w7{8T09:;T<T=0T>?! JA! DD!!9UA" D D!" aA# D!D !#6zlA$ D"D!!$ wA% D#D"!%HA& D$D#!&u(A' D%D$!',eA( D&D%!(A) D'D&!)pA* D(D'!*ֹA+ D)D(!+RA, D*D)!,OA- D+D*!-W\A. D,D+!. $#A/ D-D,!/A0 D.D-!0bA1 D/D.!1˙qB2 D0D/!2eB3 D1D0!32B4 D2D1!4(B5 D3D2!5H4B6 D4D3!6V[?@B7 D5D4!7zJJB8 D6D5!8hiEUB9 D7D6!9m5aB: D8D7!: r"kB; D9D8!;-1ȆvB< D:D9!<HHl9B= D;D:!=|B> D<D;!>ۗB? D=D<!?vALB@ D>D=D l%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@T0ABCDE!@: R:BA D?D>!AXDCBB D@D?!B_ZpBC DAD@!C@BD DBDA!D0=BE DCDB!Eژ&B DDDCVd%%%%%(  p  6NMM?- ]`  "??3`  `  `  `  п03d23 M NM4 FF3QQ ;EQQ3_4E43_43_43_4D $% M 3O&Q4$% M 3O&Q4FAya3OS 3 b+MZ43*?#M! M4%  >vM3O%&Q  Cell number(n)'4% NMZ3O%.&Q  F(n)'4523  NM43" C $@/3OC $% M3OQ4444% QzM03O,&Q &Fibonacci numbers'44Feee >@   Sheet2   dMbP?_*+%M\\EAD-MFSPS\HPLASER4SI0C odXXLetter DINU"0? "dXX??U} 3T0     w{GwG' DimRange Macro-$' Macro written 8/31/95 by Dan Clark ' 'Sub DimRange()% Sheets("Ranking").Select cnt = 2 For I = 0 To 35+" CheckPrevSeg = Cells(cnt, "v")9 0 If CheckPrevSeg = "0" Then GoTo stopcounting  cnt = cnt + 1  Next I  'ncnt = cnt + 1!  'For n = 0 To 354+ 'CheckNotPrevSeg = Cells(ncnt, "v")A8 'If CheckNotPrevSeg = "0" Then GoTo stopcounting! 'ncnt = ncnt + 1 'Next n   stopcounting:@7 Set PrevSeg = Range(Cells(2, "A"), Cells(cnt, "U"))G> 'Set NotPrevSeg = Range(Cells(cnt, "A"), Cells(ncnt, "U"))& 'Sheets("RANKING").Select;2 'Range("A5:D6,A10:D11,A15:D16,A19:D20").Select3* 'Range("PrevSeg", "NotPrevSeg").Select$ Range("PrevSeg").Select  End Sub<d1) /=$%8E%DK*?7(>@ Sheet3 dir5Sheet18:A_Sheet2{Sheet39?2.Tlb#OLE Autom`ation^MSFor ms>SFErms/z pF5CD90E02-D7E3-11D2-B0A8F8362FF9DF3.TWD#Microsoft = ` Ob LibraryG9P0j P3$PTEMP \VBE\&EX&.E .`M ACvOfficDvO@sficBv)*2DF8D04C-5BFA-101B-BDE5SAA@u42Sgram Files\ O\MSO9`7.DLLHX (8.0XB"TZBThisWorkbookN2@1Th@6sWkbokHB1C-C@,BRZ*"B+BSheet12S@e@Pt1PVMPU2H2 2b^ 3 Z3 3 \ $UserAe#2@uerKw$p0OXc0()`#1b<ʄNb FʄNbxsTZPZ#ʄNbʄNb 4P[LSS6"<<<N0{00020820-0000-0000-C000-000000000046}9"*\Rffff*c39dcee9b*\R1*#15dH($ph$$$$$$$i i $8$h$ b`|   fp`@Ih (  $x( $ $xH $ $xh $ $x $ $x@ $ $x  $ $x $ $x $ $x0 $ $xP $ $xx $ $x( $ $x $ $x $ $x $ $x $Ij $$pxpX@0ME 8" X  `,  ( @ " 0 x "0 @X8   HlplD4:D15A@4B@F@pl B@JB@F'Z: Worksheet_SelectionChange(ByVal Target As Excel.Range)Sub0M \e;C Zv$`'dst d0FbgN Z 'Za \n;Cncnt = cnt + 1stFor n = 0 To 25 Z v$`'dlls(ncncnt = ncnt + 1Next n B@J1Looks at the remainder of the Euclidean AlgorithmRemainder = Cells(ncnt, "v"))If Remainder = "0" Then GoTo stopcountingAttribute VB_Name = "She@et1" Bast0{00020820- C$0046} |CreatablFalse PredeclaIdTru "ExposeTemplate`Deriv$eCustomizd 'Looks at the remaind er ofEuclidean Algorithm Sub RRange(D5, D30) .Select cntk5For I0 To 2 '<= Cells(, "v"* If9"0" Then Go"Stopcoun0ting8;+ 1 Next IS'n= A(nM(B)) +a + D#,B.n Endn ^_<(W^U ,F G<5b F5bx6TZ^Z#5b5b4(SLSS6"N0{00020820-0000-0000-C000-000000000046}9"*\Rffff*339db31b7($H0h $ $ $p@8MExAttribute VB_Name = "She@et2" Bast0{00020820- C$0046} |CreatablFalse PredeclaIdTru "ExposeTemplate`Deriv$eCustomizd<5b F5b     ,+!"#$%&'()*-/0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`ax6TZ\Z#5b5b4(SLSS6"N0{00020820-0000-0000-C000-000000000046}9"*\Rffff*439db31b7($H0h $ $ $p@8MExAttribute VB_Name = "She@et3" Bast0{00020820- C$0046} |CreatablFalse PredeclaIdTru "ExposeTemplate`Deriv$eCustomizdK)^rU~~~~~~~~~~~~~T  ʄNb  a  I i ! 9 Q )1__SRP_0__SRP_1<>__SRP_2__SRP_3=A! GreatestCD VBAProject ThisWorkbookSheet1Sheet2Sheet3F=C:\Program Files\Common Files\Microsoft Shared\VBA\VBA332.dllVBA i PF 3C:\Program Files\Microsoft Office\Office\EXCEL8.OLBExcel `0FC:\WINNT\System32\StdOle2.Tlbstdole  p\bC:\WINNT\System32\MSForms.TWDMSForms yY.E .`M \bC:\TEMP\VBE\MSForms.EXD YL-[DR 2C:\Program Files\Microsoft Office\Office\MSO97.DLLOffice 9aF^DYb F]DYbDF WorksheetWorksheet_SelectionChangeFF @F5bF5bDFWorkbookF  UserForm1ʄNbʄNb RemainRange Stopcounting ʄNb ʄNb v 0ʄNbʄNbrU~~~y   1 1iTarget 1Q (D5D30arU 8 9 A4a {?SrU @,` //$)` prU  ) 4Q y __SRP_4 __SRP_5@C@UserForm1ThisWorkbookBDcrU @pD ʄNbʄNbɄNb ʄNbxpTZOX ʄNb ʄNb48<PSPSSS6"<<<0{0A8F470B-C9FA-11D4-B22F-00008362FF9D}{0A8F4700-C9FA-11D4-B22F-00008362FF9D}9"*\Rffff*a39dcee7900($X0 $8$$i 8$L0H`MEhAttribute VB_Name = "UserForm1" " Bas0{0A8F470B-C9FA-11D4-B22F-08362FFh9D}J0J dCreatabli False Pr@edeclaI"dTru "Ex0pose@TemplateDerivCustomizD<5bF5bx6TZRZ#5b5b4(SLSS6"N0{00020819-0000-0000-C000-000000000046}9"*\Rffff*239db31b7( $H0h $333 $2 $p@hh8MExAttribute VB_Name = "ThisWorkbook" Bas0{00020P819-0C$0046} |CreatablFalse ^PredeclaIdTru "@ExposeTemplateD0eriv$eCustomiz2a^  *\G{000204EF-0000-0000-C000-000000000046}#3.0#9#C:\Program Files\Common Files\_VBA_PROJECT-PROJECT7F:pPROJECTwmGDUserForm1I@@      !"#$%&'()*+,-./0123456789;<=>?@ABCEFHIKLNPQRSUVWYZ[\]^_abcdefhijkmMicrosoft Shared\VBA\VBA332.dll#Visual Basic For Applications *\G{00020813-0000-0000-C000-000000000046}#1.2#0#C:\Program Files\Microsoft Office\Office\EXCEL8.OLB#Microsoft Excel 8.0 Object Library*\G{00020430-0000-0000-C000-000000000046}#2.0#0#C:\WINNT\System32\StdOle2.Tlb#OLE Automation*\G{5CD90E02-D7E3-11D2-B0A8-00008362FF9D}#2.0#0#C:\WINNT\System32\MSForms.TWD#Microsoft Forms 2.0 Object Library*\G{5CD90E03-D7E3-11D2-B0A8-00008362FF9D}#2.0#0#C:\TEMP\VBE\MSForms.EXD#Microsoft Forms 2.0 Object Library.E .`M *\G{2DF8D04C-5BFA-101B-BDE5-00AA0044DE52}#2.0#0#C:\Program Files\Microsoft Office\Office\MSO97.DLL#Microsoft Office 8.0 Object Library9TZThisWorkbook 239db31b7*DRZ Sheet1 c39dcee9b*DPZ Sheet2 339db31b7*D^Z0 Sheet3 439db31b7*D\ZHUserForm1 a39dcee79*DMOXhhH0VDYbXDYbZDYb\DYb5bH:;, Excel+ VBAWin16~Win32Mac GreatestCDu stdole`MSFormsC VBAProject Officeu ThisWorkbook| _Evaluate Sheet1 Sheet2 Sheet3 WorksheetRange Worksheet_SelectionChange4TargetFOffsetSelectionChangen _B_var_OffsetR%WorkbookkMatchRCountD4D154Count0vD4\ _B_var_Count: ActiveCell rowOffset& columnOffsetʚrowOffset: =(count(d4:d15)-13rcolumnOffset:=0rowOffset: =-1JActivate|ActiveS _B_var_Active UserForm1)UserFormNTextBox1SUserForm_ClickImage1_DimRangee|Sheets cnt+I` CheckPrevSeg7|Cells StopcountingET Remainder^ RemainRangekD5\D30y _B_var_cnt<<_B_var_I _Defaultj_B_var_Remainderg _B_var_EndFM ZID="{C444ED63-9959-11D4-B204-00008362FF9D}" Document=ThisWorkbook/&H00000000 Document=Sheet1/&H00000000 Document=Sheet2/&H00000000 Document=Sheet3/&H00000000 Package={AC9F2F90-E877-11CE-9F68-00AA00574A4F} BaseClass=UserForm1 Name="VBAProject" HelpContextID="0" CMG="1715BCD7C4F9DFFDDFFDDFFDDFFD" DPB="2E2C85C08BC0A3C1A3C1A3" GC="4547EEE512FD13FD1302" [Host Extender Info] &H00000001={3832D640-CF90-11CF-8E43-00A0C911005A};VBE;&H00000000 [Workspace] ThisWorkbook=44, 44, 492, 410, Sheet1=22, 22, 470, 388, Z Sheet2=0, 0, 0, 0, C Sheet3=0, 0, 0, 0, C UserForm1=66, 66, 514, 432, C, 44, 44, 492, 410, ThisWorkbookThisWorkbookSheet1Sheet1Sheet2Sheet2Sheet3Sheet3UserForm1UserForm1  }t 9T$fGoHJJCompObjKMaVBFrameO#TextBox1$ Image1x1"; d@H,J INTEGER A: INTEGER B: 9D5Tahoma 'q Microsoft Forms 2.0 FormEmbedded Object9qVERSION 5.00 Begin {C62A69F0-16DC-11CE-9E98-00AA00574A4F} UserForm1 Caption = "UserForm1" ClientHeight = 3225 ClientLeft = 45 ClientTop = 330 ClientWidth = 4710 StartUpPosition = 1 'CenterOwner TypeInfoVer = 2 End Oh+'08@Th  SWENDSEK  SWENDSEK Microsoft Excel@W>#,SummaryInformation(6MTDocumentSummaryInformation8X1Table.fSummaryInformation(P`՜.+,D՜.+,L PXp x  MDEQ-EAD-MFSWoj Sheet1Sheet2Sheet3Chart1  WorksheetsCharts 6> _PID_GUIDAN{38309C71-9877-11D4-B203-00008362FF9D}gA-e!$3Mj #٩'_j;Rk f;֞u|_0aMSRL)X%0Q'_?.ڝ;1W`ͬ d% ILo-DdJ   C A ? "23T O4Bkw4K`!T O4Bkw4KD``!!xMN Aa=3rBveu=J,t=='{o\25͙32@FJ2_D1"HQmqTTu(!4xҟt79tI/\d.~I1 S`=`Ú\RL.,XŨү iNꝘ+A\fVۑi}$7o-(DdJ   C A ? " 23T O4Bkw4K`!T O4Bkw4KD``!!xMN Aa=3rBveu=J,t=='{o\25͙32@FJ2_D1"HQmqTTu(!4xҟt79tI/\d.~I1 S`=`Ú\RL.,XŨү iNꝘ+A\fVۑi}$7o-(Dd!0  # A2'y9`Giҥ6com `!'y9`Giҥ6coQBT';xŜ UU>aa3j#~HpB?!_4L13,&FMŔQ^MI))#AJ2d3ébJ2_J)y`<1RJHS-)⤌rHbRBJI R⤘RRF8)Ό0;yBUWg䁆I))#AwB1%eCBRJH'Ť22bgB1L=%3߱6h1 .䒨65kV=3QSSSyh֭ѫ޽{G{{j\Y%0[ E̦Zm%(v[oor[-uߧ!qc(}3UR -;5_npt;t$+̓zupN2)~v,W5宇W?ϛ;{bI+_xI 5vK1_O;w?T꘱?v49>:w)=v(Tٸdz,\>Z[hJvgZ eqciW9ƙVqU|1δO:ƙV=pci v3qciU/8ƙVnv3_v3>WL1δzp3[q;1δL}8j|gZəVAci:ƙV۠cip3@?8j3gZmqs01δ;ƙV)g渲ZQ['9ƙVkd8ӪNs33L5pci8ƙVqUs3VEqr1δZ 9ƙVq"1δZW;ƙVaci59ƙV \gZ5t38j.u3qlht3f]q 01δqci59ƙVci5V9f|$w'p oԹm nax+ώY6L>ܟ߹El.9 L:213 NkT _xB g/9k! 6 >gwA%tfjbe g|\s6l-ALU%k@m-=J0UA 䌏}Q*:Z hl_ g|s[胿Scc@1`lG= =O`6f|ASXS= 0U=6rgv>gy0U043>9{lSU1 r}60UF ϵ}^sm`"|!3>9{>WT!n@xv6_9{Tٸ/3s[M 䌯%_o۸'3s[{aU1aL^9ks>g봽0Uob㌯uנ3]v83NsViih^ٸ=3ZsAw4UArl}zҞRNApg|:W[9>g踧?t&qW}Ύhgl_9h6ӹF;Q9B%0g9>gyT=Onals( yrx|ΪD4U)Tٸ.3sv Mzn@~ _FSFu9; 3TSm|,3sv&TNqM g|\ _AS8e@>\磩Zٸ*3suloZ _)3's6W7T l\ߙ9x4UMp9>gRMmrw}.apr ]h6. 䌟X9Uh۸ 3~njZl'3~zl*΃Z4U56 䌟!9 M|I g$u3T̓?Os3lT%S9z|fb=FS7X?[sv nESlE g 8'3~ Ά_ qv g 9`@37x܃j6i oާop܇j&̳qF g@)@78BSUm?}ka%Ak9'"OTxMtXn@ M7x FSU M6^s؝?/>0Wt܎~GҶ<$\m߯_G $ +?VB/FO.&ꇓ/0ZA_cI9铜C:L L{)-oxP?CzC _&^Uȍ=U'bcG4va~Ъ.;젱 ?hc ]>o?M[z~pMIo?0t_9׹߆Gj_ {Vu3ZFε?٪3׶?lD?Ugkv#[}Rݪ?Ͷ?v.N)\[f跂v; 'w]V}|'1a$<[џ&Uм+x=z^}5D Go`Z.oZ-\rǭtahK\Yy[DW秼{^Zyyɽg#kU~>fzv3~_w; y֣ULSOlb'K>لOKhx^)snim' S&Nvs>??@z@@AhAvAAA/BqBBBBBrEsEFFGGGHH1H2HGHKUVYcdgqruɐʐِ͐ؐܐ (),89<HILXY\hilxy|ȑɑّܑ̑ؑ (),89:;<=>?@͓Γ00000000000800"0"0"0"0"0"0"0"0"0"0"0"00t0t0t00x0x0x0x0x0x0x0x0x0x000000000000000000000000000000000000000000000000000000000 0 00000000 0 0 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000(000(00000000000000000000000000000000000000000000000800(000000000000000000000000000000000000000000000000000800(00000000@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0000000000@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@000@0@0 0@0@0@0@0 077OOOR )+U<~G`Pem{lqrtuwy{|~x 3*HZ$juѫˬ Yp/7?aj}ܮ0MjЯ,eԱmopsvxz}n      / C E d x z  !!!45 55)5+5555::::::::::-4@GIR! :l,2$'y9`Giҥ6co"F@(  V  C A ?"B S  ?gt!4m6p6U7X788;;DDEEFFHHOOOO[[A_J___eeffffvv4=@444466V7X788;;<<><EE$F&FHHHHfIhIJJJJKKLLLLVMXMMMMMNNNNOO?OAOHOIOOOOO+P1PPP3Q5QoQqQQQRRR SSS2T4TTTeUgUUUVVVV[[\\^^S_U_____n`p`eeeeffuiwij j!k#kzz@33333333333333333333333333333333333333333333333333333333333/358>A !   / F d {  $ t4x444\6`6J7N78888;;N<R<BBCCDD0E4E{EEBFFFiMmMOOVV\V`VVVYY__eeeeeeffffkktttttt?̓דGuestfC:\WINNT\Profiles\guest\Application Data\Microsoft\Word\AutoRecovery save of EntireProject Report2.asdGuestfC:\WINNT\Profiles\guest\Application Data\Microsoft\Word\AutoRecovery save of EntireProject Report2.asdGuestfC:\WINNT\Profiles\guest\Application Data\Microsoft\Word\AutoRecovery save of EntireProject Report2.asdGuestfC:\WINNT\Profiles\guest\Application Data\Microsoft\Word\AutoRecovery save of EntireProject Report2.asdGuestfC:\WINNT\Profiles\guest\Application Data\Microsoft\Word\AutoRecovery save of EntireProject Report2.asdGuestA:\EntireProject Report2.docCurtis BennettKC:\My Documents\Classes\Capstone\Student Reports\Euclid Alg\Euclid Post.docCurtis Bennett<C:\My Documents\Carnegie\Portfolio\Picture 8\Euclid Post.docCurtis Bennett<C:\My Documents\Carnegie\Portfolio\Picture 8\Euclid Post.docCurtis Bennett<C:\My Documents\Carnegie\Portfolio\Picture 8\Euclid Post.doc4 >^oȌ88^8`6o()^`. L ^ `L.  ^ `.xx^x`.HLH^H`L.^`.^`.L^`L.88^8`o()^`. L ^ `L.  ^ `.xx^x`.HLH^H`L.^`.^`.L^`L.4 o,8        (Z         !ABCDEFGazÍčȍʍ͍эӍԍՍ֍ڍ܍'(EFHJKLMNPRSelmoqr|~ŽĎǎȎɎʎˎ͎ЎюҎӎԎ׎ڎێ܎ݎގ  !$)*+,-056789<ABCDEHNOPQRU[\]^_bhijklouvwxy|ȏɏʏˏ̏Ϗ׏؏ُڏۏޏ  !$-.1:;>GHKUVYcdgqruɐʐِ͐ؐܐ (),89<HILXY\hilxy|ȑɑّܑ̑ؑ (),89<=>?@@AA( A8`--78:;<=@ABFGKL|M|NFPFRFSF_F`FaFbFcFdTgTh`@` `@`>`@`D`F`H`J`P`R`@`X`@`^`@`b`@`f`j`@`x`z`|`~``@``@UnknownG:Times New Roman5Symbol3& :ArialQ"Antique Olive (PCL6)7& Verdana;WingdingsE& Britannic Bold"qh5X&5X& 'x=!20d;2QProject ReportCollege of EducationCurtis Bennett