GCD

Abstract

---

• Stands for Greatest Common Divisor, also known as Greatest Common Factor(GCF)
• The largest positive Integer (整数) that is a Factor for both two or more integers
• Basically a product of all the common Prime Number (质数) factor in the given set of integers

One of given integer is 0

The GCD of 0 and another number $a$ is $a$, since 0 divided by any number results in a remainder of 0

GCD is 1

This means there isn’t a single common Prime Number (质数) Factor between the two numbers

Euclidean Algorithm

• The efficient way of finding GCD
• The Euclidean Algorithm states that

$$GCD(a,b)=GCD(b,r)$$

• Given 2 Integer (整数) - $a$ & $b$, where $a\ge b$. With the use of Divisibility Mathematical Model $a=qb+r$, when $r$ is $0$, $b$ is the GCD
• The gcd() function implemented with Recursion, Worst Time Complexity is O(logn)

public static int gcd(int a, int b) {
  if (b == 0) return a;
 
  int r = a%b;
  if (r == 0) return b;
  return gcd(b, r);
}

Proof

Not a very clear proof, just for better understanding

• Euclidean Algorithm Proof Reference
• Let d be the GCD of a and b → d|a and d|b
• And we know a = bq + r, so r = a - bq
• With r = a - bq, we are sure we can factor out a d from a - bq, since d|a and d|bq, since q is an Integer (整数)
• So since d|r, and d|b, we can reduce the range by finding gcd(b, r)

Brute-force Method: List Factors

Write out the Prime Number (质数) of each given Integer (整数) and identify the prime numbers that appears in both. The GCD is the product of the common set of prime numbers