I thought I would end the week with a piece exploring one of the most fascinating areas of mathematics. This area is number theory and, more specifically, the prime numbers. Before delving into this area in more detail, we first need to define what we mean by a prime number.
What is a Prime Number?
To define a “Prime Number” we first need to explore what we mean by the set of positive integers. The positive integers are the set of whole numbers that we learn in primary school such as 1, 2, 3, 4, 5… They are the whole numbers which are greater than 0.
Now that we have defined the positive integers, we can more precisely explain what is meant by the prime numbers. A positive integer greater than 1 is a prime number if its only positive factors are 1 and itself. Put more simply, a whole number will be prime where it is greater than one and can only be divided by 1 and itself. Examples of prime numbers are 2, 3, 5, 7, 11 and 13.
Why are Prime Numbers so Interesting?
I am going to be very sloppy in this post and will make a statement without giving any proof. I do this to keep things at a high level. However, for a mathematician this would be the equivalent of a crime, and I will therefore apologise now.
For now, all I will say is that there is a “Fundamental Theorem of Arithmetic” in number theory which states that every positive integer greater than 1 is either prime or can be written as a product of prime numbers. What’s more, this product of primes is unique. I will provide an example of this in practice. Think of the number 110. This number can be written as the product of the prime numbers 2, 5 and 11, given that:
110 = 2 × 5 × 11
This is called prime factorisation. So, in this case the prime factorisation of 110 is 2 × 5 × 11.
Because of this “Fundamental Theorem of Arithmetic”, the prime numbers are often called the building blocks of all integers. Now the question you might have is, “how can I determine the prime factorisation of an integer?” It turns out to be very difficult to determine the prime factorisation of very large numbers, which makes this theory incredibly useful for purposes such as securing online banking.
Congruence
Before I go any further with this post, I want to introduce congruences. As stated earlier, I am going to break mathematical “laws” by not using strict definitions on this occasion, to keep things at a high level. Let m be a positive integer such as 4, then an integer a is congruent to an integer b modulo m if:
This can be written symbolically such that:
a ≡ b (mod m)
This definition might be confusing at this stage. However, it becomes clearer when represented through some examples.
Examples
If we take 15, 5 and 10, we can say that:
15 ≡ 5 (mod 10)
This is true from the definition outlined above, given that 15 – 5 = 10 which is divisible by 10. Put another way, 15 gives remainder 5 when divided by 10 (i.e. 10 goes into 15 once with remainder 5). Similarly, 5 gives remainder 5 when divided by 10 (i.e. 10 goes into 5 zero times with remainder 5).
We can take another example from the clock:
16 ≡ 4 (mod 12)
Here 16 – 4 = 12 which is divisible by 12, therefore the congruence holds. From this we know that 16 gives remainder 4 when divided by 12 and 4 gives remainder 4 when divided by 12.
We are indeed applying congruences when using a clock. If we think of a clock and start at 12 and then move around the clock 16 hours, we end up at the 4 o’clock position. This is because 16 gives a remainder of 4 when divided by 12.
So what?
Congruences can be used in cool ways to determine the prime factorisation of integers. However, due to lack of time this story will be continued in the next update to this post.