Number Theory

Number theory is the study of the integers — the plain, familiar whole numbers $\ldots, -2, -1, 0, 1, 2, \ldots$ — and the astonishingly deep patterns hidden inside them. It asks questions a curious child might ask: Which numbers divide evenly into others? Why do some numbers refuse to be broken apart? Is there any order to where the primes appear? And yet those innocent questions lead to some of the hardest and most beautiful mathematics ever done. Carl Friedrich Gauss called it "the queen of mathematics" because it demands nothing but whole numbers to state a problem, yet the answers can require the full arsenal of modern math.

What makes number theory matter far beyond the classroom is that it turned out to be the secret engine of the digital age. Every time you buy something online, log in securely, or send an encrypted message, prime numbers and modular arithmetic — ideas Euclid wrote about more than two thousand years ago — are quietly protecting you. The gap between "pure curiosity" and "runs the internet" is nowhere shorter than here. This branch will take you from the simple idea of one number dividing another all the way to the machinery behind RSA encryption, one clear step at a time.

Learning Objectives

• Determine when one integer divides another and apply divisibility rules quickly.
• Identify prime numbers and understand why primes are the building blocks of arithmetic.
• State and use the Fundamental Theorem of Arithmetic to factor integers uniquely.
• Compute the greatest common divisor and least common multiple, including via the Euclidean algorithm.
• Perform arithmetic "on a clock" using modular arithmetic and congruences.
• Solve linear Diophantine equations and recognize when integer solutions exist.
• Convert numbers between bases (binary, decimal, hexadecimal) and understand positional notation.
• Connect these ideas to real applications such as cryptography, error detection, and computer science.

Quick Answer

Number theory studies the integers and the relationships between them, starting from a single idea: divisibility, whether one whole number goes evenly into another. From divisibility comes the notion of a prime — a number greater than $1$ divisible only by $1$ and itself — and the Fundamental Theorem of Arithmetic, which says every integer above $1$ factors into primes in exactly one way. Tools like the greatest common divisor (GCD) and least common multiple (LCM), computed efficiently by the ancient Euclidean algorithm, let us compare the divisibility structure of numbers. Modular arithmetic reframes numbers by their remainders, giving a "clock arithmetic" that underlies everything from calendars to cryptography. Diophantine equations ask which of these problems have solutions in whole numbers only, a restriction that makes them surprisingly hard. Number bases remind us that the same integer wears different clothes depending on how we group it — base $10$ for humans, base $2$ for machines. Together these topics form a tightly linked toolkit: primes build numbers, GCD and modular arithmetic reveal their inner structure, and the whole edifice powers modern secure communication.

Where It Came From

Number theory is among the oldest branches of mathematics. The Babylonians and Egyptians worked with fractions and simple divisibility, but the first systematic treatment survives in Euclid's Elements (around 300 BCE), which proves that there are infinitely many primes and describes the algorithm for the GCD that still bears his name — an algorithm you will run yourself in this branch. Around the same era, Eratosthenes gave us the "sieve" for listing primes.

The subject was transformed in the 3rd century CE by Diophantus of Alexandria, whose Arithmetica studied equations demanding whole-number solutions; his name is attached to that entire family of problems, and it was in the margin of a copy of his book that Pierre de Fermat scribbled his famous "Last Theorem" in the 1600s. The modern era began with Fermat, Leonhard Euler, and above all Gauss, whose 1801 masterwork Disquisitiones Arithmeticae introduced the language of congruences and modular arithmetic that organizes the field today. For centuries number theory was prized precisely because it seemed useless — pure thought for its own sake. That changed dramatically in 1977 when Rivest, Shamir, and Adleman built the RSA cryptosystem directly on the difficulty of factoring large numbers into primes, and the queen of mathematics suddenly became the guardian of the digital world.

Topics at a Glance

Topic	What You'll Learn	Key Concepts
Divisibility and Primes	When one integer divides another, and what makes a number prime	Divisors, divisibility rules, primes, composites, the sieve of Eratosthenes
The Fundamental Theorem of Arithmetic	Why every integer factors into primes in exactly one way	Prime factorization, uniqueness, canonical form
GCD and LCM	Finding shared and common-multiple structure between numbers	Greatest common divisor, least common multiple, Euclidean algorithm
Modular Arithmetic	Doing arithmetic with remainders on a "clock"	Congruence, modulus, residues, modular inverse
Diophantine Equations	Solving equations that require whole-number answers	Linear Diophantine equations, existence conditions, Bezout's identity
Number Bases	Representing the same integer in different positional systems	Base $10$, binary, hexadecimal, place value, base conversion

Learning Path

Real-World Applications

• Cryptography (RSA): Secure web traffic, banking, and messaging rely on the fact that multiplying two large primes is easy but factoring their product is effectively impossible — a direct application of primes, factorization, and modular arithmetic.
• Error detection: ISBN book codes, credit-card numbers (the Luhn algorithm), and barcodes use modular arithmetic checksums to catch typos automatically.
• Computer science: Every computer stores data in binary (base $2$) and programmers read memory in hexadecimal (base $16$); hashing and array indexing use the modulo operation constantly.
• Scheduling and calendars: Working out days of the week, leap years, and repeating events is modular arithmetic in disguise — figuring out what happens every $7$ days is arithmetic modulo $7$.
• Music and gears: LCM tells you when two rhythmic cycles or two rotating gears realign; GCD helps reduce ratios and fractions to simplest form.

Key Terms

Term	Definition	Related Concept
Divisor	An integer that divides another with no remainder	Divisibility
Prime	An integer greater than $1$ whose only divisors are $1$ and itself	Divisibility and Primes
Composite	An integer greater than $1$ that is not prime	Prime factorization
Prime factorization	Writing an integer as a product of primes	Fundamental Theorem of Arithmetic
GCD	The largest integer dividing two given integers	Euclidean algorithm
LCM	The smallest positive integer divisible by two given integers	GCD and LCM
Congruence	Two integers having the same remainder modulo $n$	Modular arithmetic
Modulus	The number you divide by when taking remainders	Modular arithmetic
Diophantine equation	An equation whose solutions must be integers	Bezout's identity
Base (radix)	The number of digits a positional system uses	Number bases

Quick Revision

• Number theory studies the integers; divisibility is its foundational idea.
• A prime has exactly two positive divisors; primes are the atoms of arithmetic.
• The Fundamental Theorem of Arithmetic guarantees unique prime factorization.
• The Euclidean algorithm finds the GCD fast; $\gcd(a,b) \times \operatorname{lcm}(a,b) = a \times b$.
• Modular arithmetic works with remainders: $a \equiv b \pmod{n}$ means $n$ divides $a - b$.
• A linear Diophantine equation $ax + by = c$ has integer solutions exactly when $\gcd(a,b)$ divides $c$.
• The same integer has different representations in different bases; humans use base $10$, computers base $2$.
• These ideas combine to power cryptography, error detection, and computing.

Related Topics

Prerequisites

• Algebra — comfort with variables, equations, and basic manipulation.

Related Topics

• Discrete Mathematics — logic, sets, and combinatorics that share number theory's rigor.
• Statistics and Probability — counting and randomness that intersect with number-theoretic ideas.

Next Topics

• Linear Algebra — extends structured, systematic reasoning to vectors and matrices.
• Financial Mathematics — applies modular and computational ideas to real-world finance.