What makes a number prime or composite? These two definitions are surprisingly easy to remember. Continue on for tricks on remembering them and help with math problems.
Primes and Composites
To mathematicians, prime numbers are a subject of great interest and importance. A prime number is simply any integer with exactly two factors, itself and one (meaning it can only be divided by itself and the number one). What is a composite number, then? Simply any number that isn’t prime! More specifically, the definition of composite numbers is those numbers which contain factors other than themselves and one. There is one special case - the number one itself. Because it does not have exactly two factors, it is not prime, and because it does not have any factors other than one it is also not composite.
Prime and composite are terms that are generally applied only to the positive integers. Zero, for example, is neither prime nor composite (although many people fail to realize that it is an even integer). Similarly, although we can get a product of three by multiplying either 3 and 1 or -3 and -1, three is still a prime number.
The Fundamental Theorem of Arithmetic says that every whole number greater than one can be written uniquely as the product of primes, up to ordering; that means that for any positive integer, we can write it either as itself (if it is prime) or as the product of a set of primes (if it is composite), and if the order of the factors doesn’t matter (which, according to the commutative law of multiplication, it does not), then there is only one such set of prime factors.
Deciding If a Number is Prime
As prime numbers have a number of applications (and because the ancient Greeks thought they were interesting), a great deal of work has gone into finding methods to determine whether a number is prime or composite.
The simplest such method is known as the Sieve of Eratosthenes, Eratosthenes being one of those ancient Greek mathematicians. Rather than checking to see if one particular number is prime, it simply finds all prime numbers up to a particular value.
The algorithm works as follows: first write down all the integers from two up to the largest number you’d like to check. Circle two: it is a prime number. Then go through the list and cross out every other number starting with four; because these are all multiples of two, they are all composite numbers. Circle the next number that is not crossed out; this is three, which is also prime. Now cross out every third number that isn’t already crossed out. Six is crossed out, so we’ll cross out nine, then twelve is crossed out so we cross out 15, and so on. Now go to the next number that isn’t crossed out (five), circle it, and start crossing out every fifth number. Once you’ve passed the square root of the number you’re interested in without crossing it out, you know that your number is prime.
This works because when you get to a number, you’ve already checked it against all prime numbers smaller than it, so nothing divides it; if it was divisible by a composite number, it would also be divisible by a prime. Every number that gets crossed out is a multiple of a prime and is thus composite.
This method is reasonably efficient for finding small primes. For checking whether large numbers are primes, advanced mathematical techniques are available. Additionally, there are ongoing searches to find the largest prime numbers that meet certain additional properties. For example, a Mersenne prime is a prime number of the form 2n-1; the largest known such prime so far is 243112609-1, which is a number much, much too large to actually type out; it contains nearly thirteen million digits!
Practical Use
Today, prime and nearly-prime numbers (that is, composite numbers with only two prime factors) are primarily used for cryptographic purposes. While there are now efficient methods for determining whether or not a number is prime, there is no known way to easy factor numbers that are the product of two large primes.
Extra Credit:
Can you tell which of the following numbers are prime or composite? Hint: exactly four of them are composite.
7 11 19 21 25 27 32 37
