What is the Greatest Common Divisor?

This question could also have been asked as What is the Greatest Common Factor?

Greatest Common Divisor and Greatest Common Factor are the same thing.

---

This should not be confused with Least Common Denominator or Least Common Multiple which is something different.

---

---

Given any two whole numbers, their Greatest Common Divisor is the largest whole number that divides evenly into both of them.

Here are some examples:

---

Question: What is the Greatest Common Divisor of 6 and 8?

Answer: 2

---

Question: What is the Greatest Common Divisor of 1 and 12?

Answer: 1

---

Question: What is the Greatest Common Divisor of 30 and 0?

Answer: 30

---

Question: What is the Greatest Common Divisor of 12 and 18?

Answer: 6

---

Question: What is the Greatest Common Divisor of 8 and 9?

Answer: 1

---

---

One method that is commonly used to find the Greatest Common Divisor of two numbers is the Euclidean Algorithm.

---

The Turing Machine EUC uses the Euclidean Algorithm to compute the Greatest Common Divisor of two numbers.