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

- Lemma 12:
*Let be prime, and let be a natural number. Then .*This was a routine calculation using our earlier observation that . - Proposition 13:
*Let be a natural number. Then .*We proved that is a multiplicative function, and then computed . - Theorem 14 (Lagrange):
*Let be a prime, and let be a polynomial with integer coefficients, with not divisible by . Then the polynomial congruence has at most solutions.*We proved this by induction, using the fact that 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?

#### Further reading

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 (where is prime). Can you make any conjectures on the basis of experimenting with some small values of (building on what we did at the end of the lecture)? Can you prove your conjectures?

We’re going to move on to study — you could start to think about those too.

October 17, 2013 at 2:19 pm

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.

October 18, 2013 at 12:33 pm

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.

October 23, 2013 at 10:51 am

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