The definition of a prime number

The standard definition of a prime number is an integer greater than 1 which is only divisible by itself and 1. While this definition is the simplest to state and often the easiest to work with, it’s not very motivated. And it has the pecularity that a prime number is required to be greater than 1. Why is this complication in the definition?

Obviously, the requirement is just a convention—and one which wasn’t even followed until the 20th century; many 19th-century mathematicians called 1 a prime number—but the convention does make quite a lot of sense. I hadn’t realised until recently just how much sense it made. The explanation I’d always heard was the same one given in Hardy & Wright’s Introduction to the Theory of Numbers. Using the standard definition, it is a theorem that every positive integer n is the product of a finite sequence of prime numbers (p_1, \dotsc, p_k) which is unique up to a permutation (i.e. every finite sequence of primes whose product is n is a permutation of (p_1, \dotsc, p_k)). But if 1 was considered a prime number, n would also be the product of every finite sequence obtained by inserting any number of terms equal to 1 into (p_1, \dotsc, p_k), so the theorem as stated would not be true. Of course, we could fix this by saying “unique up to a permutation or having any number of terms equal to 1 inserted or removed” rather than “unique up to a permutation”. Since the uniqueness is already qualified in the statement of the theorem, it doesn’t seem like a strong argument against the definition that another qualification would have to be added.

Even though 1 is not a prime, nobody has ever argued that 1 should be called composite. This is because with 1 not considered composite, the definition of a composite number is simple and clearly motivated: a composite number is a positive integer which is the product of a pair of smaller positive integers (we might call such a pair a decomposition of the composite number). The motivation for this definition is that smaller numbers may be easier to work with than the original, larger number. Clearly, 1 is not composite by this definition since it has no smaller factors.

Every composite factor in the decomposition of a composite number can be decomposed itself, and the same thing can be done with the composite factors in the resulting decomposition. Since there is only a finite number of positive integers smaller than each positive integer, there will always eventually be no composite factors left in the decomposition, so every composite number can be decomposed into non-composite factors. Now I can state my favourite definition of a prime number: a prime number is a non-composite number that is present in a decomposition of a composite number. Or in other words, prime numbers are the fundamental factors which all composite numbers are built out of. In fact, all numbers can be regarded as being built out of prime numbers, since each prime number is the product of a sequence whose only term is itself, and 1 is the product of the empty sequence, which is vacuously a sequence of prime numbers. It’s therefore very clear from this definition why primes are interesting. And it’s also clear that 1 is not a prime, because if 1 were present in the decomposition of a composite number n, the other number in the decomposition would have to be n, which isn’t smaller than n! Think of it this way: a prime is a non-composite number which you can divide a composite number by to make it smaller. But dividing by 1 wouldn’t make it smaller.

Hopefully, that explanation makes the requirement that prime numbers are not 1 make more sense to you. It worked for me, at least!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s