[PDF] The Structure of (Z/nZ) Apr 6 2018 If (Z/

View - Download The Structure of (Z/nZ)

Previous PDF

Next PDF

The Structure of (Z=nZ)

R. C. Daileda

April 6, 2018

The group-theoretic structure of (Z=nZ)is well-known. We have seen that ifN= p n11pnrrwithpidistinct primes andni2N, then the ring isomorphismof the Chinese remainder theorem provides a multiplication preserving bijection (Z=nZ)!(Z=pn11Z) (Z=pnrrZ) (below we will dene such a function to be agroup ismorphism). This reduces the study of the general unit group (Z=nZ)to understanding the unit group (Z=pnZ)with prime power modulus. It turns out that the structure of these groups depends on whether or not p= 2. Moreover, whenpis odd, the proof of the main structure theorem on (Z=pnZ)will be broken down into the casesn= 1,n= 2 andn3 separately. Before we can get into any of this, however, we need some preliminary results.

1 Gauss' Result on'(n)

Givenn2Nand a positivedjnlet

S d=f1anj(a;n) =dg and T d=n knd j1kd;(k;d) = 1o The setsSdpartition the integers from 1 tonaccording to their GCD withn.

We claim that

S n=d=Td:(1)

First note that any elementknd

2Tdsatises

knd ;n knd ;dnd =nd (k;d) =nd and hence belongs toSn=d. Conversely, fora2Sn=dwe have nd = (a;n) =an=d nd ;dnd =nd an=d ;d )an=d ;d = 1; and hencea=an=d nd 2Td. We apply (1) to prove the following essential result on Euler's'function. 1

Corollary 1(Gauss).For anyn2N,

X djn'(d) =n; the sum running over the positive divisors ofn. Proof.Asdruns through the (positive) divisors ofn, so doesn=d. Hence, f1ang=[ djnS d=[ djnS n=d since (a;n) takes on the value of each divisor ofnat least once. Since the setsSdare pairwise disjoint (no integer has more than one GCD withn), taking the size of each of the sets above, and using equation (1), yields n=X djnjSn=dj=X djnjTdj=X djn'(d):Example 1.The (positive) divisors of 20 are 1, 2, 4, 5, 10 and 20. We see that X dj20'(d) ='(1) +'(2) +'(4) +'(5) +'(10) +'(20) = 1 + 1 + 2 + 4 + 4 + 8 = 20; as claimed.

2 Cyclic Groups and Primitive Roots

Denition 1.LetGbe a group andg2G. The set

hgi=fgnjn2Zg is called thecyclic subgroup (ofG) generated byg. IfG=hgifor someg2Gwe say that

Giscyclic.N

Remark 1.The sethgiis itself a group under the binary operation onG. Hence the use of the termsubgroup.H Denition 2.If (Z=nZ)is cyclic with generatora+nZ, we say thatais aprimitive root modulon.N Remark 2.Although entirely standard, we nd the termprimitive rootto be somewhat archaic. We have introduced it in the interest of cultural literacy, but will rarely use it, preferring the termgeneratorinstead.H 2

Example 2.

(Z;+) is cyclic since it is generated by1, e.g.n=n1 for andn2Z. (Z=nZ;+) is cyclic since it is generated by 1 +nZ, i.e.a+nZ=a(1 +nZ) for any a2Z. (Z=8Z)isnotcyclic since for anyx+ 8Z2(Z=8Z), hx+ 8Zi=f1 + 8Z;x+ 8Zg 6= (Z=8Z) sincex21(mod 8) for all oddx. Therefore there does not exist a primitive root modulo 8. Every cyclic group is abelian sincegmgn=gm+n=gn+m=gngmfor allm;n2Z. Given an elementg2G, the size ofhgiis intimately related to ord(g).

Lemma 1.LetGbe a group andg2G. Thenjhgij= ord(g).

Proof.First assume ord(g) =1. Then no two powers ofgare equal, for otherwise we'd havegi=gjwithi < jand hencegji=ewithji >0, implying ord(g)<1. Thushgi is innite (it can be bijected withZ), and the result follows.1 Now suppose ord(g) =n2N. The group elementse;g;g2;:::;gn1must be distinct since otherwise, as above, we end up withgk=efor some 1kn1, contradicting the minimality ofn= ord(g). Moreover, given anym2Zwe can writem=qn+rwith

