A Brief Introduction to Prime Numbers


Home / A Brief Introduction to Prime Numbers

Selection of Prime Numbers – Image by Decoded Science

Would you like a simple introduction to primes? This article introduces a series about prime numbers by answering the following basic questions: What are prime numbers? Are primes important? How many prime numbers are there?

What is a Prime Number?

Prime numbers are those Natural numbers that are greater than one and can only be evenly divided by the numbers one and itself. As a set, P={all ‘i’ in N such that “i>1” and, for ‘j’ in N, where “i/j” is in N only if ‘j’ equals either one or ‘i’}.

The set of prime numbers begins as {2, 3, 5, 7, 11, 13, 17…}.

What are Non-Prime Numbers Called?

Non-prime numbers greater than 2 are called “composite” numbers. These are positive integers that are “composed of” the product of primes. The set of composite numbers begins as {4, 6, 8, 9, 10…}.

Why are Zero and One Commonly Excluded From Lists of Prime Numbers?

Zero: Since zero divided by anything is still zero, with no remainder, one could say that zero is not a prime number. Zero may be excluded from lists of prime numbers because no-one ever found an acceptable reason to include it in a discussion of primes.

One: The number one is not a composite number, so why is it excluded? This controversy raged in the 20th century; at least, there were disagreements. One can say, “There is no Natural number other than 1 and itself that can divide 1 evenly; therefore 1 is a prime number.” Several mathematicians did indeed consider ‘1’ to be the first Prime number.

However, the number ‘1’ requires exceptional handling in a variety of “primal” situations. The first example is the “fundamental theorem of arithmetic.” There seems to be consensus that the number one is simply defined as “neither prime nor composite.”

What is the “Fundamental Theorem of Arithmetic?”

The Fundamental Theorem of Arithmetic states that any Natural number that is greater than one is the product of a unique set of prime numbers. The sequence of numbers can be rearranged in the list, but an ordered set would be unique.

Two examples should make this concept clear. “7 = 7”, since 7 is prime. “84 = 2*2*3*7” is the unique decomposition of 84 into primes, ordered by increasing value of the primes. One could also write “84 = (2^2)*3*7”.

If the number ‘1’ were included in the set of prime numbers, then this theorem would have a problem. “7 = 7 = 7*1 = 7*1*1 = 7*1*1*1 = …”. The theorem would have to exclude ‘1’ or stipulate that ‘1’ may only be used once.

The more descriptive name for this theorem is the “Unique Factorization Theorem“, as each divisor of a Natural number is called a “factor”.

Sieve for Seven – Image by Scot Nelson

The Infinite Universe of Prime Numbers

Euclid, an ancient Greek philosopher, proved that the number of prime numbers is infinite.

Another ancient Greek, Eratosthenes, described a mathematical “sieve” to filter out composite numbers that are the products of the first primes found. These two Greeks allow us to say, without being too rigorous, that the number of prime numbers must be a “countable” infinity.

This introductory article will not delve into Euclid’s proof or a more detailed description of the sieve of Eratosthenes. An earlier article, “Cantor Defeated Galileo in the Battle of Infinite Numbers“, explains countable versus uncountable infinities.

Leonhard Euler by Johann Georg Brucker: Image by Haham hanuka

The Future of Prime Numbers

Future articles in this series may include specific types of prime numbers, and ways in which prime numbers are used. Leonhard Euler is a modern mathematician who contributed to the study of prime numbers.
One use for prime numbers familiar to many in the fields of cryptography and of computer security is to multiply a pair of large prime numbers for data encryption. Because it is difficult to determine factors of a large number, this is a fairly secure way of encrypting computer data. Whether faster algorithms or “quantum computing” will ever make this approach obsolete are questions that remain unsolved.

External Resources:

Weisstein, Eric W. MathWorld (Wolfram). Fundamental Theorem of Arithmetic, Mersenne Prime, and Prime Number. Accessed Oct. 17, 2011.

Leave a Comment