Prime Numbers: What and Why

I’ll begin a short series of posts on prime numbers with several questions on the basics: What are prime (and composite) numbers, and why do they matter?

What is a prime number?

We’ll start with an anonymous question from 1995:

Prime Numbers

What are prime numbers?

Doctor Ken answered with the definition and a pair of examples:

Hello!

A prime number is a positive number that has exactly two factors, 1 and itself.  For example, if we list the factors of 28, we have 1, 2, 4, 7, 14, and 28.  That's six factors.  If we list the factors of 29, we only have 1 and 29.  That's 2.  So we say that 29 is a prime number, but 28 isn't.

As we’ll be seeing in the next two weeks, there are many ways to misstate this definition; every word in the definition matters!

Note that the definition of a prime number doesn't allow 1 to be a prime number: 1 only has one factor, namely 1.  Prime numbers have EXACTLY two factors, not "at most two" or anything like that.

This is where the word “exactly” comes in. Without it, you could take “has two factors, 1 and itself” as being true for 1, since 1 and itself are both factors and there is no other. (We’ll be seeing next week why we don’t want 1 to be a prime number; and the following week, we’ll see why “positive” matters.)

Here are the first few prime numbers:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, etc.

One important feature of prime numbers is that they are hard to predict, and seem almost random – yet they are definitely not! Here are the primes less than 100 on a number line:

Here are all the primes listed above, namely those less than 200:

The farther out you look, the more random they appear. Even here, you can see runs of nearly consecutive primes, and gaps with none.

How can I make a list like that?

Here is a 1997 question:

Prime Numbers: 20-30

Dear Dr. Math,

What are the prime numbers 20 through 30? My mom can't help me.

Thank you,
Leah

Doctor Wilkinson answered, starting with the basics:

First of all, you need to be sure you understand what prime numbers are.  In fact, if you understand that, you should be able to do this problem without any difficulty.

A prime number is a whole number which is not the product of smaller numbers.  For example, 14 is not a prime number, because it is 2 times 7. But 3 is a prime number, because the only smaller numbers are 1 and 2, and 3 is not 1 times 1 or 1 times 2 or 2 times 2.

This version of the definition is less formal, but gives the main idea well. We can directly use it to find primes (though not very efficiently).

To see if a number is prime, all you need to do is try the numbers smaller than it and bigger than 1 and divide them into your number.  If this ever comes out even, then your number isn't prime.  Otherwise, it is.

For example take 15.  If you try dividing it by 2, it doesn't come out even.  But if you try 3, it does.  15 is 3 times 5.  So it's not a prime.

Now let's look at 17.  If you try dividing it by 2, it doesn't come out even.  If you try 3, that doesn't come out even either.  Neither does 4, and neither does 5.

One way to improve efficiency would be to try only prime divisors, so we’d skip 4. Why? Because if a number can be divided evenly by 4, then it would have already have been found to be divisible by 2. But we aren’t looking for the best possible way to accomplish the task; we just want Leah to experience what primes are – and maybe discover more about them by doing things that aren’t necessary.

Now you could go ahead and try 6, 7, 8, and so on.  But if you noticed when you tried 5, you got a quotient of 3 and a remainder of 2. Now if you try something bigger, you're going to get a smaller quotient. So if it was going to come out even, it would already have come out even when you tried the smaller number, and at this point you can quit, because you now know that 17 is prime.

This kind of thinking allows you to decide when to stop: If the quotient is smaller than the divisor, you don’t need to try any larger divisors.

Do you think you can do this for the numbers from 20 to 30?  To get you started, I'll point out that 20, 22, 24, 26, 28, and 30 are all evenly divisible by 2, so none of them is prime.

This suggests other ways to shorten the work, which you can discover as you work. Later, we’ll look into how to test a number to see if it’s prime, and how to make a list more efficiently. But that can wait.

Prime and composite numbers

For more details, here is a question from 2003:

Prime, Composite, or Neither?

What are prime and composite numbers?  I just don't get it.

Doctor Ian answered:

Hi Hillary,

Suppose I have 12 items, and I try to arrange them into a rectangle. I can do this in more than one way:

  . . . . . . . . . . . .       1 x 12

  . . . . . .                   2 x 6
  . . . . . .

  . . . .                       3 x 4
  . . . .
  . . . .

We could also use \(4\times3\), \(6\times2\), and \(12\times1\), with the same pairs in the reverse order; we’re interested only in the pairs, not the order.

For some numbers, there is only one rectangle that I can make.  For example, if I have 7 items, I can do this:

  . . . . . . .

But if I try to make more rows, I always have something left over:

  . . . .
  . . .


  . . .
  . . .
  .

  
  . .
  . .
  . .
  .

