Prime Numbers and Prime Factorizations
In Math . . .
A number is a prime number if it has no factors except one and itself.
In English . . .
A prime number is one that no other number goes into evenly. For example, 12 isn't a prime number because 12 / 3 = 4. On the other hand, 7 is a prime number because the only numbers that divide seven evenly are 7 and 1.
Quick Tip - Which One Did You Find?
Prime numbers are exceptionally usefull - most of modern cryptography is based on them. Unfortunately, they're also very mysterious. For example, no one has every been able to figure out a pattern to how they occur. This makes finding prime numbers exceptionally difficult. The easiest way to do it is just to divide a number by every number smaller than it and see if anything goes into it evenly. Unfortunately, for exceptionally large numbers, i.e. ones with hundreds of digits which are the kind needed to do cryptography, even the most powerful computer would take decades to work through all the required numbers.
So how can you tell if a number is prime or not? For our purposes, the easiest way is just to the number you're given by every number smaller than it. If anything goes into it evenly then the answer is no. If nothing goes into it evenly then the answer is yes.
To make things easier as we go along, here's a list of the prime numbers less than 100.
Don't take my word for that list. Try to divide those numbers by any other number (except one and the number itself) and you'll see that the result has a decimal part.
One of the most important tasks, you'll need to do with prime numbers is writing out the "prime factorization" of a number.
In Math . . .
The prime factorization of a number is the number written as a product of prime numbers.
In English . . .
What we want to do here is rewrite the original number as a bunch of prime numbers mutiplied together. For example, 3 · 3 · 5 is the prime factorization of 45 because 3 · 3 · 5 = 45 and 3 and 5 are both prime numbers. On the other hand, 9 · 5 would not be the prime factorization of 45. It's true that 9 · 5 = 45 but this can't be the prime factorization because 9 isn't a prime number.
The procedure for finding the prime factorization of a number goes like this:
- Is the number divisible by 2? If it is then rewrite the number as 2 times a smaller number.
- Is the smaller number divisible by 2? If it is then rewrite the smaller number as 2 times an even smaller number. Repeat this step until you can't divide 2 into the smaller number any more.
- Try to divide the smaller number from step 2 by the next prime number on the list. Repeat steps 1 and 2 with every prime number that's smaller than the original number.
Find the prime factorization of 45.
This is the number that I used in the "In English ..." discussion above. Here's how I went about finding the prime factorization.
Find the prime factorization of 550.
Find the prime factorization of 180.
Write the prime factorization of 14365.
Big numbers may look intimidating but all you have to do is work through the prime numbers just like in the previous examples. (Having a calculator helps with the division.)
Dyanmic Practice - Finding the Prime Factorization