What is the Greatest Common Factor or GCF of 15, 22 and 91?

The Greatest Common Factor (GCF), Highest Common Factor (HCF) or Greatest Common Divisor (GCD) of 15, 22 and 91 is 1.

We can calculate the Greatest Common Factor or GCF in multiple simple and easy ways:

• Using prime factorization method
• Using list of factors method
• Using Euclidean algorithm
• Using Binary GCD algorithm

Let us look at each of these methods, and calculate the GCF of 15, 22 and 91.

Prime Factorization Method To Calculate GCF of 15, 22 and 91

This is the most simple method, and also the most effective. All we need to do here is find the common prime factors for 15, 22 and 91, and then multiply them.

Step 1: Let's create a list of all the prime factors of 15, 22 and 91:

Prime factors of 15:

As you can see below, the prime factors of 15 are 3, 5.

Let's illustrate the prime factorization of 15 in exponential form:

$15 = 3^1 * 5^1$

Prime factors of 22:

As you can see below, the prime factors of 22 are 2, 11.

Let's illustrate the prime factorization of 22 in exponential form:

$22 = 2^1 * 11^1$

Prime factors of 91:

As you can see below, the prime factors of 91 are 7, 13.

Let's illustrate the prime factorization of 91 in exponential form:

$91 = 7^1 * 13^1$

Step 2: Write down a list of all the common prime factors of 15, 22 and 91:

Identifying the common prime factors from our computations above, we can see that the common prime factors of 15, 22 and 91 are none.

So, common prime factors would be $none$

Step 3: All we have to do now is to multiply these common prime factors:

Find the product of all common prime factors by multiplying them:

$GCF(15, 22, 91) = 1$

That's it! We have found the Greatest Common Factor of 15, 22 and 91 using the prime factorization method.

According to our calculations above, the GCF of 15, 22 and 91 is 1.

Method 2 - List of Factors

With this simple method, we'll need to find all the factors of 15 and 22 and 91, and then identify the common factors.

The greatest common factor (GCF) is the largest of these common factors.

Remember, factors are numbers that divide another number without a remainder.

The steps are simple:

Step 1: Create a list of all the numbers that divide 15 and 22 and 91 without a remainder:

List of factors that divide 15 without a remainder are:

"1", "3", "5" and "15"

List of factors that divide 22 without a remainder are:

"1", "2", "11" and "22"

List of factors that divide 91 without a remainder are:

"1", "7", "13" and "91"

Step 2: Identify the largest common number from the 2 lists above:

As you can see in the lists of factors from above, for the numbers 15, 22 and 91, the common factors have been highlighted for clarity.

According to our calculations above, the Greatest Common Factor (GCF) of 15, 22 and 91 is 1.

Method 3 - Euclidean algorithm

The Euclidean algorithm proceeds in a series of steps, with the output of each step used as the input for the next.

The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number.

For example, the GCD of 252 and 105 is exactly the same as the GCD of 147 (= 252 - 105) and 105. Since the larger of the two numbers is reduced, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, they are the GCD of the original two numbers.

By reversing the steps, the GCD can be expressed as a sum of the two original numbers each multiplied by a positive or negative integer, e.g., 21 = 5 × 105 + (−2) × 252. The fact that the GCD can always be expressed in this way is known as Bézout's identity.

To put it in the form of a formula, if $A$ and $B$ are two non-negative integers with $A < B$, and if $R$ is the remainder of the division of $B$ by $A$, then $GCF(A, B) = GCF(A, R)$.

So, can we use the Euclidean algorithm to calculate the GCF of 15, 22 and 91?

The answer is YES.

But, should we use the Euclidean algorithm to calculate the GCF of 15, 22 and 91?

We would strongly recommend against it.

Just because something should be done, doesn't mean it should be done.

That principle applies here. The Euclidean algorithm is not the best method to calculate the GCF of 15, 22 and 91.

The Euclidean algorithm is best suited for calculating the GCF of 2 numbers. For 15, 22 and 91, we have 3 numbers.

So, we advise using the prime factorization method to calculate the GCF here. It is much simpler and easier to understand.

However, if you are interested in learning more about the Euclidean algorithm, you can look at one of the examples below:

• GCF of 10 and 6
• GCF of 33 and 48
• GCF of 51 and 59
• GCF of 63 and 24
• GCF of 85 and 100;

Method 4 - Binary GCD algorithm

The Binary GCD algorithm is an algorithm that computes the greatest common divisor of two nonnegative integers $A$ and $B$.

The algorithm reduces the problem of finding the GCD of two nonnegative integers by repeatedly applying the identity $GCF(A, B) = GCF(A, B - A)$ if $B > A$ and $GCF(A, B) = GCF(A - B, B)$ if $A > B$.

This is a relatively efficient algorithm for large numbers, even though it involves several divisions, so we don't recommend using it for small numbers.