A number like 7 is called 'prime'.  In contrast, a number like 12 is called 'composite'.

It’s easy to see that prime numbers are special. They can’t be broken down, sort of like atoms in chemistry.

One way to remember this is that something that is 'composed' is 'put together' from smaller pieces.  (For example, we compose a poem from words, and compose a song from notes.)

So composite numbers are numbers that are composed of other numbers. (And in chemistry, a compound is composed of different atoms! That’s related, too.)

On the other hand, prime means “first“, or “most important”; primes are the numbers we start with when we build up other numbers by multiplication – the building blocks of the natural numbers.

In the case of a number like 12, we can put it together in more than one way, using multiplication:

  12 = 1 x 12 

     = 2 x 6

     = 3 x 4

But 1 x 12 is hardly like putting something together, is it?  So if we ignore ways that include a 1, we see that there are two ways to put together a 12, 

  12 = 2 x 6

     = 3 x 4

and _no_ ways to 'put together' a 7.

So when we say that a prime number is one that has exactly two factors (itself and 1), we are saying that there are no “non-trivial” ways to factor it; it can’t be made by “putting together” numbers not including itself.

One tricky point is that the number 1 is considered to be neither prime nor composite.  (Think about why this would be the case.)  So while it's tempting to say things like 

   A number is prime if it's not composite.

or

   A number is composite if it's not prime.

neither of these is quite true, because 1 isn't composite, but it's also not prime; and 1 isn't prime, but it's also not composite.

We say that the terms “prime” and “composite” are not exhaustive; “composite” doesn’t quite mean “not prime”. More on this, again, next time.

Why do we care about any of this?  That's discussed here:

  Why Study Prime and Composite Numbers?
    http://mathforum.org/library/drmath/view/57182.html

Who uses primes?

That was a reference to the following question from 2001:

Why Study Prime and Composite Numbers?

My daughter is in Grade 6. She is learning about prime and composite numbers but my husband and I wonder why this is taught in school at all. Who uses this in the real world? Why does someone need to know whether a number is a prime number or not?

Doctor Ian had answered that:

Hi Kim,

Every time you send a credit card number over the Internet, it gets encrypted by your browser, and the encryption algorithm is based on the theory of prime numbers. At some point, electronic money will become as common as paper money, and _that_ will also be based on the theory of prime numbers. And what's used more in the real world than money?

Encryption is everywhere now! And the basic idea behind the common method is that it’s easy to “compose” numbers, but hard to “decompose” them into a product of primes.

For example, say I choose the primes 7127 and 7879. Their product is 56,153,633. I send you this number (or just post it on my website for anyone to use); you use that number, by a method I’ve specified, to encrypt a message; and I then use my separate primes to create a number I can use to decrypt the message. This calculation is easy using the primes themselves, but would be very hard using only their product. On the other hand, anyone who could factor 56,153,633 could decrypt the message; so I’m trusting that it’s too hard for anyone to do quickly enough to take advantage of it. (We’d really use primes with 100 or more digits.)

But that’s all behind the scenes, and you don’t have to know about that math in order to use it. (Somebody does have to know it, though!) How might primes be needed directly in your own experience? Mostly as a part of other math:

The importance of prime numbers is that any integer can be decomposed into a product of primes. For example, if you want to know how many different pairs of numbers can be multiplied to get 360, you can start trying to write them down,

  1 * 360
  2 * 180
  3 * 120
  4 *  90
  5 *  72
  6 *  60

checking every single number up to 180, and hope that you don't miss any; or you can decompose 360 into its prime factors, 

  360 = 2 * 2 * 2 * 3 * 3 * 5

with the assurance that every factor of 360 will be a product of a subset of these prime factors.

Knowing how a number breaks down, like knowing what atoms a chemical is made of, or how the parts of a car fit together, makes it possible to understand it better.

In the example above, you can list the pairs of factors by listing all ways to choose 0, 1, 2, or 3 twos, 0, 1, or 2 threes, and 0 or 1 five to make a factor. This tells you, in fact, that there are \(4\times3\times2=24\) factors of 360 (that is, 12 pairs of factors). The 12 factors listed above are only half of them. (Can you find the other 12?)

(See Counting Divisors of a Number for more on this.)

This kind of analysis is extremely convenient when working with fractions (since prime factorization tells you which common denominators are available for any two fractions), when factoring polynomials... when doing just about anything where integers are involved, really.

For example, if the denominators of two fractions are, say, 2205 and 2100, that is, \(3^2\times5\times7^2\) and \(2^2\times3\times5^2\times7\), we know that the least common denominator, in order to be a multiple of both, has to have 2 twos, 2 threes, 2 fives, and 2 sevens, making it \(2^2\times3^2\times5^2\times7^2=44,100\). We can find the greatest common factor similarly. Of course, since it is hard to find factors of large numbers, another method is needed when the numbers are really large.

