Prime Numbers

In primary school, we learned about counting numbers:

$1, 2, 3, \dots, 10\, 000\, 000.$

Of course, $10\, 000\, 000$ isn’t the biggest number: add one to it to get an even bigger or larger number $10\, 000\, 001$ . Repeating this procedure indefinitely, it seems at least likely that the “total number” of counting numbers is beyond finite.

We call these numbers the natural numbers, which we can formulate using more primitive ideas in discrete mathematics.

But perhaps we should start by think smaller. Let’s think about the natural numbers $2,3, \dots, 10$ . Notice the natural numbers

$4 = 2 \times 2, \quad 6 = 2 \times 3, \quad 8 = 2 \times 4, \quad 9 = 3 \times 3,\quad 10 = 2 \times 5.$

We call these numbers composite, since they are composed of smaller natural numbers. We call these smaller numbers the factors of the original number.
On the other hand, if we tried to write $2$ or $3$ as a product of smaller natural numbers, it is impossible! Natural numbers like $2, 3, 5, 7$ , therefore, are primary, or rather, prime.

Definition 1. A natural number larger than $1$ is composite if it can be written as a product of at least two strictly smaller natural numbers larger than $1$ . A number larger than $1$ is prime if it is not composite.

Just like the natural numbers, there are an infinite number of primes that we can write down in sequence, one after another. But the number $8$ is weird. Observe that $4 = 2 \times 2$ , so that

$\begin{aligned} 8 &= 2 \times 4 \\ &= 2 \times (2 \times 2) \\ &= 2 \times 2 \times 2 \\ &= 2^3, \end{aligned}$

where the power $3$ is the “short-form” for repeated multiplication.

There are no other factors: we cannot obtain $8 = 2^2 \times 3$ (the right-hand side is, in fact, $12$ ), for example. We say that the decomposition $8 = 2^3$ is unique, and this decomposition turns out to be a feature, not a bug.

Theorem 1. Every natural number larger than $1$ can be written as product of prime numbers in exactly one way. This result is known as the fundamental theorem of arithmetic.

Proof. Omitted as it requires a technical result known as mathematical induction. You can explore more on that here.

Remark 1. In mathematical writing, we use somewhat fancy words like Definitions and Theorems. Let’s clarify what we mean such crazy words:

Definition: a name for a mathematical idea.
Theorem: a correct mathematical sentence.
Proof of a Theorem: a logically correct sequence of ideas that show why the theorem is correct.
Example: a case study.
Remark: random miscellaneous comments that would disrupt the main story.

The resulting product from Theorem 1 is called the prime factorisation of the original natural number. Hence, the prime numbers as part of that factorisation are known as the prime factors of that number.

Example 1. Evaluate the prime factorisation of $60$ .

Solution. We will slowly divide $60$ by the prime numbers.

The first prime number is $2$ . Doing some long division, $60 = 2 \times 30$ .
Can we decompose $30$ as well? Yes, since $30 = 2 \times 15$ .
Now with $15$ , we get $15 = 2 \times 7 + 1$ , so we need to move on to the next prime number $3$ : $15 = 3 \times 5$ .
Now $5 = 3 \times 1 + 2$ , so we move on to the next prime number $5$ : $5 = 5$ .

Since we reached our last prime number, we obtain:

$\begin{aligned} 60 &= 2 \times 30 \\ &= 2 \times (2 \times 15) \\ &= 2 \times (2 \times (3 \times 5)) \\ &= (2 \times 2) \times 3 \times 5 \\ &= 2^2 \times 3 \times 5. \end{aligned}$

Why should we care about prime factorisation? Because we can use them to obtain the highest common factor and the lowest common multiple between two numbers. What is the highest common factor between $60$ and $80$ ? Compare their prime factorisations:

$\begin{aligned}60 &= 2^2 \times 3^1 \times 5^1, \\ 80 &= 2^4 \times 3^0 \times 5^1.\end{aligned}$

Remark 2. Here, we let the power of $0$ represent the the process of repeated multiplication of $3$ a total of $0$ times to the number $1$ —we just remain with the number $1$ .

Observe that what’s shared by both numbers are:

two copies of $2$ and
one copy of $5$ .

Therefore, their largest common factor, denoted $\mathrm{HCF}(60,80)$ , must be

$\mathrm{HCF}(60,80) = 2^2 \times 5^1 = 20.$

