Skip to content
Tutorials Center
My learning

Topics

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

  1. 1 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.
  2. 2 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.
  3. 3 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.
  4. 4 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

  1. 5 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.
  2. 6 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.
  3. 7 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.
  4. 8 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.
  5. 9 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.
  6. 10 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.
  7. 11 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

  1. 12 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.
  2. 13 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.
  3. 14 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.
  4. 15 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

  1. 16 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.
  2. 17 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.
  3. 18 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.
  4. 19 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

  1. 20 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.
  2. 21 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.
  3. 22 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.
  4. 23 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

  1. 24 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.
  2. 25 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.
  3. 26 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

  1. 27 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.
  2. 28 Legendre and Jacobi Symbols Compute Legendre and Jacobi symbols with quadratic reciprocity, without factoring, and use them in the Solovay-Strassen primality test.
  3. 29 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

  1. 30 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.
  2. 31 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.
  3. 32 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.
  4. 33 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

  1. 34 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.
  2. 35 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.
  3. 36 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.
  4. 37 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.