Table of Contents
Number theory is the study of whole numbers and their properties. At first glance, whole numbers (like $1,2,3,\dots$) seem simple and familiar. Number theory shows that they hide surprisingly deep patterns and questions, some of which are still unsolved today.
This chapter gives an overview of what number theory is about and why it matters. Later chapters in this part of the course will focus on specific topics: divisibility and primes, modular arithmetic, and applications such as cryptography. Here, you will see the big picture and a few central ideas that make number theory distinct.
What Number Theory Studies
Number theory focuses on integers and related objects. Some of the central questions are:
- How do integers factor into prime numbers?
- How do we measure divisibility and common factors?
- How can we solve equations where the solutions are required to be whole numbers?
- How do numbers behave when we only care about remainders (modular arithmetic)?
- How can these ideas be used in real-world systems, such as secure communication?
Some of the main themes include:
- Divisibility and primes: understanding when one integer divides another, and how every integer can be built from primes.
- Congruences (modular arithmetic): working with remainders to simplify problems and reveal structure.
- Diophantine equations: equations where we demand integer solutions, not just real or rational ones.
- Arithmetic functions and patterns: functions that take integers as inputs and reveal patterns in their factors or digits.
Why Number Theory Is Important
Number theory is important for several different reasons.
Theoretical importance
Number theory is one of the oldest branches of mathematics. Many basic concepts—primes, greatest common divisors, and mathematical induction—arose naturally while studying integers. Number theory has:
- Deep connections to algebra (through structures like groups and fields),
- Links to geometry and analysis (for example, via complex functions that encode information about primes),
- A rich history of problems that are easy to state but hard to solve, such as:
- Is there an infinite number of primes? (Yes, and there’s a classic proof.)
- Are there infinitely many twin primes (primes that differ by 2)? (Still unknown.)
- Can every even number greater than 2 be written as a sum of two primes? (Goldbach’s conjecture, still unproved.)
These questions motivate the development of new methods and theories.
Practical importance
Despite its ancient and “pure” origins, number theory is deeply practical today. Modern uses include:
- Cryptography: securing data using properties of primes, modular arithmetic, and related ideas.
- Error-correcting codes: detecting and fixing errors in communication and storage.
- Randomness and hashing: designing algorithms that spread data “evenly” using arithmetic properties of numbers.
- Computer science algorithms: fast methods for tasks like factoring, testing primality, and computing greatest common divisors.
A key theme is that many modern digital systems depend on problems that are easy to state but (as far as we know) hard to solve quickly—exactly the kind of problems number theory studies.
Types of Questions in Number Theory
Number theory asks questions that often sound very simple but lead to deep analysis. Here are a few general types.
Questions about primes
Primes are the “building blocks” of positive integers. Number theory asks questions like:
- How many primes are there up to a given size?
- How are primes spaced out along the number line?
- Can primes be found in special patterns (for example, infinitely many primes of the form $4n+1$)?
You will later study prime factorization and related ideas in detail.
Questions about divisibility and greatest common divisors
Another type of question concerns how integers divide each other:
- Given integers $a$ and $b$, what is their greatest common divisor (the largest integer that divides both)?
- When can we find integers $x$ and $y$ such that $ax+by=1$?
- Under what conditions does a certain expression always divide another?
Techniques for answering these questions are foundational for later topics such as modular arithmetic and cryptography.
Questions about remainders
Number theory often studies integers using remainders:
- If you know the remainders of a number when dividing by several smaller numbers, what can you say about the original number?
- How can you simplify large computations by working with remainders?
This viewpoint is formalized using congruences and modular arithmetic, which will be developed in its own chapter.
Questions about integer solutions (Diophantine equations)
Sometimes we are not satisfied with any kind of solution—we specifically want integer solutions, for example:
- Find integers $x$ and $y$ such that $3x+5y=1$.
- Does the equation $x^2 + y^2 = z^2$ have solutions in positive integers? (Yes: $3,4,5$ is one example.)
Equations where the solutions are required to be integers are called Diophantine equations, and they are a classic topic in number theory.
Ways of Thinking in Number Theory
Number theory is not just a collection of facts about numbers; it also uses characteristic methods of reasoning. A few that you will encounter include:
- Reasoning about divisibility: carefully tracking how factors behave when you add, subtract, or multiply integers.
- Using remainders to distinguish numbers: showing that certain equalities or equations are impossible by examining remainders.
- Using infinite sets of examples: proving that something happens infinitely often (for example, that there are infinitely many primes).
Later, in the Mathematical Proofs part of the course, you will see general proof techniques. In number theory, these techniques often appear in concrete, arithmetic settings that are easier to visualize.
How This Part of the Course Is Organized
The Number Theory section of the course focuses on three main topics, each in its own chapter:
- Divisibility and Primes
- How to formalize “$a$ divides $b$”.
- Prime numbers, prime factorization, and the structure of integers.
- Modular Arithmetic
- Working with remainders systematically.
- Congruences and arithmetic “mod $n$”.
- Applications
- How the above ideas underpin cryptography and other real-world systems.
This introductory chapter has sketched the scope and flavor of number theory. The next chapters will develop the core tools you need—divisibility, primes, and modular arithmetic—and then show how they are used in practice.