Introduction to Number Theory: The Basic Concepts

Portrait of Pierre de Fermat and Marin Mersenne

Hi, everyone. Today I want to talk about number theory, one of the most important and fundamental fields in all of mathematics. This is a field that grew out of arithmetic (as a sort of generalization) and its main focus is the study of properties of whole numbers, also known as integers.

Concepts and results from this field are important enough to have implications for (and be used in) almost every branch of mathematics. And not just mathematics. Number theory is also extremely fundamental to fields like cryptography and computer science and has applications in many other sciences, like physics and chemistry.

Apart from wanting to show you the basics of a field as important as number theory, I have two more concrete motives for writing today’s post.

Why number theory?

First, even though strictly speaking this post isn’t part of my series on numbers and arithmetic, it’s very closely related to it. The concepts I’m going to introduce will be very helpful for following the last two posts of the series on fractional and irrational numbers. In fact, if you’re completely new to this topic, I’d put this series in the list of strongly recommended readings before you proceed with today’s post. In particular, I’d recommend you skim through the topics up to my post on negative numbers and integers to make sure you’re familiar with the basics of whole numbers and operations with them. Also, check out my post on Euclidean division to make sure you’re familiar with division with remainder and some common divisibility rules.

Second, the things I’m going to show you today (and in two other follow up posts) will be useful for some of the more advanced topics in my series on cryptography, as well as other future posts related to cryptography and cryptanalysis. Well, number theory’s usefulness will also be popping up in many other areas I’m planning to cover on my website.

Anyway, since we’re talking about number theory, the focus today is naturally integers. The main concepts I’m going to cover are factors and multiples, along with two other central number theoretic concepts they spawn: prime numbers and common factors and multiples between numbers.

Initially, I also wanted to include numeral systems and modular arithmetic here but then I realized it’s too much to fit in a single post. And so I decided to leave those two for follow up posts because they’re too important and deserve their own space. Especially modular arithmetic which, arguably, is the most important topic in all of number theory. You’ll see what I mean!

Table of Contents

Factors and multiples

Alright, let’s first talk about factors. This concept is quite fundamental and you’ll use it in almost everything related to number theory (and more).

When we multiply two numbers, we call the result their product. Looking from the point of view of the product itself, the two numbers are called its factors. For example, if you have something like:

$6 \cdot 4 = 24$

We say that 6 and 4 are factors of 24. But they’re not the only factors since we could have obtained 24 in other ways. For example:

$2 \cdot 12 = 24$

$8 \cdot 3 = 24$

Which means that 2, 3, 8, and 12 are also factors of 24. Finally, the number 24 itself, as well as the number 1, are factors because:

$1 \cdot 24 = 24$

One common notation for saying that a number a is a factor of another number b is:

$a \mid b$

And to say that a is not a factor of b, we use the notation:

$a \nmid b$

So far, so good. Now, let’s look at things from the factors’ perspective. As far as each factor is concerned, its product with another number is its multiple. For example, 6 is a multiple of 2 because $2 \cdot 3 = 6$

and 24 is a multiple of 8 because $8 \cdot 3 = 24$

A product of two factors resulting in a common multiple

Notice the inverse relationship between factors and multiples. If a number f is a factor of another number m, this means that m is a multiple of f, and vice versa. So, we can also read an expression like $a \mid b$ as “b is a multiple of a” and $a \nmid b$ as “b is not a multiple of a“.

All factors and multiples of a number

In general, the set of factors of a natural number m are all numbers which can be multiplied by some other number to produce m. Therefore, every positive number has a finite set of numbers associated with it, called its “factors”. There is no common notation for this set, so I’m going to use F(n) for an arbitrary number n. For example, with this notation we can write the set of factors of 24 as:

$\textrm{F}(24) = \{1, 2, 3, 4, 6, 8, 12, 24\}$

Unlike factors, every number (except 0) has infinitely many multiples because there’s infinitely many other numbers you can multiply it with, each resulting a different product. In general, the set of all multiples of a natural number n consists of all numbers in the form:

