This brief article is about Prime and Composite numbers and, more specifically, trick that many people learn to test whether or not a number is a multiple of three. I have covered these concepts in other work, but include some basic background here as well.

The genesis of this piece is an answer that I wrote to the question “How is 51 not a prime number?”, which was posted on Q&A site Quora.com. While rather a silly question ^[1], I used the opportunity to talk about a field of Mathematics called Modular Arithmetic; something that is important in many areas.

Several sections of the text are verbatim copies of my original answer, but I have also interleaved some definitions, explanations and illustrations along the way and made a few minor improvements or clarifications here and there.

At the time of writing, the Quora answer this article is based on has passed 1,400,000 views; making it my most popular Quora post. Quora is often a very strange place!

 
Prelude…

Let’s start by recalling that the question was, “How is 51 not a prime number?”. The TL:DNR ^[2] answer I initially offered was:

Grab a calculator. Type these buttons:

And we are done…
 

 
…and Fugue

What the above answer achieved in terms of brevity and accuracy was perhaps not matched by its didactic merits. Many, many (so many ^[3]) Quora members delighted in telling the person who asked the question that must be divisible by because, if you sum its digits (i.e. ), you get an answer () which is itself divisible by . As no one seemed inclined to explain why this trick worked, I took the burden upon myself.

Before leaping in to my answer, let’s make sure that we are straight on our definitions…
 
 
Prime or Composite

The concepts Prime and Composite can be extended to analogues in a range of number systems ^[4], but properly apply only to Natural Numbers. Natural Numbers (denoted by ) are a very familiar set, namely:

where, of course, the ellipsis at the end means that these go on forever ^[5].

Whether a Natural Number is Prime or Composite is to do with its factors. Factors themselves relate to multiplication. Once a child has taken on board the concept of addition (and its mirror image subtraction), multiplication (and its mirror image division) are tackled next. Indeed multiplication is introduced as repeated addition as in:

though a more robust definition is required when multiplying other types of numbers (e.g. ).

It is not hard to see that if we multiply any two Natural Numbers, we arrive at a third Natural Number ^[6]. Equally, it is probably self-evident that, starting with a given Natural Number, , you can always find two Natural Numbers, and , whose product yields the initial number. In the language of Mathematical Logic:

In our example, and are known as factors of . For our purposes, factors of a Natural Number are other Natural Numbers that can be multiplied together to generate the original number.

To consider some concrete examples:

As , three and four are both factors of twelve. As , eighteen and six are both factors of one hundred and eight.

If we focus on twelve, then we also have the following:

so factors may not be unique ^[8].

However, it is worth noting that sometimes the only way we can factor a Natural Number is like this:

That is, some Natural Numbers can only be factored in one way (ignoring the order of multiplication as of course ).

Another way of stating this is that some Natural Numbers cannot be expressed as the product of other Natural Number factors unless these are the number itself and one. Phrasing this slightly differently, some Natural Numbers have precisely two factors (themselves and one) and others have more.

Of the above – wholly equivalent – definitions, it is the final one relating to the number of factors that is most frequently used to define Prime and Composite Numbers. Natural Numbers with precisely two factors are called Prime Numbers and Natural Numbers with more than two factors are called Composite Numbers.

This leaves one of course. As it only has one factor (itself) it is neither Prime nor Composite; it is often described as a unit ^[10].

Flexing our definitional muscles, we can see that two is a Prime Number, three is Prime, four () is Composite, five is Prime, six () is Composite, seven is Prime, eight () is Composite, nine () is Composite, ten () is Composite and so on.

A simple – albeit laborious – way to tease out Prime Numbers is called the Sieve of Eratosthenes. A subset of the Natural Numbers is written out in a grid. Then – using our times tables – all multiples of two except two itself are crossed out , followed by all multiples of three except three itself. Four is crossed out already, so we move on to crossing out all multiples of five except five itself. Six is crossed out already, so we move on to crossing out all multiples of seven except seven itself. And so on…

We can see that what remains is a subset of the Prime Numbers. We can also observe with some confidence that this approach will not yield the most efficient of algorithms. Sadly, there is no silver bullet which enables us to quickly tell whether any given number is Prime. However, there are a number of tricks that can be employed to immediately determine that some are Composite. Echoing the Sieve of Eratosthenes, any even number (bar two itself) is Composite. Any number ending in zero or five (bar five itself) is divisible by five and so Composite. Is there any trick like this which helps us to detect multiples of three? Well let’s explore this question further.

 
 
The Rule of Three

By popular demand, we are delighted to present a proof that if the digits of a Natural Number sum to a multiple of , the number itself is divisible by and vice versa. This is pertinent to the question asked as clearly and ( is shorthand for is divisible by ).

One way to do this is to introduce the concept of modular arithmetic, often known – for reasons that will shortly become apparent – as clock arithmetic. It is with clocks that we start.