0rn1 so that

g m= (gn)qgr=eqgr=gr2 fe;g;g2;:::;gn1g: It follows thathgi=fe;g;g2;:::;gn1g, and since these elements are distinct,jhgij=n= ord(g).Remark 3. IfGis a nite group andg2G, thenGis cyclic and generated bygif and only if ord(g) =jGj. We will tacitly assume this fact from now on. H Lemma 2(Generators of a Cyclic Group).LetG=hgibe a nite cyclic group of ordern.

ThenG=hhiif and only if

h2 fgaj(a;n) = 1g: Proof.Suppose thath=gawith (a;n) = 1. Then clearlyhhi hgias every power ofhis a power ofg. For the reverse containment, use Bezout's lemma to writera+sn= 1. Then h r=gar=g1sn=g(gn)s=ge=g. Hence every power ofgis a power ofhand so hgi hhias well. Now suppose thathgi=hhi. Thenh=gafor somea2Z. Sinceg2 hhi,g=hr=gra for somer2Z. Henceg1ra=eso thatn= ord(g) (by the previous lemma) divides 1ra. This means thatra1(modn) so thatain a unit modulonand hence (a;n) = 1.1

This is the reason we say that an element that doesn't have an order has innite order: so that this lemma will hold in this

case as well. 3 Corollary 2.LetGbe a nite cyclic group of ordern. ThenGhas exactly'(n)generators. Proof.WriteG=hgiso that the distinct elements ofGaree,g,g2;:::;gn1. Then according to Lemma 2 the number of generators ofGis #f1an1j(a;n) = 1g='(n):Example 3. The only generators of (Z=nZ;+) area(1 +nZ) =a+nZwhere (a;n) = 1, i.e. the elements of (Z=nZ). One can easily show that 2 + 11Zgenerates (Z=11Z). Since this group has order

10, the only other generators are (2 + 11Z)3= 8 + 11=Z, (2 + 11=Z)7= 7 + 11Zand

(2 + 11=Z)9= 6 + 11=Z.

3 The Structure of(Z=pZ)

The structure of prime power modulus unit groups begins simply with the case of prime modulus. Recall that whenpis a prime,Z=pZis a eld, i.e. a commutative ring in which every nonzero element is a unit. We will be interested in counting the number of elements in (Z=pZ)of each allowable orderdjp1. Because we can't determine these elements directly, we will instead interpret them as solutions of the polynomial equationxd1 = 0, which turns the problem into counting the roots of special polynomials. Since we are working in a eld, there is a natural limit to the number of roots a polynomial can have. To deduce this limit we rst prove the following lemma.

Lemma 3.LetFbe a eld and let

f(x) =anxn+an1xn1++a1x+a0; ai2F; an6= 0 be apolynomial overFof degreen. Ifr2Fandf(r) = 0, then f(x) = (xr)g(x) whereg(x)is a polynomial overFof degreen1. Proof.Replacexby (xr) +rinf(x), apply the binomial theorem to each summand and collect terms with common powers ofxr. Sincef(r) = 0 this yields f(x) =an(xr+r)n+an1(xr+r)n1++a1(xr+r) +a0 =an(xr)n+bn1(xr)n1++b1(xr) +f(r) = (xr)an(xr)n1+bn1(xr)n2++b1+ 0 (bi2F) = (xr)an(xr)n1+bn1(xr)n2++b1 = (xr)anxn1+cn2xn2++c0 |{z} g(x)(ci2F); where in the nal line we have again used the binomial theorem to expand each power of xr.4

Theorem 1(Lagrange).LetFbe a eld and let

f(x) =anxn+an1xn1++a1x+a0; ai2F; an6= 0 be a polynomial overFof degreen. Then the equationf(x) = 0has at mostnsolutions in F. Proof.We induct onn. Whenn= 1 we have the equation a

1x+a0= 0; a0;a12F; a16= 0;

