Skip to content

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.

11 chapters · 26 sectionsEN · 繁 · 简
My course notes

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.

Open this course in the knowledge map

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.

Open this course in the knowledge map

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.1

    Euclid, Bézout and prime factorization

    Derive the Euclidean algorithm, solve integer linear equations, and prove unique prime factorization.

  2. 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.

  3. 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

  1. 2.1

    Linear congruences and Chinese remainders

    Solve congruences through gcd conditions, then assemble compatible local residues into a global solution.

  2. 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

  1. 3.1

    Fermat, Euler and multiplicative order

    Explain periodic powers through units, prove Fermat and Euler, and distinguish exponent bounds from exact order.

  2. 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

  1. 4.1

    Arithmetic functions and Möbius inversion

    Build divisor-sum functions from prime powers and invert divisor sums using the Möbius function.

  2. 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

  1. 5.1

    Primitive roots and power congruences

    Prove primitive roots exist for prime moduli, then convert power congruences into linear exponent congruences.

  2. 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

  1. 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.

  2. 6.2

    Square congruences with nonunit targets

    Use valuations to classify square roots modulo odd prime powers.

  3. 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

  1. 7.1

    A Pell equation by descent

    Classify solutions of x²−2y²=1 and derive rational approximations to √2.

  2. 7.2

    Sums of two squares

    Prove the prime-factor criterion for a sum of two integer squares and construct representations.

  3. 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.

  4. 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

  1. 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.

  2. 8.2

    Miller–Rabin traces and computational cost

    Trace strong rounds and distinguish arithmetic and bit costs.

  3. 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

  1. 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.

  2. 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

  1. 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

  1. 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.

  2. 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.

Vercel visit statistics and public-page performance measurements each require separate consent. Neither is needed to use the website.

Website function storage (used when needed)

Security, sign-in and your chosen preferences use storage when needed. This is separate from optional statistics.

Withdrawing stops future statistics. The page reloads if analytics code needs unloading. It does not delete data already sent.

Read Cookie and storage details