Number Theory

One of the most important distinctions in number theory is between prime and composite numbers. Prime numbers can only be divided evenly (with nothing left over) by 1 and themselves. Prime numbers include 2, 3, 5, 7, 11, 13, 17, and so on to infinity. The number 1 is not considered a prime. All primes are odd numbers except for 2, because any even number can be divided evenly by 2.

A composite number can be divided, or factored, into two or more prime numbers in addition to 1 and itself. Ten is a composite number because it can be divided by 2, 5, 1, and itself. The numbers 2 and 5 are the prime factors of 10. Any whole number that is not a prime is a composite.

One difference between prime and composite numbers is that it takes relatively little time to determine if a number is prime, but far longer to determine the prime factors of a composite number, especially if the composite is very large (100 digits or more). This discrepancy in computation time is important in developing computer security systems.

Prime numbers do not occur in a predictable way. There are sequences of primes which can be partially described in a formula, but sooner or later the formula breaks down. One formula, invented by Marin Mersenne (1588-1648) is 2^p - 1, where p is a prime number. Although this formula generates many primes, it also misses many primes. Another formula, invented by Leonhard Euler (1707-1783), generates prime numbers regularly for the series of consecutive numbers from 0 to 15 and then stops. The formula is x² + x + 17, in which x is any number from 0 to 15.