which has the unique solutionx=a11a02F, sinceFis a eld. Now assume the result holds for all polynomials overFof some degreen1. Consider f(x) =an+1xn+1+anxn++a1x+a0; ai2F; an+16= 0: Iff(x) = 0 has no solutions inFthere is nothing to prove, so assume thatf(r) = 0 for somer2F. According to the lemma,f(x) = (xr)g(x) for some polynomialg(x) over Fof degreen. SinceFis a eld, we nd that iff(s) = 0 for somes2F,s6=r, then g(s) = 0. Sinceg(x) has degreen, by our inductive hypothesis there are at mostnpossible values fors. Hencef(x) = 0 has at mostn+ 1 solutions, and we have established the next

case. Induction gives us the result.Lemma 4.Letpbe a prime. For eachdjp1, the equationxd1 = 0has exactlydsolutions

inZ=pZ. Proof.By Fermat's little theorem the equationxp11 = 0 hasexactlyp1 solutions in Z=pZ, namely the elements of (Z=pZ)(0+pZis certainly not a solution). Writep1 =kd so that x p11 =xdk1 = (xd1)(xd(k1)+xd(k2)++xd+ 1): Thenxp11 = 0 if and only ifxd1 = 0 orxd(k1)+xd(k2)++xd+1 = 0, sinceZ=pZ is a eld. Lagrange's theorem tells us that the numberN1of solutions toxd(k1)+xd(k2)+ +xd+ 1 = 0 inZ=pZsatisesN1dkd=p1d. Likewise,N2, the number of solutions toxd1 = 0 inZ=pZ, must satisfyN2p1(p1d) =d. Asxp11 = 0 has exactlyp1 solutions we therefore have2 p1N1+N2= (p1d) +d=p1 and hence we must actually haveN1=p1dandN2=d. The latter equality gives the statement of the lemma.Remark 4. Note that ifa+pZsolvesxd1 = 0, then we actually havea+pZ2(Z=pZ). Indeed, in this case (a+pZ)1= (a+pZ)d1. In view of the remark above, we see that fordjp1, the solutions ofxd1 = 0 inZ=pZ are the elements of (Z=pZ)with order dividingd.2 We do not knowa priorithat the two factors ofxp11 don't share roots. 5 The proof of the preceding lemma allows us to conclude thatxd(k1)+xd(k2)++ x d+ 1 = 0 (wherekis the divisor ofp1 complementary tod) has exactlyp1d solutions inZ=pZand that these must be distinct from the solutions toxd1 = 0. H Lemma 5.Letpbe a prime,djp1. The number of elements of(Z=pZ)of orderdis either0or'(d).3 Proof.Suppose there exists ana+pZof orderdin (Z=pZ). LetHdenote the subgroup it generates. ThenHcontainsdelements, each of which is a solution toxd1 = 0. Given that any other element of orderdwould generate a subgroup with the same property, and thatxd1 = 0 has onlydsolutions, it must be thatHcontains every element of orderd. Nowb+pZ2Hhas orderdif and only ifH=hb+pZiand according to the corollary to

Lemma 2,Hhas exactly'(d) generators. This is what we needed to show.We are nally ready to determine the structure of (Z=pZ).

Theorem 2.Letpbe a prime. For everydjp1, there are exactly'(d)elements of(Z=pZ) of orderd. In particular,(Z=pZ)is cyclic.

Proof.For eachdjp1 let

(d) denote the number of elements of (Z=pZ)of orderd.

According to Lemma 5,

(d)'(d) for alld. Moreover, since every element has some order dividingp1, and by Gauss' result, p1 =X djp1 (d) =X djp1'(d):

This equality implies that, in fact,

(d) ='(d) for alld, as claimed. In particular, (p1) = '(p1)1 so that elements of orderp1 =j(Z=pZ)jexist, i.e. (Z=pZ)is cyclic.Example 4. pGenerators of (Z=pZ)32 + 3Z

52 + 5Z, 3 + 5Z

73 + 7Z, 5 + 7Z

112 + 11Z, 6 + 11Z, 7 + 11Z, 8 + 11Z