$n \cdot k$

…where k is any integer. This means that now we’re considering negative numbers too!

For example, let’s consider the set of multiples of 3. The first four positive multiples are obtained by multiplying 3 by 1, 2, 3, and 4, which are the numbers 3, 6, 9, and 12. And for the first four negative multiples we multiply by -1, -2, -3, and -4 to get the numbers -3, -6, -9, and -12. Finally, we also have 0 as a multiple of 3 because $3 \cdot 0 = 0$ .

A common notation for writing the set of all multiples of a natural number n is $n\mathbb{Z}$ because, if you remember, $\mathbb{Z}$ is the common notation for the set of all integers. Therefore, with this notation we can express the integer multiples of 3 as:

$3\mathbb{Z} = \{..., -15, -12, -9, -6, -3, 0, 3, 6, 9, 12, 15, ...\}$

For two more examples, the integer multiples of 4 and 5 are:

$4\mathbb{Z} = \{..., -20, -16, -12, -8, -4, 0, 4, 8, 12, 16, 20, ...\}$

$5\mathbb{Z} = \{..., -25, -20, -15, -10, -5, 0, 5, 10, 15, 20, 25, ...\}$

If you’re wondering why I skipped the multiples 0, 1, and 2… Well, the first two are rather trivial:

$0\mathbb{Z} = \{0\}$

$1\mathbb{Z} = \mathbb{Z}$

And I left the multiples of 2 as a separate topic.

Even and odd numbers

The set of all integer multiples of 2 has a special name in number theory. We call those integers even numbers:

$2\mathbb{Z} = \{..., -10, -8, -6, -4, -2, 0, 2, 4, 6, 8, 10 ...\}$

You see that every even number can be represented as $2k$

where k is some integer. And notice that between any two even numbers there’s a gap of exactly one number:

A number line of the even and odd numbers — Even (in red) and odd (in blue) numbers

These numbers that live in between even numbers were given the name odd numbers. An arbitrary odd number is always in the form $2k + 1$ for some integer k. You can think of odd numbers as the numbers that fill the gaps between even numbers to complete the entire set of integers.

The property that deals with whether a number is odd or even is called parity. For example, we say that the parity of 6 is “even” and the parity of 9 is “odd”.

Now, there are a few patterns when it comes to adding and multiplying odd and even numbers I’d like to show you. They are both useful on their own and they’ll serve as a warm-up for the more general topic of modular arithmetic I’m going to talk about in one of the next posts.

Adding even and odd numbers

Before we start, let’s pick the letters k and j to represent two arbitrary integers. Also, let’s pick n to represent their sum $k + j = n$ , which is another arbitrary integer.

So here’s the first pattern: if you add two even numbers, the result is always another even number. Here’s why:

$\textrm{Even} + \textrm{Even} = 2k + 2j = 2(k+j) = 2n$

Here we simply used the distributive property of multiplication over addition. Because 2n matches the definition of an even number, we know the result is even.

Second, if you add two odd numbers, the result is again always an even number:

$\textrm{Odd} + \textrm{Odd} =(2k + 1) + (2j + 1) = 2k + 2j + 2$

$= 2(k + j + 1) = 2(n + 1) = 2m$

Here we made use of the commutative and associative properties of addition and then the distributive property of multiplication. I used the letter m to represent the sum $n+1$

(which is also an arbitrary integer) to make the evenness of the result more noticeable.

Finally, if you add an odd and and even number, the result is always an odd number:

$\textrm{Odd} + \textrm{Even} = (2k + 1) + 2j = 2(k + j) + 1 = 2n + 1$

After using the commutative, associative, and distributive properties once again, we got the result in the form $2n + 1$

which exactly matches the definition of an odd number.

So, to summarize:

Even + Even = Even
Odd + Odd = Even
Odd + Even = Odd

Try a few examples of each combination to verify that they work!

Multiplying even and odd numbers

Similar patterns exist for multiplication. I’m going to use k and j to express arbitrary even and odd numbers again (and go through these short proofs a bit faster).

