/** The Euclid class illustrates Euclid's algorithm for 
 *  the Greatest Common Divisor.  This can be simplified 
 *  using the remainder '%' function.
 */
public class Euclid {
  /**
   * The GCD method recursively calculates the greatest
   * common divisor for two integers using a technique 
   * devised by Euclid.  
   * The implemented rules are as follows:
   * GCD(m,n):
   *   1) if m equals n, then the GCD(m,n) = m = n.
   *   2) if m is greater than n, then GCD(m,n) = GCD(n,m-n).
   *   3) if m is smaller than n, then GCD(m,n) = GCD(n,m).
   * In recursion - we need to first find our termination state.  In
   * this algorithm, ther termination is when m equals n.
   * We can show that we are constantly reducing our terms to either
   * reach a state when m and n = 1, or m and n equal the same value.
   * How would we prove this?
   */
  public static int GCD(int m, int n) { 
    if (m == n) {
      return m;
    } else if (m > n) {
      return GCD(n, m-n);
    } else
      return GCD(n,m);
  }
}