Number Theory: Lecture 2

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 $a$ , $b$ and $c$ be natural numbers. There are integers $m$ and $n$ such that $am + bn = c$ if and only if $(a,b) | c$ . 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 $p$ be a prime number, and suppose that $p$ divides the product $ab$ . Then $p|a$ or $p|b$ . Proof using Bézout (Theorem 4). This is a good illustration of how useful Bézout is.
Theorem 6 (Fundamental Theorem of Arithmetic): Let $n$ be a natural number. Then $n$ 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 $n > 1$ .) 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 $\mathbb{Z}/n\mathbb{Z}$ .
Exercise: Show that we can add, subtract and multiply congruences. Show that these make $\mathbb{Z}/n\mathbb{Z}$ into a ring.
Lemma 7: Let $n$ be a natural number, and $a$ an integer coprime to $n$ . Then $a$ has a multiplicative inverse modulo $n$ . That is, there is an integer $m$ such that $am \equiv 1 \pmod{n}$ . We proved this very quickly using Bézout. Exercise: show that if $(a,n) > 1$ then $a$ does not have a multiplicative inverse modulo $n$ .
We noted the special case of Lemma 7 that shows that if $p$ is prime then $\mathbb{Z}/p\mathbb{Z}$ is a field.
Definition of the multiplicative group $( \mathbb{Z}/n\mathbb{Z})^{\times}$ .
Definition of the Euler totient function $\phi$ : we define $\phi(n) = |(\mathbb{Z}/n\mathbb{Z})^{\times}|$ . So $\phi(n)$ records the number of elements of the set $\{1, 2, 3, ..., n \}$ that are coprime to $n$ .
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 saw that this follows from an application of Lagrange‘s theorem (applied to the group $(\mathbb{Z}/n\mathbb{Z})^{\times}$ ). And of course Fermat’s Little Theorem is then a special case of this theorem.

Preparation for Lecture 3

We’re going to start studying the structure of $\mathbb{Z}/n\mathbb{Z}$ and $(\mathbb{Z}/n\mathbb{Z})^{\times}$ 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 $\mathbb{Z}/n\mathbb{Z}$ and $(\mathbb{Z}/n\mathbb{Z})^{\times}$ . If you like, you could start by considering particular values of $n$ .

Like this:

Be the first to like this post.

This entry was posted on October 10, 2011 at 12:30 pm and is filed under Cambridge Maths Tripos, II Number Theory, Lecture. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

5 Responses to “Number Theory: Lecture 2”

Verrius Flaccus Says:
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.
theoremoftheweek Says:
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.
Verrius Flaccus Says:
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.
Number Theory: Lecture 6 « Theorem of the week Says:
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 [...]
Number Theory: Lecture 20 « Theorem of the week Says:
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, [...]

Theorem of the week