First, multiplying two even numbers always results in another even number:

$\textrm{Even} \cdot \textrm{Even} = 2k \cdot 2j = 2 (2kj) = 2m$

Here I used the commutative and associative properties of multiplication to put the result in the form 2m, where m is an arbitrary integer equal to 2kj.

Second, multiplying an odd by an even number always results in an even number:

$\textrm{Odd} \cdot \textrm{Even} = (2k + 1) \cdot 2j = 4kj + 2j$

$= 2(2kj + j) = 2n$

Finally, multiplying two odd numbers always results in an odd number:

$\textrm{Odd} \cdot \textrm{Odd} = (2k + 1) \cdot (2j + 1) = 4kj + 2k + 2j + 1$

$= 2(2kj + k + j) + 1 = 2p + 1$

To summarize:

Even $\cdot$ Even = Even
Odd $\cdot$ Odd = Odd
Odd $\cdot$ Even = Even

Prime numbers

Now that we’re familiar with factors and multiples, let’s explore the most central type of objects in number theory called prime numbers.

Let’s think about the number of possible factors of a particular natural number. Zero has infinitely many factors because $n \cdot 0 = 0$ for any natural number n (in other words, the set of factors of 0 is the set of all natural numbers). And 1 has a single factor: itself. With the notation I introduced earlier, we can say:

$\textrm{F}(0) = \mathbb{N}$

$\textrm{F}(1) = \{1\}$

Any natural number greater than 1 has a finite number of factors and this number is always at least 2. Why? Well, because every number is divisible by 1 and by itself! Of course, the number of factors could be more than 2, as we saw in an earlier example (the number 24 has 8 factors).

In this context, prime numbers are defined as those natural numbers which have exactly two factors: no more, no less. These two factors are always 1 and the number itself.

Well, this automatically excludes 0 (because it has infinitely many factors) and 1 (because it has only one factor). What about 2? It’s the first natural number after 1, so it can’t have any other factors besides itself and 1. Which means we just discovered the first prime number!

And here are the first twelve of them (verify for yourself):

$\mathbb{P} = \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ...\}$

I used blackboard bold $\mathbb{P}$

to stand for the set of all prime numbers. This notation is in spirit of using $\mathbb{N}$

and $\mathbb{Z}$

for natural numbers and integers (though it’s not necessarily as common).

In the same context, numbers greater than 1 that aren’t prime are called composite numbers. The first few composite numbers are:

$\{ 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22... \}$

Notice how prime and composite numbers complement each other in a similar way to how even and odd numbers complement each other.

Prime factorization of composite numbers

Consider the factors of the number 35:

$\textrm{F}(35) = \{1, 5, 7, 35\}$

Besides the trivial factors 1 and 35, the remaining two factors, 5 and 7, are both prime numbers. If we wanted to write 35 as a product of two factors, we have exactly two choices:

$1 \cdot 35$

$5 \cdot 7$

Notice that the second product consists of only prime factors. Now compare this to the factors of 24 and the four product pairs we saw earlier:

$\textrm{F}(24) = \{1, 2, 3, 4, 6, 8, 12, 24\}$

$1 \cdot 24$

$2 \cdot 12$

$3 \cdot 8$

$4 \cdot 6$

Of all nontrivial factors here, only 2 and 3 are prime and the remaining factors (4, 6, 8, and 12) are composite numbers. Also, notice that this time none of the products consists solely of prime factors. Then again, who is to say a factorization can only be done with two factors?

Consider the the first nontrivial product $2 \cdot 12$ . Here, the first factor is prime and the second isn’t. But we can write 12 itself as a product of two of its factors, like $12 = 3 \cdot 4$ . If we then substitute this product into the first one, we get:

$24 = 2 \cdot 12 = 2 \cdot 3 \cdot 4$

This time two of the factors are prime and only 4 isn’t. But now we can also write 4 as a product of its nontrivial factors ( $2 \cdot 2$

) and get:

$24 = 2 \cdot 3 \cdot 2 \cdot 2 = 2^3 \cdot 3$

Now our factorization finally consists only of the prime numbers 2 and 3. And we can’t factorize any further because, by definition, prime numbers don’t have any nontrivial factors!

Everything I just did is called prime factorization — the process of breaking down a composite number into its prime factors.

How it works

In short, you perform prime factorization of any composite number n in the following way.

Starting from 2, you successively divide n by every prime as many times as possible, until the result becomes 1. The number of times you divided by each prime becomes that prime’s exponent in the prime factorization. If you didn’t divide by a particular prime at all, its exponent will simply be 0. And because $p^0=1$ , we can simply omit the respective prime from the factorization. Of course, to quickly test for divisibility by a particular prime number, we can (and should) make use of the divisibility rules I showed you in my post on Euclidean division.

For a quick reference, here’s the first few prime numbers again:

$\mathbb{P} = \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ...\}$

Let’s go back to the 24 example and factorize it according to the steps I just described:

$24 \div 2 = 12$

$12 \div 2 = 6$

$6 \div 2 = 3$

$3 \div 3 = 1$

We divided by 2 three times and by 3 only once, hence the factorization $24 = 2^3 \cdot 3$

For another example, let’s consider the prime factorization of 126. First, is it divisible by 2? Well, its last digit is even, so yes: $126 \div 2 = 63$ . Is 63 also divisible by 2? No, but according to our divisibility rules it is divisible by 3 and $63 \div 3 = 21$ . Well, let me cut to the chase and perform the full factorization:

$126 \div 2 = 63$

$63 \div 3 = 21$

$21 \div 3 = 7$

$7 \div 7 = 1$

Thus, we get the prime factorization:

$126 = 2 \cdot 3^2 \cdot 7$

Here’s two more examples, without going through the steps:

$2288 = 2^4 \cdot 11 \cdot 13$

$19125 = 3^2 \cdot 5^3 \cdot 17$

The fundamental theorem of arithmetic

Under the addition operation, you can think of the number 1 as the building block of all numbers. Starting from 0, you can add 1 to it a sufficient number of times to obtain any natural number.

Is there a number with a similar role under multiplication? Not really. However, there is a set of numbers which are the building blocks of all numbers: $\mathbb{P}$ . That’s right, this is what the fundamental theorem of arithmetic is about. It says that any composite number n can be expressed as a unique product of prime numbers in the form:

$n = p_0^{e_0} \cdot p_1^{e_1} \cdot p_2^{e_2} ...$

Here $p_0$

is the first prime number (2), $p_1$

is the second prime number (3), and so on. And the values $e_0$

, $e_1$

, … are the respective exponents to which the prime factors are raised. If a particular prime $p_i$

isn’t a factor of the respective composite number, its exponent $e_i$

is simply 0.

This means that we can think of prime factorization as writing a composite number as an infinite product of prime numbers, where only finitely many of them will have non-zero exponents (unique for each natural number). For example, the prime factorization $2288 = 2^4 \cdot 11 \cdot 13$ actually looks like:

$2288 = 2^4 \cdot 3^0 \cdot 5^0 \cdot 7^0 \cdot 11^1 \cdot 13^1 \cdot 17^0...$

Of course, in practice we only want to write the primes with non-zero exponents, since the others don’t have any contribution to the final product.

The fundamental theorem of arithmetic is one of those theorems whose formal proof I don’t want to overwhelm you with. Both to keep the post from getting too long and because the theorem is quite intuitive. But there’s another thing I haven’t addressed yet that you might be wondering about.

How many prime numbers are there?

Since the fundamental theorem of arithmetic tells us that prime numbers are the building blocks of all composite numbers, a question that arises naturally is: how many of them are there? Are there infinitely many primes or can every composite number be formed by a product of some privileged finite subset of natural numbers which we call “prime”?

Well, it turns out there are, in fact, infinitely many prime numbers. The proof is surprisingly straightforward and I want to share with you a nice and short Numberphile video on this topic which will also give you a better intuition for prime numbers in general:

