Selected Classical Theorems in Number Theory

Introduction: why these theorems matter

students, number theory is the study of whole numbers, and some of its biggest ideas come from classical theorems—results that have stood the test of time because they explain patterns that keep appearing again and again 🔍. In this lesson, you will explore several famous theorems that form the backbone of advanced number theory. These results help mathematicians answer questions such as: Which numbers are prime? When do equations have whole-number solutions? How can we tell whether one number divides another? Why do remainders behave so predictably?

By the end of this lesson, you will be able to explain the main ideas behind selected classical theorems, use them in reasoning and calculations, and connect them to larger themes in advanced number theory. You will also see how these theorems are useful in problem solving, proofs, and student presentations 🎓.

Euclid’s theorem: there are infinitely many primes

One of the most important classical theorems is Euclid’s theorem, which says there are infinitely many prime numbers. A prime number is a whole number greater than $1$ that has exactly two positive divisors: $1$ and itself.

Why is this theorem so important? Because prime numbers are like the “building blocks” of whole numbers. Every whole number greater than $1$ can be written as a product of primes in a unique way, which is called the Fundamental Theorem of Arithmetic.

Here is the classic idea behind Euclid’s proof. Suppose, just for the sake of argument, that there are only finitely many primes: $p_1, p_2, \dots, p_n$. Now consider the number

$$N = p_1p_2\cdots p_n + 1.$$

When you divide $N$ by any listed prime $p_i$, the remainder is $1$. That means none of the primes in the list divides $N$. So either $N$ is prime itself, or it has a prime factor not in the list. In both cases, the original list was incomplete. This contradiction shows that there must be infinitely many primes.

This theorem is a great example of proof by contradiction. It also shows a major theme in number theory: sometimes the best way to understand numbers is to assume the opposite of what you want to prove and look for a contradiction.

For example, if someone claims the primes stop at $29$, Euclid’s idea shows why that cannot be true. The number $2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23\cdot 29 + 1$ is not divisible by any of those primes, so new prime factors must exist.

The Division Algorithm and the Euclidean Algorithm

Another classical result is the Division Algorithm. It states that for integers $a$ and positive integer $b$, there exist unique integers $q$ and $r$ such that

$$a = bq + r, \qquad 0 \le r < b.$$

Here, $q$ is the quotient and $r$ is the remainder. This theorem is not just about long division; it is a foundation for modular arithmetic, divisibility, and many proofs in number theory.

The Euclidean Algorithm uses repeated division to find the greatest common divisor, written as $\gcd(a,b)$. The key idea is

$$\gcd(a,b) = \gcd(b,r),$$

where $r$ is the remainder when $a$ is divided by $b$.

Example: find $\gcd(252,198)$.

First,

$$252 = 198\cdot 1 + 54.$$

So $\gcd(252,198) = \gcd(198,54)$.

Next,

$$198 = 54\cdot 3 + 36,$$

so $\gcd(198,54) = \gcd(54,36)$.

Then,

$$54 = 36\cdot 1 + 18,$$

so $\gcd(54,36) = \gcd(36,18)$.

Finally,

$$36 = 18\cdot 2 + 0.$$

Therefore, $\gcd(252,198)=18$.

This algorithm is classical because it is ancient, efficient, and still used today in computer science and cryptography 🔐. It also connects to linear combinations of integers: if $d = \gcd(a,b)$, then $d$ can be written as

$$d = ax + by$$

for some integers $x$ and $y$. This idea is called Bézout’s identity.

Bézout’s identity and linear combinations

Bézout’s identity says that for integers $a$ and $b$, their greatest common divisor $d = \gcd(a,b)$ can be expressed as a linear combination of $a$ and $b$:

$$d = ax + by$$

for some integers $x$ and $y$.

This theorem is powerful because it turns a question about divisibility into a question about algebraic expressions. It also explains why the Euclidean Algorithm works: the repeated remainders eventually lead to the greatest common divisor, and then working backward gives the coefficients $x$ and $y$.

Example: for $a=30$ and $b=18$, we know $\gcd(30,18)=6$. One linear combination is

$$6 = 30(2) + 18(-3).$$

Check it:

$$30\cdot 2 + 18\cdot (-3) = 60 - 54 = 6.$$

Bézout’s identity is especially useful for solving equations like

$$ax + by = c.$$

Such equations have integer solutions only when $\gcd(a,b)$ divides $c$. For example, the equation

$$6x + 15y = 9$$

has integer solutions because $\gcd(6,15)=3$ and $3$ divides $9$. But

$$6x + 15y = 8$$

has no integer solutions because $3$ does not divide $8$.

This theorem fits into advanced number theory because it is one of the main tools for studying Diophantine equations, which are equations where integer solutions are sought.

