*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.

#### Further reading

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, .)

October 14, 2013 at 1:46 pm

So I looked up ‘totient’ in Chambers, and it defines another word ‘totitive’ for a number less than n and coprime to it, but doesn’t give another meaning for either of them. They seem to come from the Latin word ‘tot’ meaning ‘so many’, so I’m imagining Euler thinking “What shall I call this function that counts how many of these things there are? Don’t know, let’s just say there are so many of them, and come up with a better name later.”

October 14, 2013 at 3:12 pm

Here’s a link that addresses the etymology of the word ‘totient’ (since the question came up in lectures today):

http://english.stackexchange.com/questions/23694/where-does-the-word-totient-come-from

It seems that totient is a made-up word first coined by Sylvester, not used outside of mathematics. It is built from a latin root ‘tot’, meaning ‘that many’, combined with a Sanskrit suffix ‘iens’ (like in quotient etc.). So, for Euler, the ‘totient’ function was the (tautological) answer to the question: how many primes are there smaller than n?

October 14, 2013 at 4:37 pm

For those who are interested, here’s a thread on the English Stack Exchange on the etymology of the word “totient”:

http://english.stackexchange.com/questions/23694/where-does-the-word-totient-come-from

November 25, 2013 at 11:33 am

[…] this course so far we’ve seen a few results of the form “If is prime, then …”, for example Fermat’s Little Theorem and Euler’s criterion. It would be helpful to go back to those two results in particular, to […]