Prime numbers are like atoms that build every integer number. That is, a prime decomposition of a number is unique and then we can use it to find the number’s factors. Today we will explore this idea a bit more.
We will introduce a couple of new terms. First, a common divisor of two numbers is simply a number that both of these numbers can be divided by. Two numbers which have no common divisors (except from 1) are called relatively prime. We can establish if two numbers are relatively prime by looking at their prime factorizations - if they share no common primes, then they cannot share a common divisor!
Out of all the common divisors two numbers have, one must be the largest. This is an important number and is called the Greatest Common Divisor (GCD). You can find it by looking at the prime factorizations of the two numbers. For every prime number appearing in both factorizations, we take the smaller power. Then we multiply all our choices together. If we divide both numbers by their GCD, the resulting numbers will have no common divisors left and so will be relatively prime.
Similar to the notion of a common divisor is the one of common multiple. It is simply a number that is divisible by both numbers. Among the common multiples, one must be the smallest – this is called the Least Common Multiple (LCM). Again, the LCM can be found by looking at the prime factorizations of the two numbers. For every prime number appearing in any of the two factorizations, we take the larger power. Then we multiply all our choices together.