Finding the Greatest Common Factor (GCF) of Non-Zero Integers

[Jason]

In the case of any size number (Prime Factorization Method).

By use of multiples, break down each number into prime powers. Next, look for the lowest prime powers, common to all numbers. Those are then multiplied, unless it comes out singular, to find the GCF.

Negative integers need to have their absolute value taken first, because the procedure uses only positive numbers.

When powers are multiplied to find the lowest power/powers - common to all numbers, you might end up creating bigger powers - only to break them down again. This is because the common lowest power/powers - might be a subset of what's bigger.

example:

\(16 \longrightarrow 4 * 4 \longrightarrow (2 * 2) * (2 * 2) \longrightarrow 2^{1} * 2^{1} * 2^{1} * 2^{1} \longrightarrow 2^{4}\)

\(32 \longrightarrow 4 * 8 \longrightarrow (2 * 2) * (2 * 4) \longrightarrow [(2 * 2) * (2 * (2 * 2) )\longrightarrow 2^{1} * 2^{1} * 2^{1} * 2^{1}* 2^{1}\) \(\longrightarrow 2^{5} \longrightarrow 2^{4} * 2^{1} \)

The lowest prime power/powers - common to all numbers - is

\(2^{4}\)

Regarding the "32" group: 2 to the 4th (which is at the end of the "16" group) is a subset of 2 to the 5th - so I instead of building up at the end, I broke it down again - from 2 to the 5th to 2 to the 4th * 2 to the 1st.

1-a: What is the GCF of 20 and 90?

\(20 \longrightarrow 5 * 4 \longrightarrow 5 * (2 * 2) \longrightarrow 5^{1} * 2^{1} * 2^{1} \longrightarrow 5^{1} * 2^{2} \longrightarrow 5^{1} * 2^{1} * 2^{1} \)

\(90 \longrightarrow 10 * 9 \longrightarrow (5 * 2) * 3 * 3 \longrightarrow 5^{1} * 2^{1} * 3^{1} * 3^{1} \longrightarrow 5^{1} * 2^{1} * 3^{2} \)

The lowest prime power/powers, common to all numbers, are:

\(5^{1}, \,\,2^{1}\)

\(GCF = 5^{1} * 2^{1} = 5 * 2 = 10\)

1-b: What is the GCF of the following 10 and 20?

\(10 \longrightarrow 2 * 5 \longrightarrow 2^{1} * 5^{1}\)

\(20 \longrightarrow 2 * 10 \longrightarrow 2 * (2 * 5) \longrightarrow 2^{1} * 2^{1} * 5^{1}\)
\(\longrightarrow 2^{2} * 5^{1} \longrightarrow 2^{1} * 2^{1} * 5^{1} \)

The lowest prime power/powers, common to all numbers, are:

\(2^{1}, 5^{1}\)

\(GCF = 2^{1} * 5^{1} = 2 * 5 = 10\)