Common factors and multiples between numbers

In this final section, I want to introduce two other important concepts from number theory that connect everything we did so far.

I want to talk about the sets of common factors and common multiples between two or more numbers, as well two privileged members of those sets: the greatest common factor (GCF) and the least common multiple (LCM). I’m going to show you how to calculate these using prime factorization. This isn’t an efficient way of doing it but it gives a good conceptual explanation. In my post on modular arithmetic, I’m going to show you a much more efficient way of calculating GCF and LCM for any set of numbers.

Finally, related to GCF, I’m also going to introduce the concept of coprime numbers. Namely, numbers whose greatest common factor is equal to 1.

Common factors and the GCF

Say you take two arbitrary natural numbers m and n, along with their factors F(m) and F(n). Now let’s ask the question: do they share any common factors? Well, since 1 is a factor of every number, we know they will share at least that. But they can share more. For example, consider the factors of 12 and 24:

$\textrm{F}(12) =\{1, 2, 3, 4, 6, 12\}$

$\textrm{F}(24)=\{1, 2, 3, 4, 6, 8 ,12, 24\}$

You see that every factor of 12 is also a factor of 24 but 8 and 24 are only factors of 24. With the following notation, we can write the common factors as a set too:

$\textrm{CF}(12, 24)=\{1, 2, 3, 4, 6, 12\}$

In general, we can use $\cap$

to denote the intersection between two sets (all elements they have in common) and define the set of common factors of the arbitrary numbers m and n as:

$\textrm{CF}(m, n) = \textrm{F}(m) \cap \textrm{F}(n)$

Here’s another example:

$\textrm{CF}(32, 156) = \{1, 2, 4\}$

It’s easy to generalize the notion of common factors to more than two numbers. If we have k different numbers, their common factors are:

$\textrm{CF}(n_1, n_2, ..., n_k) = \textrm{F}(n_1) \cap \textrm{F}(n_2) \cap ... \cap \textrm{F}(n_k)$

For example:

$\textrm{CF}(48, 240, 840) = \{ 1, 2, 3, 4, 6, 8, 12, 24 \}$

$\textrm{CF}(2520, 1680, 180) = \{1,2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 \}$

$\textrm{CF}(28, 636, 248, 484) = \{1, 2, 4\}$

Here’s some visual aid for the first example:

All factors of the numbers 48, 240, and 840 listed, with the common ones highlighted — The factors of 48, 240, and 840, with the common ones marked in red

Of all common factors between two or more numbers, the largest has a special place in number theory and it’s called the greatest common factor (GCF). Sometimes you’ll also come across the term greatest common divisor (GCD).

Going back to the examples above, the respective greatest common factors are:

$\textrm{GCF}(12, 24) = 12$

$\textrm{GCF}(32, 156) = 4$

$\textrm{GCF}(48, 240, 840) = 24$

$\textrm{GCF}(2520, 1680, 180) = 60$

$\textrm{GCF}(28, 636, 248, 484) = 4$

As an exercise, try to find the GCF of some arbitrary numbers of your choosing.

Coprime numbers

We say that two numbers are coprime (mutually prime) if their greatest common factor is equal to 1. This means that, if two numbers are coprime, there is no prime or composite number that divides both of them evenly.

Any pair of prime numbers is coprime, but composite numbers can be coprime too. For example, 10 and 21 are both composite but the only factor they share is 1:

$\textrm{F}(10)=\{1,2,5,10\}$

$\textrm{F}(21)=\{1,3,7,21\}$

$\textrm{GCF}(10, 21) = 1$

We can naturally generalize this concept to more than two numbers. For example, 4, 9, and 13 are coprime because their respective sets of factors have only the number 1 in common:

$\textrm{F}(4) = \{1, 2, 4\}$

$\textrm{F}(9) = \{1, 3, 9\}$

$\textrm{F}(13) = \{1, 13\}$

$\textrm{GCF}(4, 9, 13) = 1$

Simple!

Finding GCF with prime factorization

