In which we review some more ideas from Numbers & Sets, and start to study the Euler totient function.
- Definition of what it means for two numbers to be congruent modulo .
- Lemma 7: Let be a natural number, and let be an integer coprime to . Then has a multiplicative inverse modulo . That is, there is an such that . We proved this using Bézout.
- Definition of the multiplicative group and the Euler totient function.
- Theorem 8 (Fermat-Euler): Let be a natural number, and let be an integer coprime to . Then . We proved this using Lagrange‘s theorem from group theory.
- Theorem 9 (Chinese Remainder Theorem): Let and be coprime natural numbers greater than , and let and be integers. Then there is a solution to the simultaneous congruences and , and moreover this solution is unique modulo . We proved the existence part of this by finding and such that and and and and then taking a suitable linear combination. We did the uniqueness part on autopilot.
- Corollary 10: Let and be coprime natural numbers greater than . Let and be integers with and . Then there is a solution to the congruences and , and such a solution satisfies . We proved this using the Chinese remainder theorem, checking that using contradiction.
- Definition of multiplicative and totally multiplicative functions.
- Corollary 11: Euler’s function is multiplicative. This followed immediately from Corollary 10.
Understanding today’s lecture
You could practise finding the multiplicative inverse of numbers for various moduli. You could practise solving simultaneous congruences.
Your favourite introductory number theory book(s), and your Numbers & Sets lecture notes.
Preparation for Lecture 3
Clarification in response to a question after the lectures: the idea is that we’ll answer these questions during lectures, so what I’m doing in this section is giving you advance notice of the questions so that you can think about them before we answer them (because I think that it’s easier to understand an answer if you’ve thought about the question).
We’re going to think more about the function . What can you say about the value of ? What can you say about the value of ? (Here is fixed, and the sum is over all divisors of . For example, .)