## Number Theory: Lecture 2

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 $n$.
• Lemma 7: Let $n$ be a natural number, and let $a$ be an integer coprime to $n$.  Then $a$ has a multiplicative inverse modulo $n$.  That is, there is an $m$ such that $am \equiv 1 \pmod{n}$.  We proved this using Bézout.
• Definition of the multiplicative group $\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}$ and the Euler totient function.
• Theorem 8 (Fermat-Euler): Let $n$ be a natural number, and let $a$ be an integer coprime to $n$.  Then $a^{\phi(n)} \equiv 1 \pmod{n}$.  We proved this using Lagrange‘s theorem from group theory.
• Theorem 9 (Chinese Remainder Theorem): Let $m_1$ and $m_2$ be coprime natural numbers greater than $1$, and let $a_1$ and $a_2$ be integers.  Then there is a solution to the simultaneous congruences $n \equiv a_1 \pmod{m_1}$ and $n \equiv a_2 \pmod{m_2}$, and moreover this solution is unique modulo $m_1 m_2$.  We proved the existence part of this by finding $x_1$ and $x_2$ such that $x_1 \equiv 1 \pmod{m_1}$ and $x_1 \equiv 0 \pmod{m_2}$ and $x_2 \equiv 0 \pmod{m_1}$ and $x_2 \equiv 1 \pmod{m_2}$ and then taking a suitable linear combination.  We did the uniqueness part on autopilot.
• Corollary 10: Let $m_1$ and $m_2$ be coprime natural numbers greater than $1$.  Let $a_1$ and $a_2$ be integers with $(a_1, m_1) = 1$ and $(a_2, m_2) = 1$.  Then there is a solution to the congruences $n \equiv a_1 \pmod{m_1}$ and $n \equiv a_2 \pmod{m_2}$, and such a solution satisfies $(n, m_1m_2) = 1$We proved this using the Chinese remainder theorem, checking that $(n, m_1 m_2) = 1$ using contradiction.
• Definition of multiplicative and totally multiplicative functions.
• Corollary 11: Euler’s $\phi$ 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 $\phi$.  What can you say about the value of $\phi(n)$?  What can you say about the value of $\sum_{d|n} \phi(d)$?  (Here $n$ is fixed, and the sum is over all divisors of $n$.  For example, $\sum_{d|12} \phi(d) = \phi(1) + \phi(2) + \phi(3) + \phi(4) + \phi(6) + \phi(12)$.)

### 4 Responses to “Number Theory: Lecture 2”

1. Richard Freeland Says:

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

2. Josh P. Says:

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?

3. alexwlchan Says:

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

4. Number Theory: Lecture 20 | Theorem of the week Says:

[…] 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 […]