Theory of numbers: Prime tests

Item: Theory of numbers: Prime tests
Rating: 5
Author: PostSingularity Institute

by Richard E Borcherds

Formal & Physical Sciences Mathematics PBMathematics PBHNumber theory

🎙 Richard E Borcherds 👥 82K 📅 January 30, 2021 ⏱ 19 min 👁 3K 📄 lecture 🧭 2026-08-17

Available in: English (current) Français

Keywords

prime testFermat's theoremCarmichael numbermodular exponentiationprobabilistic test

Summary

This lecture from an undergraduate number theory course introduces probabilistic tests for primality based on Fermat’s little theorem. The instructor explains that for a prime n, a^n ≡ a mod n for any a, and uses this to test if a number is composite by checking if a^n mod n equals a. He illustrates with small examples, showing that for composite numbers the test often fails. He then addresses the computational challenge of computing a^n mod n for large n, introducing the method of repeated squaring and reducing modulo n at each step, which is efficient and polynomial-time. He notes the historical connection to ancient Egyptian multiplication. He demonstrates the test on 35, showing it is composite. He then discusses the limitation: there exist composite numbers, called Carmichael numbers, that pass the test for all bases a. He gives 561 as an example and explains why it works. He concludes that this test is crude and mentions that better tests exist, to be covered in the next lecture.

168 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a clear and rigorous introduction to probabilistic primality testing. The value lies in its pedagogical approach: starting from Fermat’s theorem, it builds the test, addresses computational efficiency, and honestly discusses its limitations with the Carmichael number example. The argumentation is solid, with step-by-step calculations and logical reasoning. The instructor also provides historical context, enriching the content.

Scientific Rigor, Source Quality, Title Accuracy

The scientific rigor is high: the mathematical content is correct, and the instructor is a respected mathematician. The lecture does not cite external sources, but it is part of a structured course. The title accurately reflects the content. No comments were provided for analysis.

118 words

Title / Content Match

The title accurately reflects the content: the lecture focuses on prime tests using Fermat's theorem.

Quality & Reliability

9/10

Lecture by a renowned mathematician, rigorous and clear, with correct mathematical content and historical context.

Key Moments

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

Cited Sources

Course playlist: Theory of numbers — The lecture is part of this online course.

Concurring Sources

Fermat's little theorem — The theorem is the basis of the primality test discussed.
Modular exponentiation — The efficient method for computing a^n mod n is explained.

Contribution & Novelties

The lecture provides a clear pedagogical introduction to probabilistic primality testing, emphasizing computational efficiency and historical context. It highlights the existence of Carmichael numbers, which are composite numbers that fool the Fermat test.

Pour aller plus loin :

Miller–Rabin primality test — A more robust probabilistic test that overcomes some limitations of the Fermat test.
AKS primality test — The first deterministic polynomial-time primality test.
Carmichael number — Composite numbers that satisfy a^n ≡ a mod n for all a.

80 words

Radar Profile

The radar profile shows high scores in quality, technical level, and reliability, with slightly lower quantity of information due to the focused scope. This indicates a dense, expert-level lecture with strong educational value.

Reliability 9/10