Chapter 8 Number Theory276
Things get simpler when we rephrase Euler’s Theorem in terms ofZn.Definition 8.10.2.LetZnbe the integers in.0::n/, that are relatively prime ton:^13
ZnWWDfk 2 .0::n/j gcd.k;n/D 1 g: (8.16)Consequently,
.n/Dˇ
ˇZnˇ
ˇ:
Theorem 8.10.3(Euler’s Theorem forZn).For allk 2 Zn,
k .n/D1 .Zn/: (8.17)Theorem 8.10.3 will follow from two very easy lemmas.
Let’s start by observing thatZnis closed under multiplication inZn:Lemma 8.10.4.Ifj;k 2 Zn, thenjnk 2 Zn.
There are lots of easy ways to prove this (see Problem 8.67).Definition 8.10.5.For any elementkand subsetSofZn, let
kSWWDfknsjs 2 Sg:Lemma 8.10.6.Ifk 2 ZnandSZn, then
jkSjDjSj:Proof. Sincek 2 Zn, by Theorem 8.9.5 it is cancellable. Therefore,
ŒksDkt .Zn/ç implies sDt:So mulitplying bykinZnmaps all the elements ofSto distinct elements ofkS,
which impliesSandkSare the same size.
Corollary 8.10.7.Ifk 2 Zn
kZnDZn:
Proof. A product of elements inZnremains inZnby Lemma 8.10.4. So ifk 2 Zn,
thenkZnZn. But by Lemma 8.10.6,kZnandZnare the same size, so they must
be equal.
(^13) Some other texts use the notationnforZn.