Introduction to number theory lecture 24. Primitive roots for prime powers

Introduction to number theory lecture 24. Primitive roots for prime powers

by Richard E Borcherds

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

Keywords

primitive rootsprime powersnumber theorymodular arithmeticEuler's theorem

Summary

This lecture, part of a Berkeley undergraduate number theory course, focuses on proving that odd prime powers have primitive roots. The instructor, Richard Borcherds, begins by recalling the previous lecture’s results, which established that numbers with primitive roots are exactly 1, 2, 4, p^n, and 2p^n for odd primes p, but only for n=1. The main goal is to extend this to n>1. The proof proceeds by first showing that if g is a primitive root modulo p, then either g or g+p is a primitive root modulo p^2. This is done by analyzing the order of g modulo p^2, which must divide p(p-1) and be a multiple of p-1. If the order is p-1, then g+p has order p(p-1). Next, the lecture proves that if g is a primitive root modulo p^2 for an odd prime p, then it is also a primitive root modulo p^n for any n≥1, using induction and the binomial theorem. The key step relies on p being odd, as the binomial coefficient p choose 2 is divisible by p only for odd p. The lecture also discusses the special case of powers of 2, where no primitive roots exist for n≥3, but 5 acts as a ’near primitive root’ for numbers congruent to 1 mod 4. Applications of primitive roots are then presented, including their use in defining indices (discrete logarithms) for multiplication and exponentiation, and in primality testing (e.g., proving 101 is prime). The lecture concludes with a summary of equivalent conditions for a number to have primitive roots, including Wilson’s theorem.

259 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides a rigorous and complete proof of the existence of primitive roots for odd prime powers. The argumentation is solid, building on previously established results and using standard techniques such as the binomial theorem and induction. The instructor clearly explains each step, making the proof accessible. The value of the information is high, as it covers a fundamental topic in number theory with applications to cryptography and primality testing.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is based on the textbook ‘An Introduction to the Theory of Numbers’ by Niven, Zuckerman, and Montgomery, a standard reference in the field. The instructor, Richard Borcherds, is a renowned mathematician, and the lecture is part of a well-structured course. The title accurately reflects the content, which focuses on primitive roots for prime powers. The lecture is rigorous and well-sourced, with no apparent errors or unsupported claims.

155 words

Title / Content Match

The title accurately reflects the content, which focuses on primitive roots for prime powers.

Quality & Reliability

9/10

Lecture by a renowned mathematician, based on a standard textbook, with rigorous proofs and clear explanations.

Key Moments

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

Cited Sources

Concurring Sources

  • An Introduction to the Theory of Numbers — The textbook used for the course, which covers the same material.

Contribution & Novelties

This lecture provides a clear and rigorous exposition of the existence of primitive roots for odd prime powers, a fundamental result in number theory. The proof is well-structured and accessible to advanced undergraduates. The lecture also discusses applications such as indices and primality testing, which are not always covered in standard treatments.

Pour aller plus loin :

  • Primitive root modulo n — Wikipedia article providing an overview and related concepts.
  • Discrete logarithm — Wikipedia article on discrete logarithms, which are based on primitive roots.
  • Wilson’s theorem — Wikipedia article on Wilson’s theorem, which is related to the conditions discussed in the lecture.
  • Lucas primality test — Wikipedia article on a primality test that uses primitive roots.

116 words

Radar Profile

The radar chart shows high scores in all dimensions, with particularly strong performance in quality of information and reliability. The lecture is technically rigorous but accessible, making it a valuable resource for students.

Reliability 9/10