Prime factorization
The prime factorization of an integer is its unique decomposition
into a
product of primes.
For example, the prime factorization of \(12\) is \(3 \times 2 \times 2\) (or \(2 \times 3 \times
2\),
or \(2 \times 2 \times 3\)). The order is not what makes the prime factorization unique.
Rather, the uniqueness of a prime factorization is based on the specific set of primes involved and
how
many times each prime is repeated (multiplicity) in the factorization.
To represent a prime factorization more compactly, consider exponential notation, where \(12\) is
written as \(3^1 \times 2^2.\) Here, each prime factor is raised to a power equal to its
multiplicity.
⚠ A prime is its own prime factorization! Composite numbers will always have more than \(1\) prime
in
their prime factorizations, or a single prime with a multiplicity greater than \(1.\)
Fundamental theorem of arithmetic
This essential theorem states:
Every integer greater than \(1\) has a unique prime factorization that identifies it.
Therefore,
no two integers greater than \(1\) share the same combination and multiplicities of prime factors.
Furthermore, no two integers greater than \(1\) share the same non-decreasing sequence of
prime
factors.
⚠ A "non-decreasing" sequence is one in which each subsequent element is greater than or equal to
the
element that came before it.
The prime factorization of \(12\) can be written in \(3\) different ways, but only one way is
actually
non-decreasing: \(3 \times 2 \times 2.\) According to the theorem, \(12\) is the only integer
greater
than \(1\) with a prime factorization that consists entirely of repeating \(3\) once and \(2\)
twice.
Computing the greatest common divisor
If the prime factorizations of two integers are already known, finding their greatest common divisor
is
pretty easy.
Let's find the greatest common divisor of \(12\) and \(90.\) First, let's write out their prime
factorizations:
$$12 = 3 \times 2 \times 2$$
$$90 = 5 \times 3 \times 3 \times 2$$
Next, convert to exponential notation:
$$12 = 3^1 \times 2^2$$
$$90 = 5^1 \times 3^2 \times 2^1$$
Rewrite so that the prime factorizations appear to share the same set of primes:
$$12 = 5^0 \times 3^1 \times 2^2$$
$$90 = 5^1 \times 3^2 \times 2^1$$
Take the product of all these prime factors, with each prime factor raised to the minimum
power
it has between the prime factorizations.
$$\gcd(12, 90) = 5^0 \times 3^1 \times 2^1 = 1 \times 3 \times 2 = 6$$
⚠ If you like shortcuts, keep reading! Notice that any prime factors that aren't shared between the
prime factorizations cannot affect the calculation of the greatest common divisor. This is because
unshared prime factors must have a minimum power of \(0\) due to one of the prime factorizations not
having them. So, they only contribute a factor of \(1\), which does nothing. Therefore, to calculate
the
greatest common divisor, you really only need to find the product of all the shared prime
factors, with each raised to the minimum power it has between the prime factorizations. In the above
example, you'd just need to calculate \(3^1 \times 2^1 = 6.\) Make sure you understand this shortcut
before using it.
Computing the least common multiple
If the prime factorizations of two integers are already known, finding their least common multiple
is
also pretty easy.
Let's find the least common multiple of \(12\) and \(90.\) First, let's write out their prime
factorizations:
$$12 = 3 \times 2 \times 2$$
$$90 = 5 \times 3 \times 3 \times 2$$
Next, convert to exponential notation:
$$12 = 3^1 \times 2^2$$
$$90 = 5^1 \times 3^2 \times 2^1$$
Rewrite so that the prime factorizations appear to share the same set of primes:
$$12 = 5^0 \times 3^1 \times 2^2$$
$$90 = 5^1 \times 3^2 \times 2^1$$
Take the product of all these prime factors, with each prime factor raised to the maximum
power
it has between the prime factorizations.
$$\text{lcm}(12, 90) = 5^1 \times 3^2 \times 2^2 = 5 \times 9 \times 4 = 180$$
⚠ You cannot use the same shortcut here that's used for greatest common divisors. Unshared prime
factors
do affect the calculation of the least common multiple. If you feel like you might make this
mistake, then just don't use the shortcut.
Determining divisibility
If the prime factorizations of two integers are already known, you can find out whether one divides
the
other.
Let's figure out if \(12\) divides \(90.\) (Since \(12 < 90\), we know \(90\) cannot divide \(12.\))
First, let's write out their prime factorizations: $$12=3 \times 2 \times 2$$ $$90=5 \times 3
\times 3 \times 2$$ Next, convert to exponential notation: $$12=3^1 \times 2^2$$ $$90=5^1 \times
3^2 \times 2^1$$ Rewrite so that the prime factorizations appear to share the same set of
primes: $$12=5^0 \times 3^1 \times 2^2$$ $$90=5^1 \times 3^2 \times 2^1$$ Now, check if the
minimum power of each prime factor always appears in one of the prime factorizations. In this
case, we can see that \(12\) includes the minimum powers of \(5\) and \(3\), but not \(2.\)
Therefore, \(12\) does not divide \(90.\)
Here's another example.
Let's figure out if \(12\) divides \(72.\) (Since \(12 < 72\), we know \(72\) cannot divide
\(12.\)) First, let's write out their prime factorizations: $$12=3 \times 2 \times 2$$
$$72=3 \times 3 \times 2 \times 2 \times 2$$ Next, convert to exponential notation:
$$12=3^1 \times 2^2$$ $$72=3^2 \times 2^3$$ Rewrite so that the prime factorizations
appear to share the same set of primes (in this case, they already did): $$12=3^1 \times
2^2$$ $$72=3^2 \times 2^3$$ Now, check if the minimum power of each prime factor always
appears in one of the prime factorizations. In this case, we can see that \(12\)
includes the minimum powers of \(3\) and \(2\), which are all of the prime factors.
Therefore, \(12\) divides \(72.\)