Fermat’s little theorem and modular arithmetic

A very famous classical theorem is Fermat’s little theorem. If $p$ is prime and $a$ is not divisible by $p$, then

$$a^{p-1} \equiv 1 \pmod p.$$

A related form is

$$a^p \equiv a \pmod p.$$

These statements mean that when you divide the two sides by $p$, they leave the same remainder.

Example: let $p=5$ and $a=2$. Then

$$2^4 = 16 \equiv 1 \pmod 5,$$

because $16$ leaves remainder $1$ when divided by $5$.

Why is this theorem useful? It gives a fast way to simplify large powers. For instance, to find the remainder of $7^{100}$ when divided by $13$, Fermat’s little theorem tells us that

$$7^{12} \equiv 1 \pmod{13},$$

since $13$ is prime and $13$ does not divide $7$. Then

$$7^{100} = 7^{96}\cdot 7^4 = (7^{12})^8\cdot 7^4 \equiv 1^8\cdot 7^4 \pmod{13}.$$

So we only need to compute $7^4$ modulo $13$:

$$7^2 = 49 \equiv 10 \pmod{13},$$

$$7^4 \equiv 10^2 = 100 \equiv 9 \pmod{13}.$$

Therefore,

$$7^{100} \equiv 9 \pmod{13}.$$

This theorem is a bridge to modern number theory because it is central in modular arithmetic and has applications in public-key cryptography, especially systems that rely on large primes.

The Chinese Remainder Theorem

The Chinese Remainder Theorem is another classical result with a huge role in advanced number theory. It says that if the moduli are pairwise coprime, then a system of congruences has a unique solution modulo the product of the moduli.

For example, solve

$$x \equiv 2 \pmod 3,$$

$$x \equiv 3 \pmod 5,$$

$$x \equiv 2 \pmod 7.$$

We look for a number that leaves remainders $2$, $3$, and $2$ when divided by $3$, $5$, and $7$, respectively. One solution is $x=23$ because

$$23 \equiv 2 \pmod 3, \qquad 23 \equiv 3 \pmod 5, \qquad 23 \equiv 2 \pmod 7.$$

The theorem says that every solution differs by a multiple of

$$3\cdot 5\cdot 7 = 105.$$

So all solutions are of the form

$$x = 23 + 105k$$

for integers $k$.

This theorem matters because it allows difficult congruence problems to be broken into smaller, easier ones. It also appears in computer algorithms, error correction, and cryptography. In number theory, it shows how separate modular conditions can be combined into one consistent answer.

How these theorems connect to advanced number theory

students, these classical theorems are not isolated facts. They work together as a toolkit 🧰.

Euclid’s theorem shows the infinite nature of the prime numbers.
The Division Algorithm and Euclidean Algorithm help us compute $\gcd(a,b)$ efficiently.
Bézout’s identity connects gcds to linear combinations and solvability of equations.
Fermat’s little theorem helps with powers and modular arithmetic.
The Chinese Remainder Theorem combines several congruences into one solution.

Together, they support deeper topics such as primality testing, Diophantine equations, cryptography, and algebraic number theory. In a student presentation, you might explain one theorem, show its proof idea, then give an example of how it is used in a real problem. For instance, you could show how the Euclidean Algorithm leads to Bézout’s identity, or how Fermat’s little theorem simplifies a large power calculation.

Conclusion

Selected classical theorems are the foundation stones of advanced number theory. They show that whole numbers have surprising structure, and they give us reliable methods for proving statements, solving equations, and working with remainders. students, when you study these theorems, you are learning more than a list of facts—you are learning the language of number theory itself 📘.

These theorems also fit perfectly into Advanced Topics / Student Presentations because they are rich enough for independent exploration, yet concrete enough to support clear examples and proofs. Whether you are presenting Euclid’s theorem, using the Euclidean Algorithm, or applying the Chinese Remainder Theorem, you are working with ideas that are both classical and still important today.

Study Notes

Prime numbers are numbers greater than $1$ with exactly two positive divisors.
Euclid’s theorem proves there are infinitely many primes.
The Division Algorithm says $a = bq + r$ with $0 \le r < b$.
The Euclidean Algorithm finds $\gcd(a,b)$ by repeated division.
Bézout’s identity says $\gcd(a,b) = ax + by$ for some integers $x$ and $y$.
Fermat’s little theorem says that if $p$ is prime and $p \nmid a$, then $a^{p-1} \equiv 1 \pmod p$.
The Chinese Remainder Theorem solves compatible systems of congruences with pairwise coprime moduli.
These theorems are central tools for proofs, modular arithmetic, and solving integer equations.
Classical theorems connect directly to modern topics like cryptography and computation.