Introduction to number theory lecture 14. Euler's totient function

Introduction to number theory lecture 14. Euler's totient function

by Richard E Borcherds

Formal & Physical Sciences Mathematics PBMathematicsPBHNumber theory
🎙 Richard E Borcherds 👥 82K 📅 February 5, 2022 ⏱ 48 min 👁 10K 📄 lecture 🧭 2026-08-17
Available in: English (current) Français

Keywords

totientEulermultiplicativeChinese remainder theoreminclusion-exclusion

Summary

This lecture introduces Euler’s totient function φ(n), which counts the number of integers between 1 and n that are coprime to n. The speaker begins by computing φ(n) for small n and observes its erratic behavior. He then proves that φ is multiplicative for coprime arguments using the Chinese remainder theorem, and derives the formula φ(n) = n ∏_{p|n} (1 - 1/p). He illustrates the formula using the inclusion-exclusion principle and a probabilistic interpretation, with a cautionary example about pairwise independence not implying mutual independence. He solves examples such as finding all n with φ(n)=24, discusses the Carmichael conjecture, and connects φ(n) being a power of 2 to constructible polygons (Fermat primes). He also analyzes the growth of φ(n), showing that φ(n)/n can be arbitrarily small, and introduces the average order of φ(n) and the probability that two random integers are coprime, leading to the famous result 6/π².

148 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a thorough and rigorous introduction to Euler’s totient function, covering its definition, key properties, and applications. The argumentation is solid: the speaker proves multiplicativity using the Chinese remainder theorem, derives the formula for prime powers, and illustrates the inclusion-exclusion principle with clear examples. He also gives a probabilistic interpretation and warns about common pitfalls in probability, which adds depth. The examples are well-chosen and the reasoning is transparent, making the content valuable for both beginners and those seeking a deeper understanding.

Scientific Rigor, Source Quality, Title Accuracy

The mathematical content is rigorous and accurate, with no apparent errors. The speaker references the standard textbook by Niven, Zuckerman, and Montgomery, and mentions the Carmichael conjecture and Fermat primes, which are well-known topics. The title accurately reflects the content. No external sources are cited beyond the textbook and the course playlist, but this is appropriate for a lecture. The lecture is part of a structured course, and the speaker’s expertise lends credibility.

172 words

Title / Content Match

The title accurately describes the content: a lecture on Euler's totient function.

Quality & Reliability

9/10

Lecture by a renowned mathematician, rigorous and clear, with correct mathematical content and references to standard textbook.

Key Moments

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

Cited Sources

Concurring Sources

Contribution & Novelties

This lecture provides a clear and rigorous exposition of Euler’s totient function, emphasizing its multiplicative property and the inclusion-exclusion principle. The probabilistic interpretation and the cautionary example about independence are particularly insightful. The connection to constructible polygons and Fermat primes adds historical context.

Pour aller plus loin :

98 words

Radar Profile

The radar profile shows high scores in quality and quantity of information, with a strong technical level and reliability. The lecture is dense and rigorous, suitable for an undergraduate audience.

Reliability 9/10