132 + 13Z, 6 + 13Z, 7 + 13Z, 11 + 13Z

173 + 17Z, 5 + 17Z, 6 + 17Z, 7 + 17Z, 10 + 17Z, 11 + 17Z, 12 + 17Z, 14 + 17Z

192 + 19Z, 3 + 19Z, 10 + 19Z, 13 + 19Z, 14 + 19Z, 15 + 19Z

Remark 5.

We've given an indirect (nonconstructive) proof of the fact that (Z=pZ)is cyclic be- cause we have to: there's no (known) way to actuallynda generator of (Z=pZ) without actually knowingp. Once we have one generator it is easy to produce them all via Lemma 2, but it's nailing down the existence of that rst generator that's so tricky.3

We will soon see that 0 never occurs, but we need this intermediate result in order to establish that stronger fact.

6 Artin's (primitive root) conjecturestates that ifa6=1;, then the set of primesp for whicha+pZgenerates (Z=pZ)has positive asymptotic density in the set of all primes. In particular, there are innitely many such primes. However, there is not a single value ofafor which this result has been established. Hooley proved that Artin's conjecture is a consequence of the Generalized Riemann Hypothesis for zeta functions of number elds, another conjectural result. There are partial results, however, along the lines of Artin's conjecture thathavebeen proven. It is a consequence of a result of Heath-Brown, for example, that at least one of 2, 3 or 5 is a primitive root for innitely many primes. The argument we've used to establish Theorem 2 is easily generalized to any nite subgroup of the multiplicative groupFof an arbitrary eldF. That is, ifFis a eld andGis a nite subgroup ofF, thenGis cyclic. Again, the proof is nonconstructive: it does not provide a generator, but merely establishes that one must exist. H

4 The Structure of(Z=p2Z)

We will deduce the structure of (Z=p2Z)from that of (Z=pZ). The two groups are naturally connected by ahomomorphism, a group-theoretic tool we will take advantage of to simplify our presentation. Denition 3.LetG,Hbe groups. A functionf:G!His called ahomomorphismpro- videdf(ab) =f(a)f(b) for alla; b2G. A bijective homomorphism is called anisomorphism. N

Example 5.

It is not dicult to show that iffis a homomorphism thenf(eG) =eHandf(an) = f(a)nfor alln2Z.

Ifm;n2Nandmjn, we have seen that thereduction map

r:(Z=nZ)!(Z=mZ) a+nZ7!a+mZ preserves multiplication of congruence classes, hence is a homomorphism of groups. Ifn1;n2;:::;nr2Nare pairwise relatively prime andN=n1n2nr, we have seen that :(Z=NZ)!(Z=n1Z)(Z=n2Z) (Z=nrZ) a+NZ7!(a+n1Z;a+n2Z;:::;a+nrZ) is a multiplication preserving bijection, hence is an isomorphism of groups. IfG=hgiis a cyclic group of ordern, it is not dicult to show that the mapc: Z=nZ!Ggiven bya+nZ7!gais a well-dened (additive to multiplicative) group 7 homomorphism. Sinceacan take on any value inZ,cis clearly surjective, so by Lemma

6 and the pigeon-hole principle it is an isomorphism.

Similarly, if ord(g) =1, then the mapbc:Z!Gdened bya7!gais a surjective homomorphism. The proof of Lemma 6 shows thatbcis also injective and is therefore an isomorphism. The moral is that every cyclic group is isomorphic to one ofZ=nZorZ, i.e. up to relabelling these are theonlycyclic groups! Our primary application of group homomorphisms will be through the following result. Lemma 6.Letf:G!Hbe a homomorphism of groups. Ifa2Ghas nite order, then ord(f(a))jord(a).

Proof.Letn= ord(a). Thenan=eGso that

