• 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 is , 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
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);


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)