Egbert Rijke

Course Notes on Elementary Number Theory

These are course notes for the course 304 Elementary Number Theory, which I taught at Johns Hopkins University in the Spring 2025 and Fall 2025 semesters.

[Download the course notes (pdf, 479 pages)]

Basic information

• Author: Egbert Rijke
• Title: The Great Story of Numbers
• Year: 2026
• Last updated: May 29, 2026
• Pages: 479
• Exercises: 284
• Type: Lecture notes
• Level: Upper-division undergraduate
• Prerequisites: None; Suitable for non-math majors
• Language: English
• Institution: Johns Hopkins University
• Description: Freely available notes for an undergraduate course on number theory, with an emphasis on proof-writing, history, structural thinking, the central theorems of elementary number theory, and an extensive set of exercises carefully categorized by skill level.
• URL: https://egbertrijke.github.io/notes/number-theory/

Overview of the Course

Elementary Number Theory is a designated “Introduction to Proofs” course at the Johns Hopkins Mathematics Department. The course is taken by students with a variety of majors, including mathematics, computer science, chemistry, history, or music.

The beginning of the course focuses on proof writing, and covers topics such as induction, unique existence proofs, bijections, counting with bijections, and the well-ordering theorem. These topics are approached from three angles:

• Skill development: The course gives concrete guidance on abstract reasoning, how to write a proof with clarity, and recognizing when a particular proof technique is appropriate.
• History: By answering the question “How did mathematicians of the past think about certain phenomena?”, and “Have these concepts always been like that”, we make thinking about thinking about numbers more tangible.
• Structural thinking: By articulating what kinds of structure we are thinking about, the student learns to extract the essence of a mathematical problem.

The course then develops topics such as divisibility, greatest common divisors, rational numbers, Pythagorean triples, and infinite descent. In the historical development, these lectures take us from ancient mathematics to the time of Fermat. The purpose here is to build a solid foundation in proof-writing skills, before moving on to the more typical number-theoretic topics. After this foundational part of the course, we cover topics such as modular arithmetic, the Chinese Remainder Theorem, primes, multiplicative functions, Fermat’s Little Theorem, Fermat’s Two-Squares theorem, polynomials, primitive roots, quadratic residues, and quadratic reciprocity.

The notes contain extensive references to historical aspects of number theory. I have made use of many sources to learn about the history of number theory, particularly Andre Weil’s Number Theory: An Approach Through History from Hammurapi to Legendre and Carl Friedrich Gauss’s Disquisitiones Arithmeticae. I have also read historical sources such as Fibonacci’s Liber Quadratorum, the works of Leonhard Euler, and I have benefitted from many online sources. In particular, the Internet Archive hosts scans of many original texts in number theory. Finally, I have learned from many textbooks in number theory, including LeVeque’s Topics in Number Theory, Hardy and Wright’s An Introduction to the Theory of Numbers, Silverman’s A Friendly Introduction to Number Theory, and many more. Furthermore, Keith Conrad’s various notes on topics in number theory have been invaluable.

Comments on the Pedagogy

Each chapter corresponds roughly to one lecture, although many chapters cover optional topics. At the end of each chapter, there is a set of exercises which are categorized along three tiers: starter exercises, routine-building exercises, and challenge exercises. The starter exercises are meant to test the student’s understanding of the central concept of a chapter, or their ability to make the essential computations with that concept. The routine-building exercises are designed to develop the student’s routine with a subject. A student might find them challenging at first, while they are still learning the subject, but they are designed so that most students attempting these will eventually find their solutions. These exercises are designed to bring the student to the intended level of skill for the course. The challenge exercises are designed to be harder, and require more creative solutions. Some of them are modified versions of contest problems. A weekly homework assignment consists typically of multiple routine-building exercises and one challenge problem.

For the pedagogical development of this course, I have made use of the textbook Teaching for Quality Learning at University by Biggs and Tang. While not specifically about mathematics education, this book offers valuable advice on how to foster a productive and inspiring learning environment for students.

Table of Contents