Imagine a traditional clock face, it can even have IIII instead of IV at 20 past the hour if you like, but I’m going to call that position anyway. Let’s assume our clock only has an hour hand and also forget about AM and PM. If the time now is 2 o’clock, what time will it be in three hours? Easy right? , so 5 o’clock. What about if we are at 5 o’clock and want to know what the time will be in another eight hours. Easy again. , 13 o’clock and we are suddenly trapped in a George Orwell novel. Instead of course, the hour hand goes “round the clock” and we are back at 1 o’clock. Pertinent to our work here .

In modular arithmetic, we would capture the above as follows:

Here is short for modulo.

We might also consider that if it is 5 o’clock now, it will be 2 o’clock in thirty three hours. This is because and or:

This is the essence of modular arithmetic, we ignore how many times we go round the clock and only care where we end up on the clock face.

Also, you don’t have to have clock faces with 12 marks on them, you could have any Natural Number. If we had a clock with five marks on it, the resulting arithmetic is modulo .

Here we can see that if we start at “1 o’clock” ^[11] and three hours go by, we are at “4 o’clock”, but if instead six “hours” go by, we are at “2 o’clock”. Or, using our modulo notation:

It is probably apparent that we have a link to divisibility here. If we want to work our what a number, let’s randomly pick , is modulo , then we take away the biggest multiple of that does not result in a negative number. So:

It is probably also obvious that a number is equal to zero modulo if and only if five divides the number. I.e.

So, to explore whether or not a number is divisible by three, it may be helpful to consider arithmetic modulo . Let’s do just that.

Well a useful initial observation is that:

This also implies that for all Natural Numbers, .

To see this note that as above and assume that we are given that . Then we have:

Obviously is divisible by so it is equal to so we have:

which we know is equal to . So our result holds by induction.

Now consider a number, say , what this actually means is:

or

If we look at this expression modulo , our intermediate observation means it reduces to:

or just:

We can see that:

So whether or not is divisible by three is equivalent to whether or not the sum of its digits is divisible by three (here it is, so ).

But there was nothing special about in the above, it is evident that a similar argument would apply to any Natural Number. This is why you can check whether or not a number is divisible by three by seeing whether the sum of its digits is divisible by three

 
Coda

As with many aspects of Mathematics, there are clearly other ways to prove our result about numbers that are divisible by three. However, Modular Arithmetic is one of the foundational elements of Number Theory and is of great importance in many other fields, such as Group Theory and many other areas of Abstract Algebra. It finds more practical uses in Cryptography (inevitably!) and Computer Science. Given where we started, perhaps the old aphorism that there are really no stupid questions has some merit after all.

 
For an introduction to Prime Numbers, a Prime Primer as it were, consider reading the relevant section of A Brief Taxonomy of Numbers.

What are people saying about A Brief Taxonomy of Numbers?

• “Simply the best [article introducing number systems], better than all the rest [of articles introducing number systems]” – Tina Turner
   
• “Better read it carefully, or it can change your life. For instance, once I read it to my girl and now my girl’s my wife” – The Disney Corporation
   
• “Nothing compared to 2” – Sinead O’Connor / Prince
   
• “It’s the top, it’s meeting Santa. It’s the top, it’s a proof by Cantor” – Cole Porter
   
• “[Complex Numbers are] even better than the Real thing” – U2

 

Consider Supporting Us   Like all of the content on peterjamesthomas.com, this article is free. However, if you enjoyed reading it, you might consider helping to support the creation of new content by making a small contribution to defray our costs. Pay as much or as little as you want. Of course this is entirely optional. Peter James Thomas

 

<<	Six Easy Pieces	Glimpses of Symmetry	>>
Part of the peterjamesthomas.com Maths and Science archive.

 
Notes

[1]	In the same way that the Pontiff is rather fond of rosaries that is. Such things sadly dominate Quora at the moment for reasons I won’t bore the reader with.
[2]	Too long: Did not read.
[3]	One of many (so many) annoying things about Quora is that multiple people offer exactly the same answer without checking what anyone else has said.
[4]	One example that comes to mind is “Prime” and “Composite” Gaussian Integers.
[5]	The smallest Natural number was originally defined as one, more recently, the set has been expanded to start with zero, but I am a stubborn traditionists / dinosaur (delete as applicable).
[6]	In technical parlance, the set of Natural Numbers is closed under the binary operation of multiplication.
[7]	If you are not fluent in this language, the above traslates as: For every Natural Number, , you can find two Natural Numbers, and , such that .
[8]	Well some factorisations may be unique of course. See: a section of Glimpses of Symmetry, Chapter 8 – Simplicity.
[9]	At the time of writing, it is the largest known Mersenne Prime.
[10]	Or of course the multiplicative identity element. See: Glimpses of Symmetry, Chapter 4 – Rationality and Reality.
[11]	These may or may not be actual hours, consisting of 60 minutes. Whatever the numbers denote – and unlike our original 12 hour clock – it is probably stretching things to use “o’clock” and “hours” without the quotation marks.

Text & Images: © Peter James Thomas 2020 – 2021. Published under a Creative Commons Attribution 4.0 International License.