e H=f(eG) =f(an) =f(a)n)ord(f(a))jn:We are now ready for the main result of this section. Theorem 3.Letpbe a prime,n2N. Then(Z=p2Z)is cyclic. Proof.Letg+pZbe a generator for (Z=pZ). We claim that eitherg+p2Zorg+p+p2Z generates (Z=p2Z). Letr: (Z=p2Z)!(Z=pZ)denote the reduction map. Sinceris a homomorphism andr(g+p2Z) =r(g+p+p2Z) =g+pZ, according to Lemma 6 the orders ofg+p2Zandg+p+p2Zare both divisible byp1. Sincej(Z=p2Z)j=p(p1), their orders are therefore eitherp1 orp(p1). Assume thatg+p2Zdoesnotgenerate (Z=p2Z). Then according to the preceding paragraph it must have orderp1, and to show thatg+p+p2Zisa generator it suces to show that (g+p+p2Z)p16= 1 +p2Z, i.e. that (g+p)p161(modp2). If we apply the binomial theorem we obtain (g+p)p1=gp1+ (p1)gp2p+kp2

1 + (p1)gp2p(modp2);

sinceg+p2Zhas orderp1. This nal quantity is1(modp2) if and only ifp2j(p1)gp2p

orpj(p1)gp2. But (p;p1) = (p;g) = 1, so this cannot occur. The proof is complete.Example 6.The rst example of a generator of (Z=pZ)thatdoes notgenerate (Z=p2Z)

occurs whenp= 29 andg= 14 + 29Z:ghas order 28 inbothgroups. According to the proof, this means that 14 + 29 + 29

2Z= 43 + 292Zgenerates (Z=292Z)instead.

8

5 The Structure of(Z=pnZ)for Oddp

The passage from (Z=p2Z)to (Z=pnZ)will be achieved via the following result. Lemma 7.Letpbe an odd prime,n2N. If(x;p) = 1, thenxp1(modpn+1)if and only ifx1(modpn). Proof.Suppose thatx1(modpn). Thenpnjx1. Furthermore,pjx1 impliesx1 (modp) so that x p1+xp2++x+ 11 + 1 ++ 1p0 (modp) so thatpjxp1+xp2++x+ 1. Therefore p n+1j(x1)(xp1+xp2++x+ 1) =xp1)xp1 (modpn+1): We prove the converse by induction onn. Whenn= 1 suppose we havexp1(modp2).

By Fermat's theorem we have

x p=xxp1=x(1 +kp) = 1 +`p2)x1 (modp) as claimed. Now suppose we have proven the result for somen2Nand assumexp1 (modpn+2). Thenxp1(modpn+1) so thatx1(modpn) by the inductive hypothesis.

Writex= 1 +kpnso that

x p= (1 +kpn)p= 1 +pkpn+pX j=2 p j k jpnj= 1 +pkpn+`p2n+1+kppnp; since all the middle binomial coecients p jare divisible byp. Since 2n+ 1n+ 2 and npn+ 2 (asp3), we nd that

1xp1 +kpn+1(modpn+2)

so that p n+2j(1 +kpn+1)1 =kpn+1)pjk:

Sincex= 1 +kpn, it follows thatx1(modpn+1). Induction completes the proof.Remark 6.This result isfalseifp= 2, and this is what prevents (Z=2nZ)from being

cyclic forn3. For example,x21(mod 8) for all oddx, but it is certainly not true that x1(mod 4) for all oddx.H Theorem 4.Letpbe an odd prime,n2N. Then(Z=pnZ)is cyclic. Proof.We induct onn2, the base case having been established in the preceding section. Now suppose we have proven that (Z=pnZ)is cyclic for somen2 with generatorg+pnZ. We claim thatg+pn+1Zgenerates (Z=pn+1Z). Lettingr: (Z=pn+1Z)!(Z=pnZ)denotequotesdbs_dbs20.pdfusesText_26

[PDF] calcul des quartiles d une série statistique continue

[PDF] classe de congruence

[PDF] paramètres de dispersion et de position

[PDF] écart type relatif

[PDF] écart absolu moyen

[PDF] les origines de la guerre d'algérie

[PDF] paraphrasing exercises with answers pdf

[PDF] paraphrasing techniques

[PDF] cat devant une paraplegie pdf

[PDF] tétraplégie pdf

[PDF] la paraplegie

[PDF] physiopathologie paraplégie

[PDF] paraplégie niveau lésionnel

[PDF] lésion médullaire cervicale

[PDF] prise en charge paraplégie