Greatest common factor calculator

This greatest common factor calculator determines the greatest common factor for a set of positive integers. It also breaks down each entered number into its prime factors (the prime numbers that multiply together to give the original number) and breaks down the calculated GCF into its prime factors, showing how the GCF can also be factored into primes.

Related calculators:

Greatest common factor

The greatest common factor (GCF) (also called the greatest common divisor, GCD) is the largest number that divides two or more numbers without leaving a remainder. In simpler terms, it’s the biggest number that can evenly divide all the given numbers.

Prime factorization method for finding the GCF

This method involves finding the prime factors of each number and then determining the largest set of common prime factors between them.

Here’s a step-by-step explanation:

1. Prime factorization:

Break down each number into its prime factors. Prime factors are the prime numbers that multiply together to give the original number. For example:

• Prime factorization of 12 = 2^2 \times 3
• Prime factorization of 18 = 2 \times 3^2

2. Identify common prime factors:

Find the prime factors that are common to both numbers.

• Common prime factors of 12 and 18 = 2 \times 3

3. Multiply the common factors:

Multiply the lowest powers of all the common prime factors. In the example:

• GCF = 2^1 \times 3^1 = 6

Thus, the GCF of 12 and 18 is 6.

Example:

Let’s find the GCF of 24 and 36 using prime factorization:

1. Prime factorization of 24 = 2^3 \times 3
2. Prime factorization of 36 = 2^2 \times 3^2

Common prime factors = 2^2 \times 3^1

GCF = 2^2 \times 3 = 12

So, the GCF of 24 and 36 is 12.

Other methods to find the GCF

1. Division method (Euclidean algorithm):

This method involves repeatedly dividing the larger number by the smaller number and replacing the larger number with the remainder. You continue this process until the remainder is 0. The last non-zero remainder is the GCF.

Steps:

1. Divide the larger number by the smaller number.
2. Find the remainder.
3. Replace the larger number with the smaller number and the smaller number with the remainder.
4. Repeat the division process until the remainder is 0.
5. The last non-zero remainder is the GCF.

Example:

Let’s find the GCF of 56 and 98 using the Division Method.

Step 1: Start by dividing 98 by 56. The remainder is 42.

98 \div 56 = 1 \, \text{(quotient)} \, \text{and remainder} = 98 - 56 = 42

Step 2: Replace 98 with 56, and 56 with 42. Now continue by dividing 56 by 42 and we get 14 as the remainder.

56 \div 42 = 1 \, \text{(quotient)} \, \text{and remainder} = 56 - 42 = 14

Step 3: Replace 56 with 42, and 42 with 14. Now divide 42 by 14 and the remainder is now 0.

42 \div 14 = 3 \, \text{(quotient)} \, \text{and remainder} = 0

Step 4: Since the remainder is now 0, the last non-zero remainder is 14.

Thus, the GCF of 56 and 98 is 14.

2. Listing factors method:

Another simple method is to list the factors of each number and then find the largest factor that they have in common.

Example:

Find the GCF of 20 and 30.

1. Factors of 20: (1, 2, 4, 5, 10, 20)
2. Factors of 30: (1, 2, 3, 5, 6, 10, 15, 30)

Common factors: (1, 2, 5, 10)

The GCF is 10.

Summary:

• Prime factorization method: Uses prime factors of numbers.
• Division method (Euclidean algorithm): Uses repeated division.
• Listing factors method: Involves listing factors of the numbers and choosing the greatest common one.

Each method has its own advantages, but the Euclidean algorithm is generally the fastest for large numbers.