What is the Greatest Common Factor or GCF of 85 and 100?

The Greatest Common Factor (GCF), Highest Common Factor (HCF) or Greatest Common Divisor (GCD) of 85 and 100 is 5.

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 85 and 100.

Prime Factorization Method To Calculate GCF of 85 and 100

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

Step 1: Let's create a list of all the prime factors of 85 and 100:

Prime factors of 85:

As you can see below, the prime factors of 85 are 5, 17.

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

$85 = 5^1 * 17^1$

Prime factors of 100:

As you can see below, the prime factors of 100 are 2, 5.

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

$100 = 2^2 * 5^2$

Step 2: Write down a list of all the common prime factors of 85 and 100:

Identifying the common prime factors from our computations above, we can see that the common prime factors of 85 and 100 are 5 which occurs 1 time(s).

So, common prime factors would be $5$

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(85, 100) = 5^1 = 5 = 5$

That's it! We have found the Greatest Common Factor of 85 and 100 using the prime factorization method.

According to our calculations above, the GCF of 85 and 100 is 5.

Method 2 - List of Factors

With this simple method, we'll need to find all the factors of 85 and 100, 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 85 and 100 without a remainder:

List of factors that divide 85 without a remainder are:

"1", "5", "17" and "85"

List of factors that divide 100 without a remainder are:

"1", "2", "4", "5", "10", "20", "25", "50" and "100"

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 85 and 100, the common factors have been highlighted for clarity.

According to our calculations above, the Greatest Common Factor (GCF) of 85 and 100 is 5.

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)$.

Let us look at the steps involved in calculating the GCF of 85 and 100 using the Euclidean algorithm.

Step 1: Sort the numbers into ascending order:

85, 100

So, in the formula above, $A = 85$ and $B = 100$.

Step 2: Divide the larger number by the smaller number:

$100 / 85 = 1.1764705882352942$

Our remainder from this division is supposed to be $R$. So, $R = 15$

Step 3: Do this as long as necessary. Replace the larger number with the smaller number, and the smaller number with the remainder of the division. Repeat until the remainder is 0.

$GCF(85, 100) = GCF(85, 15)$

Now, $A = 15$ and $B = 85$. Dividing $B$ by $A$, we get: $R = 10$

$GCF(15, 85) = GCF(15, 10)$

Now, $A = 10$ and $B = 15$. Dividing $B$ by $A$, we get: $R = 5$

$GCF(10, 15) = GCF(10, 5)$

Now, $A = 5$ and $B = 10$. Dividing $B$ by $A$, we get: $R = 0$

Since, our remainder is already 0, we can stop here.

So, GCF of 85 and 100 can be represented as:

GCF(85, 100) = GCF(85, 15) = GCF(15, 85) = GCF(15, 10) = GCF(10, 15) = GCF(10, 5) = 5

Therefore, $GCF(85, 100) = 5$

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.