(See Many Ways to Find the Least Common Multiple for more on this. Also, compare Three Ways to Find the Greatest Common Factor. And don’t forget How Do You Simplify a Fraction?.)

Are prime numbers necessary? Not really:

Think of it this way.  You don't need to learn to multiply, since you can always use repeated addition to solve any multiplication problem, right? If you want to know what 398 times 4612 is, you can just start adding:

  398   (1) 
  398   (2)
 ----
  796
  398   (3)
 ----
 1194
  398   (4)
 ----
  etc.

Knowing about multiplication saves you time. That's all it does... but that's a lot!

And that’s what primes do most: save time (sometimes centuries, for really big jobs).

Mostly, prime numbers are good for quickly transforming a situation with zillions of possible outcomes into an equivalent situation with only a handful of possible outcomes.  

Here is another way to think about it:  If you're looking for some needles in a haystack, you can start picking up each piece of straw, checking to see if it's a needle, and then tossing it over your shoulder. Or you can use a magnet to find the needles right away.  

In mathematics, prime numbers serve the same function as a really, Really, REALLY big magnet.  

In short, knowing about prime and composite numbers will save your daughter enormous amounts of time in her later math classes - and possibly over the course of her life, if she goes into a technical field.

It’s not how a number is written that matters

Let’s close with a 1998 question from an entirely different perspective:

Prime Numbers in Different Bases

Hi, Dr. Math,

Here is a question I have for you.  It's on prime numbers.

Are all prime numbers the same in all bases? If 21 is a prime, are 10101 (in binary), and 15 (in hexadecimal) also primes?  

I'm taking a course in Assembly Language Programming, and I was wondering if primality as such is related at all to the number system I am using?  What would happen, for instance, if I chose as a base a prime number, such as thirteen?

Computers commonly use base 2 (binary) for internal storage of numbers, and represent them in hexadecimal (base 16) to print them out more compactly. Does that affect prime numbers? How can we recognize them when written in those forms?

Writing a number in a particular base means using place values that are powers of the base. For example, 21 in base 10 means \(21_{10}=2\times10^1+1\times10^0=2\times10+1=21\), while 15 in hexadecimal (base 16) means \(15_{16}=1\times16^1+5\times16^0=1\times16+5=21\). They’re different numerals for the same number.

Doctor Mike answered:

Hi Jorge,    

A prime is a prime no matter which base you use to represent it. On the surface one might think that in Hex you would have 3*5 = 15 as "usual," but it really turns out that 3*5 = F. 

The example 21 doesn't work too well because it is not prime. The base ten number 37 is better, because it is prime, but its Hex representation is 25, which sort of looks non-prime. Hex 25 is not, however, repeat not, 5 squared.

Whether you write 21 as \(21_{10}\) or as \(15_{16}\), it is still a composite number; in either base, it is \(3\times7\). And whichever way we write 37, it still refers to the same number – even though we are so familiar with numbers like 25 that we automatically think of it as a square. (A similar issue arises with judgments of evenness and oddness; in an odd base, numbers that “look” even to our base-ten eyes may be odd!)

Okay, enough for examples. The fact of being prime or composite is just a property of the number itself, regardless of the way you write it. 15 and F and Roman numeral XV all mean the number, which is 3 times 5, so it is composite. That is the way it is for all numbers, in the sense that if a base ten number N has factors, you can represent those factors in Hex and their product will be the number N in Hex.

And if a number has no factors other than itself and 1 in base ten, that is still true when you write it in another base. It’s the number that counts, not the numeral (the representation of the number).

So, how do you recognize a prime in binary or hexadecimal? The same way, ultimately, as in decimal: Either do a lot of divisions to look for factors, or be sufficiently fluent in the appropriate base that you recognize products (or know the divisibility tests appropriate to that base – which will all be different than in base ten).

Relating to your question about base 13, the base ten number 13 will be represented as "10" in that system, but "10" will still be a prime, because you cannot find two numbers other than 1 and "10" that will multiply together to make "10". 

I hope this helps you think about primes in other bases.

So a prime base has no effect on primality of numbers written in it, any more than any other base does. It just makes things look different.

Just for fun, here are the first 13 primes, written in base 13 (with digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C):

2, 3, 5, 7, 11, 10, 14, 16, 1A, 23, 25, 2B, 32

They don’t all look prime to eyes accustomed to base ten, but they are! (Note that the units digit being even doesn’t imply the number is even, when the base is odd.)

Next week, we’ll look at some special cases: 0 and 1. The following week, we’ll consider negative numbers.