# Prime Series 1: Introduction to Prime Numbers

We have learned from elementary school mathematics that a prime number has only two factors, 1 and itself. For example, 2, 3, 5 and 7 are prime numbers, while 8 is not prime because it has four factors — 1, 2, 4, and 8. Numbers that are not prime are called composite numbers.

Geometric Interpretation of Prime and Composite Numbers

Mathematicians during the ancient times, particularly the Greeks, always make  use of geometric interpretations of numbers. Square numbers, for example, are represented with pebbles arranged with the same number of rows and columns.  The first five square numbers are 1, 4, 9, 16 and 25.

Rectangular numbers are also popular. For instance, the number 12 can be interpreted pebbles arranged in rectangles with the following dimensions: 3 by 4, 2 by 6 and 12 by 1. If we are going to use squares instead of pebbles, the geometric representations of these arrangements are shown in Figure 1.

Figure 1 – Different rectangular arrangements of 12 pebbles represented by squares.

Numbers that cannot be arranged as more than one rectangle are prime numbers. In our example above, 12 has three possible arrangements, while the numbers 3, 5 and 7 can only be arranged in a single row.

Figure 2 – Rectangular arrangements of 3, 5 and 7 pebbles represented by squares.

As we can see, this is the geometric interpretation of the definition that the factors of primes are only 1 and itself.

Sieve of Eratosthenes

The Greek philosopher and mathematician Eratosthenes was the first to be credited in identifying primes in a finite list by brute force.  The strategy is to list a finite set of counting numbers in increasing order, then starting with 2 eliminate all its multiples. This eliminates all even numbers except 2. Then we follow the same pattern: we eliminate multiples of 3 greater than 3, eliminate all multiples of 5 greater than 5 and so on, until all the numbers left are not multiples of any number smaller than it. The remaining numbers after all elimination are prime numbers.

The primes numbers less than 100 are shown in white cells in the table below. The numbers in the yellow cells are composite numbers.  Mathematicians agreed not to include 1 in the set of prime numbers or the set of composite numbers.

Figure 3 - The sieve of Eratosthenes shows primes less than 100 in white table cells..

If we look at the table above, we could not probably see a pattern about the number of primes in a given interval; however, if we investigate further, as the intervals increase, the number of primes is getting fewer and fewer. For example, there are 168 primes between 1 and 1000, 135 primes between 1000 and 2000, 127 primes between 2000 and 3000, and 120 primes between 3000 and 4000. With this observation, we want to ask the following question:

Is there a particular prime number, that after such number, we could no longer find primes?

or equivalently,

Are prime numbers finite?

We will answer this in the continuation of this article titled  “Infinitude of Primes.” The formal proof of this conjecture is also discussed in the third part.

## 25 thoughts on “Prime Series 1: Introduction to Prime Numbers”

1. Very nice primer on Primes – sorry couldn’t resist that.

Of course 1 isn’t in the set of Prime numbers or the set of composite numbers, because it is both Prime and Composite at the same time. Naturally a contradiction.

I like your explanation of Primes being expressed as rectangular arrangements. Of course we can’t express 1 that way as we would have 1 row by 1 column and that would suggest it is prime by the rectangular arrangement.

Also the set of composites is infinite as is the set of Primes but there is not a one-to-one relationship as between the two because the infinite set of the former is larger than the infinite set of the latter. Now that becomes mind-boggling…

Keep up the good work.

• Thank you Gordon. Yes, 91 is not prime, my mistake.

Hmmm… regarding the prime and composite as infinite sets, I am not quite sure. So far, we have two types of infinity, the $\aleph \null$ (the cardinality of integers, rational numbers, and natural numbers), and c (the cardinality of real numbers). As of now, it has not been proven if there is a type of infinity between them. This is what we call the continuum hypothesis. This means that the cardinality of prime numbers, composite numbers are similar as that of the set of integers. Well, I am not really a mathematician, so I might be wrong.

http://mathandmultimedia.com/2010/05/10/counting-infinite-sets/

2. Thanks for the url. An interesting read.

As for the infinity of the Prime set and Composite set. Take any two primes from the Prime set say p1 and p2, then they create an infinite set of composites p1^a x p2^b (ie p1 raised to the power a etc) for all integer values of a and b. Or one could take just one prime p1 and it creates an infinite set of composites p1^a for all a an integer value. Therefore the Composite set has larger cardinality than the Prime set.

• Comparing infinite sets and finite sets are two different things. To compare two infinite sets, we set up a correspondence between two sets such that nothing is left unpaired. For example, it seems that the cardinality of the set of integers {…,-3,-2,-1,0,1,2,3,…} is greater than the set of counting numbers {1,2,3,…}, but this is not actually the case.

That is why I think, the set of prime numbers and the set of counting numbers have the same cardinality because both of them can be paired with the set of counting numbers. As we know, if we can pair an infinite set with the set of counting numbers (that is, we can list them systematically without leaving a number without a pair), then we can say that they have the same cardinality which is equal to $\aleph \null$.

I will research on this one, though. I might be wrong.

3. Well I could be wrong too. 🙂

