Number Theory Tutorial
Learn Number Theory step by step: 37 lessons in 9 chapters with examples, quizzes, diagrams and projects.
Start learning →
of lessons completed
Getting Started
- What Is Number Theory? Meet number theory, the study of whole numbers: primes, divisibility, congruences and their uses in cryptography. Explore patterns with Python before proving them.
- Integers and the Division Algorithm Learn the integers, the well-ordering principle and the division algorithm a = bq + r, including how Python's // and % treat negative numbers.
- Number Theory in Python Set up your Python toolbox for number theory: arbitrary-size integers, divmod, three-argument pow, the math module, and the sympy.ntheory functions to check your own code.
- Proofs in Number Theory Learn the four proof methods number theory relies on: direct proof, cases by remainder, contradiction and induction, each tested with Python before you trust it.
Divisibility and Primes
- Divisibility and Its Properties Define divisibility, prove its core rules such as transitivity and linear combinations, count divisors, and use the rules to solve problems, with runnable Python checks.
- Divisibility Tests and Why They Work Learn the divisibility rules for 2, 3, 4, 5, 8, 9, 11 and 7 or 13, see the place-value proofs behind them, and build a general test in Python.
- Prime Numbers and the Sieve of Eratosthenes Define primes and composites, test primality by trial division up to the square root, and generate all primes up to n with the Sieve of Eratosthenes in Python.
- GCD, LCM and the Euclidean Algorithm Find the greatest common divisor and least common multiple, prove why Euclid's algorithm works, count its steps, and understand coprime numbers, with Python.
- Extended Euclid and Bezout's Identity Prove Bezout's identity ax + by = gcd(a, b), compute the coefficients with the extended Euclidean algorithm, and use them to prove Euclid's lemma. Python code included.
- The Fundamental Theorem of Arithmetic Prove that every integer above 1 factors uniquely into primes, then use factorization to compute divisors, divisor counts, sums, gcd and lcm in Python.
- How Primes Are Distributed Explore how primes thin out: infinitely many primes, the prime counting function, the Prime Number Theorem, prime gaps, twin primes and Dirichlet's theorem, with Python plots.
Congruences
- Congruences: The Basics Learn congruence modulo n, its equivalence-class view, the rules for adding, subtracting and multiplying congruences, and why division needs care. With Python.
- Solving Linear Congruences Decide when ax = b (mod n) has solutions, count them, find all of them with the extended Euclidean algorithm and modular inverses, and solve systems in Python.
- Residue Systems and Euler's Totient Function Understand complete and reduced residue systems mod n, define Euler's totient function phi(n), derive its product formula, and compute it in Python.
- Fermat's Little Theorem and Euler's Theorem Prove Fermat's little theorem and Euler's generalization a^phi(n) = 1 (mod n), use them to reduce huge exponents and find inverses, and meet pseudoprimes.
Modular Arithmetic and CRT
- Modular Arithmetic in Practice Implement square-and-multiply modular exponentiation, compute modular inverses and divisions, work with the usual 10^9+7 modulus, and use modular tricks safely in code.
- The Chinese Remainder Theorem Solve systems of congruences with pairwise coprime moduli using the Chinese remainder theorem. Learn the proof, the constructive formula and how to code it.
- CRT for Non-Coprime Moduli and Garner's Algorithm Solve congruence systems whose moduli share factors, detect inconsistency with gcd, and reconstruct big integers from residues with Garner's mixed-radix algorithm.
- Wilson's Theorem and Everyday Modular Applications Prove Wilson's theorem (p-1)! = -1 (mod p), then apply modular arithmetic to ISBN and credit card check digits, day-of-week formulas, hash tables and cyclic schedules.
Primality and Factoring
- The Fermat Primality Test Use Fermat's little theorem to test whether a number is probably prime, see why liars and Carmichael numbers break the test, and code it in Python.
- The Miller-Rabin Primality Test Learn why Miller-Rabin beats the Fermat test, how strong witnesses work, which fixed bases make it deterministic, and how to generate large primes.
- Pollard's Rho Factoring Factor integers faster than trial division with Pollard's rho: the birthday paradox, Floyd cycle detection, gcd tricks, and a complete Python implementation.
- Fermat's Factorization and Pollard's p-1 Factor numbers with Fermat's difference of squares and Pollard's p-1 method, see when each one is fast or hopeless, and compare them with trial division.
Diophantine Equations
- Linear Diophantine Equations Decide when ax + by = c has integer solutions, find all of them with the extended Euclidean algorithm, and solve coin and postage problems in Python.
- Pythagorean Triples Generate every primitive Pythagorean triple with Euclid's formula, see the tree structure, count triples, and meet Fermat's last theorem for n = 4.
- Pell's Equation and Sums of Squares Solve xยฒ - Dyยฒ = 1 with continued fractions, generate infinitely many solutions, and learn which integers are sums of two squares or four squares.
Quadratic Residues
- Quadratic Residues and Euler's Criterion Learn which numbers are squares modulo a prime, count them, test membership with Euler's criterion, and take square roots when p is 3 mod 4.
- Legendre and Jacobi Symbols Compute Legendre and Jacobi symbols with quadratic reciprocity, without factoring, and use them in the Solovay-Strassen primality test.
- Tonelli-Shanks Square Roots Compute square roots modulo any odd prime with the Tonelli-Shanks algorithm, understand why it works, lift roots to prime powers, and combine them with CRT.
Cryptographic Applications
- RSA from Scratch Build RSA in plain Python: choose primes, compute keys with Euler's theorem, encrypt and decrypt, sign messages, and speed up decryption with the CRT.
- RSA Attacks and Padding See how textbook RSA breaks: deterministic and malleable ciphertexts, small exponents, shared primes and Wiener's attack, and why padding is essential.
- Diffie-Hellman and Discrete Logarithms Agree on a shared secret over a public channel with Diffie-Hellman, learn the discrete logarithm problem, and attack it with baby-step giant-step and Pohlig-Hellman.
- Elliptic Curves over Finite Fields Add points on an elliptic curve modulo a prime, multiply by scalars, count points with Hasse's bound, and run ECDH on a toy curve and on secp256k1.
Projects and Practice
- Project: A Prime Explorer Build a prime explorer in Python: sieve primes, measure gaps, count twin primes, compare pi(x) with x/ln x, and draw an Ulam spiral.
- Project: A Toy RSA Messenger Build a small RSA messenger in Python with key pairs, fingerprints, block encryption, signatures and a break-it challenge on a weak key.
- Project: A Factoring Benchmark Measure how trial division, Fermat, Pollard rho and p-1 scale with the size of the factors, plot the growth, and build a combined factoring pipeline.
- Practice: Number Theory Problem Set Ten number theory problems on primality, Diophantine equations, quadratic residues and cryptography, each with a runnable Python solution and hints.