MATH3080
Number Theory
Divisibility, congruences, arithmetic functions, primitive roots, quadratic residues, Diophantine equations, primality testing and continued fractions, with proofs, worked examples and solved exercises.
Your progress
0/ 26 sections marked complete
Next section: 1.1 Euclid, Bézout and prime factorization
Completion marks are saved in this browser.
This course in the web
In the MATH3080 notes
- Theorem cards
- 72
- Definitions
- 34
- Counterexamples
- 26
- Concept lenses
- 19
- Histories of ideas
- 1
- Proof X-rays
- 28
Sections with a history of an idea
None of these is on the timeline yet.
No concept lens from this course is recorded in the web yet.
Counts cover the 26 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
In the webTheorem cards 72 · Definitions 34 · Counterexamples 26 · Concept lenses 19 · Histories of ideas 1 · Proof X-rays 28
None of these is on the timeline yet.
No concept lens from this course is recorded in the web yet.
Counts cover the 26 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
Chapter 1 · 3 sections
Divisibility and factorization
Derive the Euclidean algorithm, solve integer linear equations, and prove unique prime factorization.
Theorems 11 · Definitions 5Counterexamples 3Lenses 3History 1Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 1.1
Euclid, Bézout and prime factorization
Derive the Euclidean algorithm, solve integer linear equations, and prove unique prime factorization.
- 1.2
Euclidean divisions and Fibonacci bounds
Prove the division-count bound and distinguish it from bit complexity; includes solved practice, partly repeated from 1.1.
- 1.3
Factorial valuations and binomial divisibility
Count prime factors in factorials and explain binomial divisibility through base-p carries.
Chapter 2 · 2 sections
Congruences
Solve congruences through gcd conditions, then assemble compatible local residues into a global solution.
Theorems 9 · Definitions 3Counterexamples 3Lenses 1Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 2.1
Linear congruences and Chinese remainders
Solve congruences through gcd conditions, then assemble compatible local residues into a global solution.
- 2.2
Wilson's theorem, inverse pairing and factorial residues
Prove Wilson's theorem by inverse pairing, classify composite factorial residues, and derive half-factorial square roots.
Chapter 3 · 2 sections
Powers and orders
Explain periodic powers through units, prove Fermat and Euler, and distinguish exponent bounds from exact order.
Theorems 7 · Definitions 3Counterexamples 3Lenses 2Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 3.1
Fermat, Euler and multiplicative order
Explain periodic powers through units, prove Fermat and Euler, and distinguish exponent bounds from exact order.
- 3.2
Carmichael's universal exponent and Korselt's criterion
The least exponent that annihilates every unit modulo n, its computation through the Chinese remainder theorem and prime powers, and a complete proof of Korselt's criterion for Carmichael numbers.
Chapter 4 · 2 sections
Arithmetic functions
Build divisor-sum functions from prime powers and invert divisor sums using the Möbius function.
Theorems 4 · Definitions 3Counterexamples 1Lenses 2Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 4.1
Arithmetic functions and Möbius inversion
Build divisor-sum functions from prime powers and invert divisor sums using the Möbius function.
- 4.2
Perfect numbers and the Euclid–Euler theorem
Use divisor sums to classify even perfect numbers; includes solved practice.
Chapter 5 · 2 sections
Primitive roots
Prove primitive roots exist for prime moduli, then convert power congruences into linear exponent congruences.
Theorems 4 · Definitions 2Counterexamples 2Lenses 2Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 5.1
Primitive roots and power congruences
Prove primitive roots exist for prime moduli, then convert power congruences into linear exponent congruences.
- 5.2
Lifting primitive roots and classifying cyclic unit groups
Construct generators at every odd prime power and prove exactly which composite moduli admit a primitive root.
Chapter 6 · 3 sections
Quadratic residues
Prove Euler's criterion, Gauss's sign lemma, both supplementary laws, and quadratic reciprocity by counting lattice points.
Theorems 6 · Definitions 3Counterexamples 3Lenses 2Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 6.1
Quadratic residues, Gauss's lemma, and reciprocity
Prove Euler's criterion, Gauss's sign lemma, both supplementary laws, and quadratic reciprocity by counting lattice points.
- 6.2
Square congruences with nonunit targets
Use valuations to classify square roots modulo odd prime powers.
- 6.3
Jacobi reciprocity and evaluation without factorization
Extend reciprocity from primes to odd composite denominators, prove a Euclidean evaluation algorithm and its bit-cost boundary, and distinguish the resulting symbol from a square-root certificate.
Chapter 7 · 4 sections
Diophantine equations
A quadratic Diophantine equation and descent.
Theorems 11 · Definitions 4Counterexamples 4Lenses 3Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 7.1
A Pell equation by descent
Classify solutions of x²−2y²=1 and derive rational approximations to √2.
- 7.2
Sums of two squares
Prove the prime-factor criterion for a sum of two integer squares and construct representations.
- 7.3
Classifying Positive Integer Pythagorean Triples
A complete classification of positive integer Pythagorean triples: pairwise coprimality, parity modulo 4, the parametrization through m and n with existence and uniqueness, scaling to primitive triples, and the rational parametrization of the unit circle.
- 7.4
Pell equations and the structure of quadratic units
Prove Pell existence by bounded convergent norms, classify all solutions by a least positive unit, and justify an exact continued-fraction search.
Chapter 8 · 3 sections
Primality testing
Trace the strong probable-prime test and prove an error bound.
Theorems 8 · Definitions 3Counterexamples 2Lenses 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 8.1
The Miller–Rabin strong probable-prime test
Build the test from roots of one, trace decisions and interpret a round that exhausts its checks.
- 8.2
Miller–Rabin traces and computational cost
Trace strong rounds and distinguish arithmetic and bit costs.
- 8.3
A subgroup bound for Miller–Rabin errors
Prove a one-half strong-liar bound for odd composites and analyze independent repetitions.
Chapter 9 · 2 sections
Primes and their distribution
Primes and their distribution
Theorems 6 · Definitions 3Counterexamples 2Lenses 2Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 9.1
The Sieve of Eratosthenes and Certified Prime Lists
A rigorous treatment of the sieve of Eratosthenes: precise definitions, a guarded finite algorithm, an invariant-based correctness proof, elementary cost bounds, and why enumerating primes differs from testing one integer.
- 9.2
Chebyshev bounds and reciprocal prime divergence
Use prime powers in central binomial coefficients to prove the x over log x scale of prime counting, then prove divergence of reciprocal primes without the prime number theorem.
Chapter 10 · 1 section
Hensel lifting
Hensel lifting
Theorems 2 · Definitions 2Counterexamples 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 10.1
Hensel lifting, singular branches, and p-adic roots
Prove the exact one-digit lifting rule for arbitrary integer polynomials, construct compatible p-adic roots, and distinguish simple uniqueness from singular branching.
Chapter 11 · 2 sections
Continued fractions
Continued fractions
Theorems 4 · Definitions 3Counterexamples 2Lenses 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 11.1
Continued fractions, convergents, and best approximations
Derive the convergent recurrences and exact error formula, prove best approximation of the second kind, and establish Legendre's criterion.
- 11.2
Quadratic irrationals and eventual periodicity
Prove both directions of the periodic continued-fraction theorem through complete quotients, bounded integral surd states, and a reversible reduced-state map.