*In which we recap some more ideas from Numbers and Sets.*

Here’s a quick summary of what we did (again, the links are to other places where you can find more information). I have not included examples in this summary, not because they are not important (on the contrary, they’re very important), but because I want to encourage you to develop your own collection of examples.

- Theorem 4 (Bézout):
*Let , and be natural numbers. There are integers and such that if and only if .*We proved the easy direction (‘only if’) last time. Today we reminded ourselves how to use Euclid’s algorithm to prove the interesting direction (‘if’). - Proposition 5:
*Let be a prime number, and suppose that divides the product . Then or .*Proof using Bézout (Theorem 4). This is a good illustration of how useful Bézout is. - Theorem 6 (Fundamental Theorem of Arithmetic):
*Let be a natural number. Then can be factorised as a product of primes, in an essentially unique way.*(Remember that we do not count different orderings of the same factors as different factorisations. With the phrasing here, we consider 1 as being factorised into the ‘empty product‘. If you prefer, simply state the result for .) Proof of existence using induction (very similar to Lemma 1), and uniqueness using the previous result (about primes dividing products). - Definition of congruence notation, and the notation .
- Exercise: Show that we can add, subtract and multiply congruences. Show that these make into a ring.
- Lemma 7:
*Let be a natural number, and an integer coprime to . Then has a multiplicative inverse modulo . That is, there is an integer such that .*We proved this very quickly using Bézout. Exercise: show that if then does not have a multiplicative inverse modulo . - We noted the special case of Lemma 7 that shows that if is prime then is a field.
- Definition of the multiplicative group .
- Definition of the Euler totient function : we define . So records the number of elements of the set that are coprime to .
- Theorem 8 (Fermat–Euler):
*Let be a natural number, and let be an integer coprime to . Then .*We saw that this follows from an application of Lagrange‘s theorem (applied to the group ). And of course Fermat’s Little Theorem is then a special case of this theorem.

#### Further reading

Your favourite introductory number theory book(s), or your Numbers & Sets lecture notes.

#### Preparation for Lecture 3

We’re going to start studying the structure of and next time. This would be a good time to remind yourself of the Chinese Remainder Theorem, and to try to see what it tells us about and . If you like, you could start by considering particular values of .

October 10, 2011 at 2:55 pm

I think Doctor Neale will find, as was clear to anyone with the most rudimentary Latin knowledge, “totient” comes from the Latin “totiens”, meaning “so often”, cognate to “quotiens”, meaning “how often”, and giving us “quotient”. As to their use in maths, the etymology is nebulous.

October 10, 2011 at 3:52 pm

Thanks for the Latin. I’m still not quite clear why it gets attached to this particular function (as opposed to the various other functions that count things), but this is perhaps lost in the mists of time.

October 13, 2011 at 11:42 pm

And back to the topic at hand, I would like to remind the good doctor that, of course, Euler would have written many of his papers in the dear lingua latina (as I am sure the doctor knows, having, read the originals, as any decently educated mathematician ought), so one may suppose that his usage was simply one directly applying its literal meaning, and, for wont of a better word, “totient” drifted happily into English. But I merely surmise.

October 19, 2011 at 12:08 pm

[…] Then . This is interesting only when is coprime to . From Fermat’s Little Theorem (in Lecture 2), we know that , and we can then deduce that . We can take a primitive root modulo , and writing […]

November 21, 2011 at 12:10 pm

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