In general, there are many techniques for finding all factors of a number. But none of them are fast enough to do by hand for arbitrary numbers (so you’ll typically need the help of computers).

Luckily, there are other ways to directly find the GCF between two numbers, m and n, that don’t require listing all of their factors. Here I want to show you one of them that only requires prime factorization. The idea is very simple: factorize the numbers and, for each common prime factor, take the one with the smallest exponent — their product is equal to GCF(m, n).

The general formula for finding the greatest common factor between two numbers

Here again $p_0$ , $p_1$ , $p_3$ , …, $p_k$ correspond to the prime numbers 2, 3, 5, …, and so on. The exponents $e_k$ and $f_k$ are the powers to which the corresponding primes are raised for m and n. Finally, the min(a, b) function simply returns the smaller of the numbers a and b (and returns either if they’re equal).

Let’s look at the example GCF(540, 13200):

$540 = 2^2 \cdot 3^3 \cdot 5$

$13200 = 2^4 \cdot 3 \cdot 5^2 \cdot 11$

$\textrm{GCF}(540, 13200) = 2^{min(2, 4)} \cdot 3^{min(3, 1)} \cdot 5^{min(1, 2)} \cdot 11^{min(0, 1)}$

$= 2^2 \cdot 3^1 \cdot 5^1 \cdot 11^0 = 60$

Remember that prime numbers that don’t form a particular number are implicitly there with exponents of 0 but we don’t bother writing them out.

For an example involving three numbers, let’s go back to GCF(48, 240, 840) from above:

$48 = 2^4 \cdot 3$

$240 = 2^4 \cdot 3 \cdot 5$

$840 = 2^3 \cdot 3 \cdot 5 \cdot 7$

$\textrm{GCF}(48, 240, 840) = 2^{min(4, 4, 3)} \cdot 3^{min(1, 1, 1)} \cdot 5^{min(0, 1, 1)} \cdot 7^{min(0, 0, 1)}$

$=2^3 \cdot 3^1 \cdot 5^0 \cdot 7^0 = 24$

The intuition for why this method works is that, as long as you take a common subset of the numbers’ prime factors, their product is guaranteed to be a factor of each number. So, taking the product of as many common prime factors as possible guarantees the largest possible common factor. Which is exactly what we achieve when we take the smallest power of each participating prime factor.

Common multiples and the LCM

So far, so good. Now what about the common multiples between two numbers? Well, with a similar notation, we can express the set of common multiples of two arbitrary integers m and n as the intersection between their sets of multiples:

$\textrm{CM}(m, n) = m\mathbb{Z} \cap n\mathbb{Z}$

Because $m\mathbb{Z}$

and $n\mathbb{Z}$

have infinitely many elements, a natural question to ask is if the same holds for CM(m, n). And the answer is yes. First, notice that, by definition, $m \cdot n$

is a multiple of both numbers:

$m \mid m \cdot n$

$n \mid m \cdot n$

And also notice that the same holds for any integer multiple (k) of $m \cdot n$

$m \mid k(m \cdot n)$

$n \mid k(m \cdot n)$

To consider an example, let’s take the numbers 2 and 3 for m and n. Here’s the first few common multiples:

$\textrm{CM}(2, 3) = \{ 6, 12, 18, 24, 30, 36, ... \}$

Now, you might be left with the impression that the common multiples of two numbers are just the set of all multiples of their product. And in the above example this seems to be true:

$\textrm{CM}(2, 3) = 6\mathbb{Z}_+$

However, in the general case, CM(m, n) can have more elements besides $mn\mathbb{Z}_+$

, like in this example:

$\textrm{CM}(6, 8) = \{ 24, 48, 72, 96, 120, 144, ... \}$

The product $6 \cdot 8$

is 48, but the set of common multiples of 6 and 8 starts from 24 and the remaining multiples (including 48) are the multiples of 24:

$\textrm{CM}(6, 8) = 24\mathbb{Z}_+$