• Introduction
• I The Nature of Numbers
  • 1 The Nature of Mathematical Inquiry
    • 1.1 Brief Remarks on the History of Number Theory
      • 1.1.1 The Ancient Greek Scholars
      • 1.1.2 Mathematics, Astronomy, and Poetry in Ancient India
      • 1.1.3 Pierre de Fermat
      • 1.1.4 Leonhard Euler
      • 1.1.5 Johannes Carl Friedrich Gauss
      • 1.1.6 Contemporary Mathematics
    • 1.2 The Concept of Number Through History
  • 2 Mathematical Induction
    • 2.1 Recursion and Induction
    • 2.2 Addition of Natural Numbers
    • 2.3 Arithmetic of Natural Numbers
    • 2.4 Relations on the Natural Numbers
    • 2.5 Finite Sums and Products
    • 2.6 Hemachandra’s Counting Problem
    • Exercises
  • 3 Counting
    • 3.1 Hume’s Principle
    • 3.2 Equivalent Ways of Defining Bijections
    • 3.3 Counting Bijections
    • 3.4 Counting Subsets
    • 3.5 The Binomial Theorem
    • 3.6 The Inclusion–Exclusion Principle
    • Exercises
  • 4 The Integers
    • 4.1 Cyclic Sets
    • 4.2 Maps Preserving Cyclic Structure
    • 4.3 A Structural Definition of the Integers
    • 4.4 Constructing the Integers from the Natural Numbers
    • 4.5 Integer Arithmetic
    • Exercises
  • 5 Notation for Numbers
    • 5.1 Some Remarks on the History of Written Numbers
    • 5.2 The Well-Ordering Principle of the Natural Numbers
    • 5.3 Euclidean Division
    • 5.4 The Representability Theorem
    • 5.5 Combinatorial Applications
    • Exercises
  • 6 Linear Diophantine Equations
    • 6.1 Divisibility
    • 6.2 Ideals of Integers
    • 6.3 The Ordering by Divisibility
    • 6.4 Greatest Common Divisors
    • 6.5 Euclid’s Algorithm
    • 6.6 Linear Diophantine Equations in Multiple Variables
    • 6.7 Āryabhaṭa’s Computations of the Positions of Planets
    • Exercises
  • 7 Congruences
    • 7.1 The Congruence Relations
    • 7.2 Equivalence Relations
    • 7.3 Equivalence Classes and Residue Systems
    • 7.4 The Integers Modulo $n$
    • 7.5 The Multiplicative Order of an Integer Modulo $n$
    • Exercises
  • 8 Systems of Linear Congruences
    • 8.1 Solving Linear Congruences
    • 8.2 Solving Multiple Linear Congruences Simultaneously
    • 8.3 The Chinese Remainder Theorem
    • 8.4 A Method Suggested by Gauss
    • Exercises
  • 9 The Rational Numbers
    • 9.1 Integer Fractions
    • 9.2 The Irrationality of Square Roots
    • 9.3 Continued Fractions
    • 9.4 Farey’s Series of Fractions
    • 9.5 A Structural Definition of the Rational Numbers
    • Exercises
  • 10 Pythagorean Triples
    • 10.1 The Pythagorean Theorem
    • 10.2 Euclid’s Parametrization of the Pythagorean Triples
    • 10.3 Rational Points on the Unit Circle
    • 10.4 Vieta Jumping
    • 10.5 The Tree of Primitive Pythagorean Triples
    • 10.6 Squares in Arithmetic Progressions
    • Exercises
  • 11 Infinite Descent
    • 11.1 The Method of Infinite Descent
    • 11.2 The Area of a Pythagorean Triangle is not a Square
    • 11.3 The Unsolvability of $x^4+y^4=z^4$
    • 11.4 Aubry’s Theorem
    • 11.5 The Nonexistence of Four Squares in an Arithmetic Progression
    • 11.6 The Congruent Number Problem
    • Exercises
