maths.free › Number Theory

Number Theory

Primes, divisibility, gcd, modular arithmetic and sequences.

Lessons

Introductory Prime factorisation Every integer is a product of primes in exactly one way. prime factorization of 360 Introductory Prime numbers Testing for primality by trial division up to the square root. is 97 prime Introductory GCD and LCM Euclid's algorithm and the identity gcd × lcm = a × b. gcd(48, 18) Core Modular arithmetic Remainders, congruences, fast powers and modular inverses. 3^100 mod 7 Introductory Divisors Counting and listing divisors from the prime factorisation. divisors of 36 Core Sequences Fibonacci, recurrences and closed forms. fib(20) Introductory Number bases Converting between decimal, binary, octal and hexadecimal. 255 to binary Core Diophantine equations Integer solutions: linear equations via Bézout, Pythagorean triples, Fermat. gcd(12, 18) Core Fermat's little theorem and Euler's theorem aᵖ⁻¹ ≡ 1 (mod p), the totient, and fast modular arithmetic. 2^100 mod 13 Advanced RSA: cryptography from number theory Public keys from two primes, and why factoring is the lock. inverse of 17 mod 3120

The mathematics of whole numbers. Some of the oldest problems and the newest cryptography live here: factor a number into primes, run Euclid's algorithm, compute huge powers modulo a prime without ever writing the power down.

More lessons

Real Number Systems and Number Theory

Prime and Composite Numbers The Integers Order of Operations Rational Numbers Irrational Numbers Real Numbers Clock Arithmetic Exponents Scientific Notation Arithmetic Sequences Geometric Sequences

Number Representation and Calculation

Hindu-Arabic Positional System Early Numeration Systems Converting with Base Systems Addition and Subtraction in Base Systems Multiplication and Division in Base Systems

Divisibility

Number theory Fundamental theorem of arithmetic Euclidean algorithm Prime number Composite number Divisor function Perfect number Sieve of Eratosthenes Bézout's identity

Congruences

Fermat's little theorem Euler's theorem Chinese remainder theorem Euler's totient function Primitive root modulo n Quadratic residue Quadratic reciprocity Legendre symbol Multiplicative order Wilson's theorem

Deeper water

Diophantine equation Pell's equation Continued fraction Prime number theorem Riemann zeta function Dirichlet's theorem on arithmetic progressions Elliptic curve Algebraic number theory Fermat's Last Theorem RSA (cryptosystem)Mersenne prime Twin prime

Some of these lessons are adapted from open texts: OpenStax Contemporary Mathematics, Wikipedia. Each lesson page names its source and licence.

Symbols used here

Tap any symbol for the full definition, a picture, and what every letter in it means.

Questions people ask

Why are primes so important?

Every integer factors into primes in exactly one way, so primes are the atoms of multiplication. Cryptography relies on that factoring being easy to state and hard to do.

How do I tell whether a big number is prime?

Trial division up to the square root works for small numbers. For large ones, probabilistic tests (Miller-Rabin) give an answer that is wrong with negligible probability, and deterministic tests (AKS) exist but are slower.

Have a problem of your own?
Type it or draw it on the solver page: every step, a picture, the answer hidden until you ask. Solve →

Other branches

＋ Arithmetic 𝑥 Algebra △ Geometry ∿ Trigonometry ƒ Precalculus σ Statistics & Probability ⊢ Discrete Math & Logic ∫ Calculus ⊞ Linear Algebra ẏ Differential Equations ∇ Multivariable Calculus ε Real Analysis ⋔ Combinatorics & Graph Theory ∈ Set Theory & Logic 𝔾 Abstract Algebra 𝑃 Probability Theory ≈ Numerical Methods ℂ Complex Analysis ◎ Topology μ Measure Theory ‖·‖ Functional Analysis κ Differential Geometry π₁ Algebraic Topology → Category Theory ∂ Partial Differential Equations ≋ Fluid Dynamics ∞ Frontiers