## Number Theory: Lecture 3

In which we study the Euler totient function and polynomial congruences.

• Lemma 12: Let $p$ be prime, and let $j$ be a natural number.  Then $\phi(p^j) = p^{j-1}(p-1)$.  This was a routine calculation using our earlier observation that $\phi(p^j) = \# \{a : 1 \leq a \leq p^j \textrm{ and } (a,p) = 1 \}$.
• Proposition 13: Let $n$ be a natural number.  Then $\sum_{d|n} \phi(d) = n$.  We proved that $F(n) = \sum_{d|n} \phi(d)$ is a multiplicative function, and then computed $F(p^j)$.
• Theorem 14 (Lagrange): Let $p$ be a prime, and let $f(x) = a_n x^n + a_{n-1} x^{n-1} + \dotsb + a_1 x + a_0$ be a polynomial with integer coefficients, with $a_n$ not divisible by $p$.  Then the polynomial congruence $f(x) \equiv 0 \pmod{p}$ has at most $n$ solutions.  We proved this by induction, using the fact that $\mathbb{Z}/p\mathbb{Z}$ is an integral domain.

I gave out the first examples sheet, which is available on the course page.

#### Understanding today’s lecture

What examples of multiplicative functions can you come up with?

Can you prove an analogue of Theorem 14 in a general integral domain?

Davenport (The Higher Arithmetic) discusses some of the above topics in the way that I’ve presented them, but not all.  Baker (A concise introduction to the theory of numbers), Koblitz (A Course in Number Theory and Cryptography), and Jones and Jones (Elementary Number Theory) all also discuss these topics, although again not necessarily following exactly the approach that I’ve used.

#### Preparation for Lecture 4

We’d like to understand the structure of $\left(\mathbb{Z}/p\mathbb{Z}\right)^{\times}$ (where $p$ is prime).  Can you make any conjectures on the basis of experimenting with some small values of $p$ (building on what we did at the end of the lecture)?  Can you prove your conjectures?

We’re going to move on to study $\left(\mathbb{Z}/p^j \mathbb{Z}\right)^{\times}$ — you could start to think about those too.

### 3 Responses to “Number Theory: Lecture 3”

1. Richard Freeland Says:

You can also prove the fact about summing the totient function over the divisors of n by noticing that the cyclic group on n elements has d elements whose order divides d, and so phi(d) elements of order exactly d. The sum then just sums the number of elements of each order, and concludes this is the order of the group.

Since we’re going to use this property the other way round fairly soon, it’s quite nice to think of it like this; however, we don’t then realise that the argument generalises to all multiplicative functions.

2. Tadek Krassowski Says:

My favourite proof of this fact is the combinatorial one in which you consider the fractions 1/n, 2/n, …, n/n but reduced to lowest terms and simply count how many times each denominator appears in the sequence. Of course this is just a different way of saying “Let S_d be the set of integers i<=n with (i,n)=d, what is its cardinality?", but when you phrase it this way it does not provide you with the "Where did that come from?" sensation.

3. Number Theory: Lecture 6 | Theorem of the week Says:

[…] odd prime, and let be an integer.  Then .  We proved this by first showing that and then using Lagrange’s theorem to show that the even powers of a primitive root ‘use up’ all the possible solutions to […]