Number Theory
The arithmetic of the integers from Euclid to modern cryptography: divisibility and the division algorithm with proofs by cases on the remainder and base representations, greatest common divisors, the Euclidean algorithm with Lamé's bound and Bézout's identity with the extended algorithm, primes and the sieve of Eratosthenes, Euclid's proof of the infinitude of the primes, the prime number theorem and the fundamental theorem of arithmetic with Hilbert's example of failed unique factorization, congruences and residue classes with divisibility tests, check digits and the day of the week, linear Diophantine equations, linear congruences and the Chinese remainder theorem, Fermat's little theorem, Euler's theorem, Wilson's theorem and fast modular exponentiation, the arithmetic functions tau, sigma, phi and mu with Möbius inversion, perfect numbers, Mersenne primes and the Lucas–Lehmer test, orders, primitive roots and indices with the periods of repeating decimals, quadratic residues, Euler's criterion, the Legendre symbol, Gauss's lemma and Fermat's theorem on sums of two squares, the law of quadratic reciprocity with Eisenstein's lattice point proof and the Jacobi symbol, primality testing with Carmichael numbers and the Miller–Rabin test, factoring by Fermat's method and Pollard's rho method, and a capstone on public-key cryptography with the Diffie–Hellman key agreement and RSA encryption and signatures, with runnable Python examples throughout.
MATH-351 Year 3 3 credits 12 lessons · 4 h 32 min ▶ Video lessons coming soon
Offered by HSM University · Mathematics & Statistics
What you'll learn
- Use the definition of divisibility and the division algorithm to prove statements about integers, including proofs by cases on the remainder, and convert numbers between bases.
- Compute greatest common divisors with the Euclidean algorithm, find Bézout coefficients with the extended algorithm, and apply Euclid’s lemma and the relation \(\gcd(a, b)\operatorname{lcm}(a, b) = ab\).
- Prove the infinitude of the primes and the fundamental theorem of arithmetic, use the sieve of Eratosthenes, and describe the distribution of primes given by the prime number theorem.
- Calculate with congruences and residue classes, determine when inverses modulo \(n\) exist, and explain divisibility tests, check digits and calendar calculations as modular arithmetic.
- Solve linear Diophantine equations and linear congruences, and solve systems of congruences with the Chinese remainder theorem, including moduli that are not coprime.
- Prove and apply Fermat’s little theorem, Euler’s theorem and Wilson’s theorem, and compute large modular powers with square-and-multiply.
- Evaluate the multiplicative functions \(\tau\), \(\sigma\), \(\varphi\) and \(\mu\) from prime factorizations, apply Möbius inversion, and characterize the even perfect numbers.
- Compute orders modulo \(n\), find primitive roots and indices modulo a prime, and use them to solve power congruences and explain repeating decimals.
- Identify quadratic residues, evaluate Legendre symbols with Euler’s criterion, Gauss’s lemma and the supplementary laws, and decide which primes are sums of two squares.
- State and prove the law of quadratic reciprocity by Eisenstein’s lattice point argument, and evaluate Legendre and Jacobi symbols efficiently.
- Explain the Fermat and Miller–Rabin primality tests and Carmichael numbers, and factor integers with Fermat’s method and Pollard’s rho method.
- Describe and carry out the Diffie–Hellman key agreement and RSA encryption and signatures, prove that RSA decryption is correct, and explain what their security depends on.
Course content
12 lessons · 4 h 32 min total · final exam
- 1 Divisibility and the division algorithm 23 min · quiz
- 2 The Euclidean algorithm and Bézout’s identity 21 min · quiz
- 3 Primes and unique factorization 23 min · quiz
- 4 Congruences and modular arithmetic 21 min · quiz
- 5 Linear congruences and the Chinese remainder theorem 22 min · quiz
- 6 Fermat’s little theorem and Euler’s theorem 22 min · quiz
- 7 Arithmetic functions and perfect numbers 21 min · quiz
- 8 Orders and primitive roots 23 min · quiz
- 9 Quadratic residues and the Legendre symbol 23 min · quiz
- 10 Quadratic reciprocity 24 min · quiz
- 11 Primality testing and factoring 25 min · quiz
- 12 Capstone: public-key cryptography with RSA and Diffie–Hellman 24 min · quiz
- E Final exam 20 questions
Requirements
Recommended background. You can start any course at any time.
Description
The arithmetic of the integers from Euclid to modern cryptography: divisibility and the division algorithm with proofs by cases on the remainder and base representations, greatest common divisors, the Euclidean algorithm with Lamé's bound and Bézout's identity with the extended algorithm, primes and the sieve of Eratosthenes, Euclid's proof of the infinitude of the primes, the prime number theorem and the fundamental theorem of arithmetic with Hilbert's example of failed unique factorization, congruences and residue classes with divisibility tests, check digits and the day of the week, linear Diophantine equations, linear congruences and the Chinese remainder theorem, Fermat's little theorem, Euler's theorem, Wilson's theorem and fast modular exponentiation, the arithmetic functions tau, sigma, phi and mu with Möbius inversion, perfect numbers, Mersenne primes and the Lucas–Lehmer test, orders, primitive roots and indices with the periods of repeating decimals, quadratic residues, Euler's criterion, the Legendre symbol, Gauss's lemma and Fermat's theorem on sums of two squares, the law of quadratic reciprocity with Eisenstein's lattice point proof and the Jacobi symbol, primality testing with Carmichael numbers and the Miller–Rabin test, factoring by Fermat's method and Pollard's rho method, and a capstone on public-key cryptography with the Diffie–Hellman key agreement and RSA encryption and signatures, with runnable Python examples throughout.
Part of the Science stream, typically taken in year 3.