Similarly, their lowest common multiple, denoted $\mathrm{LCM}(60,80)$ , is the smallest number that includes $60$ and $80$ as factors.

Observe that:

$2^2$ and $2^4$ are both factors of any number that has at least a $2^4$ in it.
Likewise, $3^1$ and $3^0$ are both factors of any number that has at least a $3^1$ in it.
Finally, $5^1$ and $5^1$ are both factors of any number that has at least a $3^1$ in it.

Therefore,

$\begin{aligned} \mathrm{LCM}(60,80) &= 2^4 \times 3^1 \times 5^1 = 240. \end{aligned}$

Hence:

to obtain the highest common factor between two numbers, we multiply the smaller of the powers of their primes, and
to obtain the lowest common multiple between two numbers we multiply the larger of the powers of their primes.

For a complete and rigorous proof of this result, see this post.

Example 2. Determine $\mathrm{HCF}(1998,2025)$ and $\mathrm{LCM}(1998,2025)$ .

Solution. Firstly, follow Example 1 to calculate the prime factorisations of $1998$ and $2025$ :

$\begin{aligned}1998 &= 2^1 \times 3^3 \times 5^0 \times 37^1,\\ 2025 &= 2^0 \times 3^4 \times 5^2 \times 37^0.\end{aligned}$

Then we obtain

$\begin{aligned}\mathrm{HCF}(1998,2025) &= 2^0 \times 3^3 \times 5^0 \times 37^0 = 27, \\ \mathrm{LCM}(1998,2025) &= 2^1 \times 3^4 \times 5^2 \times 37^1 = 149\, 850. \end{aligned}$

Example 3. Without using a calculator, find the natural number $n$ such that $n^2 = 2025$ . We call $n$ the square root of $2025$ , denoted $\sqrt{2025}$ .

Solution. Firstly, follow Example 1 to calculate the prime factorisation of $2025$ :

$\begin{aligned}2025 &= 3^4 \times 5^2.\end{aligned}$

Firstly, we note that $n$ can only include factors of $2025$ , so that it takes the shape of

$n = 3^p \times 5^q,$

where $p, q$ are natural numbers. Since we want $n^2 = 2025$ , we must have

$\begin{aligned} 2025 &= (3^p \times 5^q)^2 \\ &= (3^p \times 5^q) \times (3^p \times 5^q) \\ &= 3^{p + p} \times 5^{q + q} \\ &= 3^{2 \times p} \times 5^{2 \times q}. \end{aligned}$

Therefore,

$\displaystyle 3^{2 \times p} \times 5^{2 \times q} = 2025 = 3^4 \times 5^2.$

Since there is only one factorisation for $2025$ (i.e. the factorisation is unique), we must have $2 \times p = 4$ and $2 \times q = 2$ . The only natural numbers that satisfy (i.e. solve) these equations are $p = 2$ and $q = 1$ . Therefore,

$\begin{aligned} \sqrt{2025} &= 3^p \times 5^q \\ &= 3^2 \times 5^1 \\ &= 45. \end{aligned}$

Using prime factorisation, we can write fractions in their simplest form.

Definition 2. A fraction $\displaystyle \frac pq$ is in simplest form if $p$ and $q$ share no common prime factors. Equivalently, $\mathrm{HCF}(p,q) = 1$ .

Example 4. Evaluate $\displaystyle \frac{1998}{2025}$ in its simplest form.

Solution. The fraction $\displaystyle \frac{1998}{2025}$ is not in simplest form since $\mathrm{HCF}(1998,2025) = 27$ by Example 2. However, by using their prime factorisations,

$\displaystyle \frac{1998}{2025} = \frac{2^1 \times 3^3 \times 5^0 \times 37^1}{ 2^0 \times 3^3 \times 3 \times 5^2 \times 37^0} = \frac{2 \times 37}{ 3 \times 5^2} = \frac{74}{75},$

which is in simplest form since $\mathrm{HCF}(74, 75) = 1$ (left as an exercise; follow Example 2).

While there can be much more to be said about the prime numbers and the natural numbers, a natural questions arises: what exactly is a negative number?

—Joel Kindiak, 18 Sept 25, 0314H

KindiakMath

Prime Numbers

Leave a comment Cancel reply

Prime Numbers

Share this:

Leave a comment Cancel reply