If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

# The fundamental theorem of arithmetic

## Video transcript

imagine we are living in prehistoric times now consider the following how did we keep track of time without a clock all clocks are based on some repetitive pattern which divides the flow of time into equal segments to find these repetitive patterns we look towards the heavens the Sun rising and falling each day is the most obvious however to keep track of longer periods of time we looked for longer cycles for this we look to the moon which seemed to gradually grow and shrink over many days when we count the number of days between full moons we arrive at the number 29 this is the origin of a month however if we try to divide 29 into equal pieces we run into a problem it is impossible the only way to divide 29 into equal pieces is to break it back down into single units 29 is a prime number think of it as unbreakable if a number can be broken down into equal pieces greater than one we call it a composite number now if we are curious we may wonder how many prime numbers are there and how big do they get let's start by dividing all numbers into two categories we list the primes on the left and the composites on the right at first they seem to dance back and forth there is no obvious pattern here so let's use a modern technique to see the big picture the trick is to use a ulam spiral first we list all possible numbers in order in a growing spiral then we color all the prime numbers blue finally we zoom out to see millions of numbers this is the pattern of primes which goes on and on forever incredibly the entire structure of this pattern is still unsolved today we are onto something so let's fast forward to around 300 BC in ancient Greece a philosopher known as Euclid of Alexandria understood that all numbers could be split into these two distinct categories he began by realizing that any number can be divided down over and over until you reach a group of smallest equal numbers and by definition these smallest numbers are always prime so he knew that all numbers are somehow built out of smaller primes to be clear imagine the universe of all numbers and ignore the primes now pick any composite number and break it down and you are always left with prime numbers so Euclid knew that every number could be expressed using a group of smaller primes think of these as building blocks no matter what number you choose it can always be built with an addition of smaller Prime's this is the root of his discovery known as the fundamental theorem of arithmetic as follows take any number say 30 and find all the prime numbers it divides into equally this we know as factorization this will give us the prime factors in this case 2 3 & 5 are the prime factors of 30 Euclid realize that you could then multiply these prime factors a specific number of times to build the original number in this case you simply multiply each factor wants to build 32 times 3 times 5 is the prime factorization of 30 think of it as a special key or combination there is no other way to build 30 using some other groups of prime numbers multiplied together so every possible number has a one and only 1 prime factorization a good analogy is to imagine each number as a different lock the unique key for each lock would be its prime factorization no 2 lakh share a key no two numbers share a prime factorization