This brings me to the idea of the least common multiple (LCM). This concept is analogous to the greatest common factor but this time we’re taking the smallest common multiple of the two numbers. Then, the set of common multiples of two numbers is just the set of all multiples of their LCM:

$\textrm{CM}(m, n) = \textrm{LCM}(m,n) \mathbb{Z}_+$

Now let’s look at a general method for finding common multiples between any numbers.

Finding LCM with prime factorization

Here the idea is exactly the same as finding the greatest common factor. The only difference is that we take the largest exponent for each common prime factor. Which means we just have to replace the min(a, b) function with the max(a, b) function, which returns the largest of a and b.

The general formula for finding the least common multiple between two numbers

For comparison, let’s look at the two examples from the GCF section above. First, to calculate LCM(540, 13200):

$540 = 2^2 \cdot 3^3 \cdot 5$

$13200 = 2^4 \cdot 3 \cdot 5^2 \cdot 11$

$\textrm{LCM}(540, 13200) = 2^{max(2, 4)} \cdot 3^{max(3, 1)} \cdot 5^{max(1, 2)} \cdot 11^{max(0, 1)}$

$= 2^4 \cdot 3^3 \cdot 5^2 \cdot 11^1 = 118800$

And to calculate LCM(48, 240, 840):

$48 = 2^4 \cdot 3$

$240 = 2^4 \cdot 3 \cdot 5$

$840 = 2^3 \cdot 3 \cdot 5 \cdot 7$

$\textrm{LCM}(48, 240, 840) = 2^4 \cdot 3 \cdot 5 \cdot 7 = 1680$

And that’s all there is to it!

The intuition behind this procedure is very similar to that of finding GCF with prime factorization. Taking the largest exponent guarantees that each of the numbers will participate in the product representing LCM. Multiplying that by any extra number(s) will keep it a common multiple but will also make it larger.

Summary

My goal with this post was to show you the big picture of number theory, one of the most important branches of mathematics. Still, I didn’t get a chance to get to the overview of some important parts of it which I decided to leave for separate posts. Namely, the topics of numeral systems and modular arithmetic, even though I had initially planned to include both here. Instead, I decided to make this post about the building blocks of number theory. The concepts that you can’t do without in the field (and probably in most of mathematics).

We first talked about factors and multiples of numbers. Every positive integer has an associated finite set of numbers called its factors. Factors come in pairs and their product is the original number. And every positive integer has an associated infinite set of numbers called its multiples. Those are the results of multiplying the original number with every integer. We looked at the symmetric relationship between factors and multiples which can be compactly illustrated with the notation $a \mid b$ that reads “a is a factor of b”, or equivalently “b is a multiple of a”.

The set multiples of the number 2 has a special name: even numbers. And the complementary set of “not even” numbers is called the odd numbers. As a warm-up for modular arithmetic, I showed you a few patterns for addition and multiplication between the two sets.

Then, we talked about the prime numbers, which are the building blocks of all integers under multiplication. Those are the numbers whose set of factors consist of exactly two elements: the number 1 and the number itself. We also talked about the complementary set of composite numbers, which are simply the numbers that aren’t prime. And we talked about prime factorization of composite numbers, as well as the fundamental theorem of arithmetic. The latter states that every composite number has a unique prime factorization.

Finally, we talked about common factors and multiples between two or more numbers. Which, as their name suggests, is simply the intersection between the respective sets of factors and multiples of the individual numbers. And we also talked about the special members of these sets, called the greatest common factor (GFC) and the least common multiple (LCM).

I’m sure many of you are already familiar with most of these topics. Probably even from your childhood. But I think it doesn’t hurt to go over old topics every once in a while, does it? I know writing this post was useful for me on that front. And, for those of you who are new to some of these topics, you’ll appreciate their real utility in future posts where we use them as building blocks for more advanced concepts in number theory.

Bonus section

This is an optional section for those of you whose curiosity was sparked by the topics I introduced in today’s post. I want to share some really nice videos from Numberphile I’ve hand-picked for you. Numberphile’s YouTube channel’s main focus has been number theory from the beginning and I’ve selected a few videos that’ll give you a broader sense of what number theory is about and what number theorists are typically busy (and have fun) with.