• II The Multiplicative Nature of Numbers
  • 12 Prime Numbers
    • 12.1 The Fundamental Theorem of Arithmetic
    • 12.2 The Infinitude of Primes
      • 12.2.1 Saidak’s Proof
      • 12.2.2 Furstenberg’s Proof, Following Cass–Wildenberg
      • 12.2.3 Erd\H {o}s’s Proof
      • 12.2.4 A Proof via the Stars-and-Bars Method
    • 12.3 Fermat Primes
    • 12.4 Legendre’s Formula and Kummer’s Theorem
    • 12.5 Bertrand’s Postulate
    • Exercises
  • 13 Multiplicative Functions
    • 13.1 Perfect Numbers
    • 13.2 Euler’s Totient Function
    • 13.3 Multiplicative Functions
    • 13.4 The M"obius Function
    • 13.5 Dirichlet Convolution
    • 13.6 Dirichlet Inverses
    • Exercises
  • 14 Strong Divisibility Sequences
    • 14.1 Lucas Sequences
    • 14.2 The Rank of Apparition
    • 14.3 Primitive Sequences
    • 14.4 LCM-sequences
    • 14.5 The Lifting the Exponent Lemma
    • Exercises
  • 15 Fermat’s Little Theorem and its Consequences
    • 15.1 Fermat’s Little Theorem
    • 15.2 Euler’s Theorem
    • 15.3 Wilson’s Theorem
    • 15.4 Lucas’s Theorem
    • 15.5 The Quadratic Character of $-1$
    • 15.6 The Infinitude of Primes Congruent to 1 Modulo Powers of 2
    • Exercises
  • 16 Fermat’s Two-Squares Theorem
    • 16.1 Numbers Representable as a Sum of Two Squares
    • 16.2 Euler’s Proof by Infinite Descent
    • 16.3 Zagier’s Proof Using Fixed Points of Involutions
    • 16.4 The Method of Brillhart–Hermite–Serret
    • Exercises
  • 17 The Gaussian Integers
    • 17.1 Definition and Basic Properties of the Gaussian Integers
    • 17.2 Euclidean Division of Gaussian Integers
    • 17.3 The Greatest Common Divisor of Gaussian Integers
    • 17.4 Primes in the Gaussian Integers
    • 17.5 Fermat’s Two-Square Theorem
    • 17.6 The Biquadratic Character of $-1$
    • Exercises
  • 18 Polynomials
    • 18.1 Polynomials with Abstract Coefficients
    • 18.2 The Factor Theorem
    • 18.3 Polynomial Congruences of Prime Moduli
    • 18.4 Lagrange’s Interpolation Theorem
    • 18.5 Fixed Divisors of Integer Polynomials
    • Exercises
  • 19 Primitive Roots
    • 19.1 Counting Elements of a Given Order Modulo a Prime
    • 19.2 Primitive Roots
    • 19.3 The Discrete Logarithm
    • 19.4 A Criterion for Congruences of Degree $n$
    • Exercises
  • 20 The Moduli with Primitive Roots
    • 20.1 Primitive Roots Modulo Odd Prime Powers
    • 20.2 The Complete Characterization of Moduli with Primitive Roots
    • 20.3 Carmichael’s Function
  • 21 Polynomial Congruences
    • 21.1 Polynomial Congruences of Composite Moduli
    • 21.2 Derivatives of Polynomials
    • 21.3 Hensel’s Lemma
    • 21.4 The Elementary Symmetric Polynomials
    • 21.5 Reduced Polynomials Modulo a Prime
  • 22 Divisibility and Irreducebility of Polynomials
    • 22.1 Primitive Polynomials and Gauss’s Lemma
    • 22.2 Euclid’s Algorithm for Polynomials
    • 22.3 Irreducible Polynomials
    • 22.4 Eisenstein’s Criterion
    • Exercises
  • 23 Cyclotomic Polynomials
    • 23.1 The Primitive Factors of $x^n-1$
    • 23.2 The M"obius Inversion Formula for the Cyclotomic Polynomials
    • 23.3 Zsigmondy’s Theorem
    • 23.4 The Infinitude of Primes Congruent to $1$ Modulo $n$
    • 23.5 Vantieghem’s Theorem
    • Exercises
  • 24 Integer Factorizations of Polynomial Values
    • 24.1 The Reducibility of $x^n-a$
    • 24.2 Aurifeuillean Factorizations
    • 24.3 Obstructions to the Infinitude of Primes in Lucas Sequences
• III The Arithmetic of Quadratic Forms
  • 25 Quadratic Residues
    • 25.1 Quadratic Congruences
    • 25.2 Quadratic Residues
    • 25.3 Legendre Symbols
    • 25.4 Euler’s Criterion
    • 25.5 Euler’s Prime-Generating Polynomial
    • Exercises
  • 26 Quadratic Reciprocity
    • 26.1 The Quadratic Character of 2
    • 26.2 The Statement of Quadratic Reciprocity
    • 26.3 Gauss’s Lemma
    • 26.4 Eisenstein’s Proof
    • Exercises
• A Conjectures in Elementary Number Theory
  • A.1 Conjectures About the Infinitude of Certain Classes of Primes
  • A.2 Conjectures About Exceptional Primes
  • A.3 Conjectures About Gaps Between the Primes
  • A.4 Conjectures About Conditions for Primality
  • A.5 Conjectures About Prime Decompositions
  • A.6 Conjectures About Arithmetic Functions
  • A.7 Conjectures About Diophantine Problems
  • A.8 Conjectures About Representations of Numbers
  • A.9 Conjectures About Iterative and Dynamical Processes
• References