Math 326, March 12 - Greatest Common Divisor

---

The greatest common divisor of two numbers of two numbers isn't too hard to find for small numbers, but it would be nice to have a computer help us with larger numbers.  Remember that the greatest common divisor (GCD) of two numbers is the largest integer which divides evenly into both numbers (leaving no remainder).

We use Euclid's Algorithm to discern the GCD, which is a process reasonably easy to implement in a spreadsheet.  Suppose we are given to numbers, the larger one we name L, the smaller we name S.  Then if we divide S into L we will get something like:
       L = dS + r
where r is the remainder.  Now, whatever the GCD of L and S is, it will divide both L and S, so it should divide r as well.  So we repeat this division, but now using S =L₂ and r=S₂.  Keep repeating until there isn't a remainder, then the last S_n you had is the GCD.

---

Additional Questions

• Pairs of integers for which the GCD is 1 are called relatively prime.  Create a spreadsheet model to find all of the integers less than a given integer n that are relatively prime to n.
• The number of integers that are less than integer n and relatively prime to n is denoted phi(n), the Euler phi function (For example, phi(6)=2, since 1 and 5 are the only integers less than 6 relatively prime to 6). Build a model which outputs the Euler phi function. 
  
• Add a function to your model so that it finds the Least Common Multiple as well.  (LCM(L,S) can be found quickly from L, S, and GCD(L,S).  How?)
  
• Build a model to output a graph of the Euler phi function for n 1 to 200. Data tables will not will properly if they depend on other data tables, so you may need to use the built in Excel function GCD( , ).