Meetup summary

2024-10-03 - Integer divisibility and the Möbius and Euler Totient functions

We’ll eventually need some number theory machinery to work through the cycle construction, which we stated last time without proof or derivation. I think this is a good opportunity to drill into the fundamentals so we can build up to that in a later session.

Recommended reading:

• Chapter 1 (full) and Chapter 2 (sections 2.1—2.5) of Tom Apostol’s Introduction to Analytic Number Theory.
• Wikipedia entries on the Möbius function and Euler totient function.

Agenda:

• Define integer division (via the Euclidean division theorem).
• Go over the 12 integer division properties. Get to know these like the back of your hand, as they are fundamental and used heavily in many number theory results.
• Define the GCD and derive an informal proof through Euclid’s algorithm (a certifying algorithm).
• Derive the Extended Euclidean algorithm (another certifying algorithm, which this time also produces the coefficients of Bézout’s identity).
• Prove Bézout’s identity following GCD properties and linearity.
• Define prime and composite numbers.
• Go over the fundamental theorem of arithmetic (prime factorization theorem) and some related results/lemmas.
• Define the $\mu$ and $\varphi$ functions.
• Derive some properties of the Möbius function, totient function, and their interrelationship.

Notes:

We ended up not getting through all the expected Möbius/totient properties, but did do a bonus derivation of the multiplicative property of the totient function and and how to compute its value for repeated prime powers.