Though I’m taking an infinite number of subsets of the Prime number set with each Prime number subset generating an infinite subset of the Composite set. This “infinite subset of the Composite set” has the same cardinality as the set of counting numbers {1,2,3,…}, however the infinite number of generated subsets of the Composite set must have more than the cardinality of the counting numbers as each subset, as above, has the cardinality of the set of counting numbers. Whereas the cardinality of the subsets of Prime number set is just that of the counting numbers.

I hope that is as clear as mud. 😉

• I think, I got what you mean. But here’s may analogy (please bear with me). If we can the elements of any infinite set systematically, then we are sure that we can pair it with the set of counting numbers. If we can do this, we know that it has the same cardinality as that of the cardinality of counting numbers. For instance, the set of integers can has the same cardinality as the counting numbers because we can devise a way to write it without missing anything: {0,1,-1,2,-2,3,-3,…} So, if we pair it with the set of couting numbers, say (x,y), where x representing the counting numbers and y the set of integers, we have the ordered pairs (1,0), (2,1),(3,-1), (4,2),(5,-2), and so on. It is clear that the set of counting numbers is as many as the set of integers.

From the analogy above, we can see that we can list the set of composite numbers (and prime numbers also) systematically without missing anything since we know can test if a number is prime or composite. So, the composite numbers are {4,6,8,9,10,12,…} and the prime numbers are {3,5,7,11,13,…}. Therefore, both of them can be paired with the set of counting numbers. Hence, they have the same number of elements.

Whew! My apologies for the long explanation. 🙂

4. Yes I understand what u are saying and I’m using the same argument of obtaining a 1-to-1 correspondence with the counting numbers or integers (Z). I think u are assuming the thing to be proved. That is u assume the cardinality of the Prime set (P) and the Composite set (C) to be the same as the integers (Z).

Let’s assume that the Prime set P={p1,p2,p3, …} has a 1-to-1 correspondence with the integers, or (1,p1), (2,p2), (3,p3) etc as u mention in your post. Now the definition of a composite number is that it is created by a prime or a series of primes, so the Composite set is C={p1^a,p2^b,p3^c,…,p1^ap2^b,p1^ap3^c,p1^ap4^d,…,p1^ap2^bp3^c,….} where the a,b,c,d,… are integer values. Now taking anyone of those elements of C, say p1^ap2^b will generate an infinite set {p1^1p2^1,p1^1p2^2,p1^1p2^3,…p1^2p2^1,p1^2p2^2,…} which has a 1-to-1 correspondence with the integers. In fact any element of C we choose will generate an infinite which can be matched to the set of integers. Therefore C cannot be matched with the integers as it is much bigger, being an infinite set of sets with the latter each having a 1-to-1 correspondence with the integers!

Similarly if we assume that C has a 1-to-1 correspondence with the integers then we find that p1 being used an infinite number of times within the set C also p2 being used an infinite number of times within C and so on. That is there are an infinite number of elements of the set P that are duplicated and so cannot have a 1-to-1 correspondence with the integers. So the set of primes P must be less than the set of integers which means it must be finite (because it is a subset of the integers). This is a contradiction as we know (and u stated the proof) that the prime series is infinite, therefore the original assumption is incorrect and C doesn’t have a 1-to-1 correspondence with the integers.

Double whew! If u apologise for the long explanation then I must doubly so. 😉 I hope that is clear? I guess it really should be written in LaTex so all the maths symbols etc read better and appear clearer.

5. I found this theorem on Wikipedia:

Theorem: Every subset of a countable set is countable. In particular, every infinite subset of a countably infinite set is countably infinite.

Here’s the proof:
http://plato.stanford.edu/entries/set-theory/primer.html

Since prime numbers, and composite numbers are both subsets of a countably infinite set, they are also countable. Therefore, their cardinalities equal that of the cardinality of the set of counting numbers. 🙂

6. Sorry been out of wireless internet contact for a few days.

I see what u are saying and I’m still reading through the primer at the url u supplied. So my argument only works if the integer set doesn’t have a cardinality of the counting numbers, which is ludicrous since it is the counting numbers. Or the subsets can be countably infinite but have another attribute whereby they increase at a slower counting rate than the set of integers.

Hmmm doesn’t look good for my idea. Then again infinity is such a challenging and mysterious concept that it requires much more thought and discussion. Thanks for your input.

7. You’re welcome and thank you also. It was nice discussing with you, since I had to do my research also. hahaha… I am having a hard time discussing higher math since my foundation is not that strong. 🙂

• my undergraduate is computer science my masters is mathematics, but only master of arts, not master of science. 🙂

8. I have an idea for prime nos you want to find factors of numbers 2 to 10
First take strips dimensions 10×1 ,9×1, 8×1,7×1,6×1,5×1,4×1,3×1,2×1
1×1
Let us find the factors of 9
3 strips of 3×1 will cover the strip 9×1
9 strips of 1×1 will cover the strip 9×1
1 strip of 9×1 will cover the strips 9×1
The factors of 9 are 1,3,9

Let find the factors of 7
7 strips of 1×1 will cover the strip 7×1
1 strip of 7×1 will cover the strip 7×1
factors of 7 are 1 and 7
You cannot two kinds of strips together for example 2×1 and 5×1 for 7×1
You have to take one kind of strip .you can take different colour for different strip for example 1×1 red, 2×1 blue, 3×1 green and so on
Numbers which exactly two factors are prime and rest composite

• Looks like another good idea for teaching. Thank you for sharing.