Most of them are about 5 minutes long and they’re very easy to follow. So, enjoy!

Interesting numbers

All numbers are interesting in their own unique way. You can probably discover interesting numbers yourself if you play around with some random integers’ properties. But here I want to show you a few famous classes of numbers with some cool and fun properties.

The first class is the set of so-called perfect numbers. These are numbers whose sum of factors (except the number itself) is equal to the number itself!

Then there’s the amicable (friendly) numbers. These are pairs of numbers which are, in a way, mutually perfect. If two numbers, a and b are amicable, then the sum of factors of a is equal to b and the sum of factors of b is equal to a! Like with perfect numbers, we’re excluding the numbers a and b from the set of factors.

Next, let’s look at the Lucas–Carmichael numbers. If a number a is of this class, this means that it’s a composite number and any of its prime factors incremented by 1 will be a factor of the number incremented by 1. That is, if p is a prime factor of a, then (p + 1) is a factor of (a + 1).

The next video is about highly composite numbers. A highly composite number a is a positive integer with more factors than any positive integer less than a.

A few fun number classes

The next four videos are about numbers that are a bit more playful. The properties that make them special only hold in the decimal numeral system we use most frequently. Though their equivalents exist in other number bases as well. If you don’t know much about numeral systems, don’t worry about this remark too much and just enjoy the videos. You’ll know all about this topic in my next post.

Here come the narcissistic numbers! Say a number b consists of n digits. We say that b is narcissistic if the sum of its digits, each raised to the power of n, is equal to the number itself!

Next, let’s look at vampire numbers. These are composite numbers which always have an even number of digits n. What’s special about them is that, among their factors, there’s at least one pair whose number of digits is exactly half of n. Аnd, together, the digits of the two numbers consist of all the digits of the original number.

Next in line are the so-called Smith numbers. Every Smith number b has the sum of its digits equal to the sum of digits of its prime factors.

There are several competing meanings for what the term evil numbers refers to in number theory. Here I want to show you a video about “the most evil number” called Belphegor’s prime which also touches upon other “evil” numbers. As you’ll see, these numbers are really cool rather than evil.

Famous theorems and conjectures

And here I want to acquaint you with a few famous and important theorems and conjectures in number theory. In mathematics, a theorem is a statement which has been proven. Remember that we already looked at the most important theorem in number theory called the fundamental theorem of arithmetic.

On the other hand, a conjecture is a statement which is widely believed to be true but which nobody has been able to prove (or disprove) yet. There are many conjectures in number theory and this isn’t surprising. Theorems in this field are generally known for being very easy to explain but extremely difficult to prove. Many of them have proofs spanning hundreds of pages and are the result of the joint effort of many mathematicians. An effort that sometimes takes centuries!

The first theorem is called Fermat’s last theorem. It is very famous and there’s a good chance you might have heard about it even in non-mathematical contexts. In short, it states that there is no set of positive integers a, b, and c that satisfy the equation $a^n + b^n = c^n$ for any power n greater than or equal to 3.

Next, I want to show you the Collatz conjecture. Start with any number a. If a is even, divide it by 2 and call the result b. If it’s odd, b is obtained by $3a + 1$ instead. Then apply the same rule on b and call the result c. Repeat this indefinitely. The conjecture says that, regardless of your starting number, you will eventually reach the number 1 and start oscillating between 1 and 4.

Now let’s watch a video on the so-called Mersenne primes. These are a prime numbers in the form $2^n - 1$ for some positive integer n and have a close relationship with perfect numbers. Namely, there is a theorem which says that all even perfect numbers have a Mersenne factor.

Finally, let’s watch a really nice video that focuses on theorems and conjectures related to gaps between consecutive prime numbers. You will learn about the so-called twin, cousin, and sexy primes, which are primes separated by 2, 4, and 6 numbers, respectively. And you will learn about their corresponding conjectures, starting with the twin prime conjecture.