Introduction to number theory lecture 25. Quadratic equations mod p.

Item: Introduction to number theory lecture 25. Quadratic equations mod p.
Rating: 5
Author: PostSingularity Institute

by Richard E Borcherds

Formal & Physical Sciences Mathematics PBMathematics PBHNumber theory

🎙 Richard E Borcherds 👥 82K 📅 February 27, 2022 ⏱ 21 min 👁 5K 📄 lecture 🧭 2026-08-17

Available in: English (current) Français

Keywords

quadratic congruencesquare root modulo pEuler's criterionFermat primeTonelli-Shanks

Summary

This lecture, part of a Berkeley undergraduate number theory course, addresses solving quadratic congruences modulo a prime p. The instructor begins by reducing the general quadratic equation ax^2+bx+c ≡ 0 (mod p) to the problem of finding square roots modulo p, using the technique of completing the square. He notes that for p=2 the problem is trivial, and for odd p, the discriminant determines solvability via Euler’s criterion. The main focus is on efficient methods to compute square roots modulo p. The lecture presents several approaches: trial and error for small primes, general polynomial root-finding algorithms (Berlekamp and Cantor-Zassenhaus, to be discussed later), and an ansatz-based method. The ansatz method leads to a simple formula for primes congruent to 3 mod 4, and a more involved procedure for primes congruent to 1 mod 4, including special cases like Fermat primes. The general solution uses a divide-and-conquer strategy, splitting the problem into finding square roots of elements of odd order and elements of order a power of 2, then combining them. A detailed example is worked out for solving x^2 ≡ 2 (mod 41). The lecture concludes by mentioning that similar techniques can be extended to higher roots.

197 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides valuable insights into solving quadratic congruences, a fundamental topic in number theory. The argumentation is rigorous and well-structured, building from basic principles to more advanced techniques. The instructor clearly explains the reasoning behind each step, making the material accessible to students with a background in elementary number theory. The presentation of multiple methods, including the ansatz approach and the divide-and-conquer strategy, offers a comprehensive understanding of the problem. The worked example for p=41 effectively illustrates the general method. The lecture also highlights connections to other algorithms, such as Berlekamp and Cantor-Zassenhaus, and mentions extensions to higher roots, adding depth to the discussion.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is scientifically rigorous, with careful attention to mathematical correctness. The instructor references the standard textbook ‘An introduction to the theory of numbers’ by Niven, Zuckerman, and Montgomery, which is a reliable source. The title accurately reflects the content, as the lecture indeed focuses on quadratic equations modulo p. The presentation is clear and logical, with appropriate use of notation and examples. The lecture is part of a structured course, indicating a well-organized curriculum. No external sources are cited beyond the textbook and the course playlist, but the mathematical content is self-contained and rigorous.

215 words

Title / Content Match

The title accurately describes the content: the lecture introduces and solves quadratic equations modulo p.

Quality & Reliability

9/10

Lecture by a renowned mathematician, part of a university course, based on a standard textbook, with rigorous mathematical reasoning and clear explanations.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

Course playlist: Introduction to number theory — The lecture is part of this course; the playlist contains all lectures.

Concurring Sources

An Introduction to the Theory of Numbers (5th edition) — The textbook referenced in the lecture, which covers similar material.

Contribution & Novelties

The lecture provides a clear and systematic exposition of solving quadratic congruences modulo a prime, with a focus on efficient algorithms. It introduces the ansatz method and a divide-and-conquer strategy that is not commonly presented in introductory texts. The worked example for p=41 illustrates the method in detail. The lecture also connects to more general polynomial root-finding algorithms, offering a broader perspective.

Pour aller plus loin :

Tonelli-Shanks algorithm — A well-known algorithm for computing square roots modulo a prime, closely related to the method presented.
Quadratic residue — Fundamental concept underlying the solvability condition.
Berlekamp’s algorithm — A method for factoring polynomials over finite fields, mentioned in the lecture.
Cantor–Zassenhaus algorithm — Another polynomial factorization method, also mentioned.

119 words

Radar Profile

The radar profile shows high scores in quality, technical level, and reliability, with slightly lower but still strong scores in quantity of information. This indicates a dense, rigorous, and well-explained lecture that may be challenging for beginners but highly valuable for students with some background.

Reliability 9/10