114 II Divisibility
(ii)for any k∈N,akhas order d/(k,d);
(iii)H={ 1 ,a,...,ad−^1 }is a subgroup of G and d divides n.
Proof Anyk∈Ncan be written in the formk=qd+r,whereq≥0and0≤r<d.
Sinceaqd=(ad)q=1, we haveak=1 if and only ifar=1, i.e. if and only ifr=0,
by the definition ofd.
It follows that ifakhas ordere,thenke=[k,d]. Since [k,d]=kd/(k,d),this
impliese=d/(k,d). In particular,akagain has orderdif and only if(k,d)=1.
If 0≤j,k<d, puti=j+kifj+k<dandi=j+k−difj+k≥d.Then
ajak=ai,andsoHcontains the product of any two of its elements. If 0<k<d,
thenakad−k=1, and soHcontains also the inverse of any one of its elements. Finally
ddividesn, by Lagrange’s theorem that the order of a subgroup divides the order of
the whole group.
The subgroupHin Lemma 31 is thecyclic subgroup generated by a.ForG=
Z×(m), the case which we will be interested in, there is no need to appeal to
Lagrange’s theorem, sinceZ×(m)has orderφ(m)andddividesφ(m), by Proposition 25
and Lemma 31(i).
A groupGiscyclicif it coincides with the cyclic subgroup generated by one of its
elements. For example, then-th roots of unity inCform a cyclic group generated by
e^2 πi/n. In fact the generators of this group are just the primitiven-th roots of unity.
Our next result provides a sufficient condition for a finite group to be cyclic.
Lemma 32A finite group G of order n is cyclic if, for each positive divisor d of n,
there are at most d elements of G whose order divides d.
Proof IfHis a cyclic subgroup ofG, then its orderddividesn. Since all its elements
are of order dividingd, the hypothesis of the lemma implies that any element ofG
whose order dividesdmust be inH.Furthermore,Hcontains exactlyφ(d)elements
of orderdsince, ifageneratesH,akhas orderdif and only if(k,d)=1.
For each divisordofn,letψ(d)denote the number of elements ofGof or-
der∑ d. Then, by what we have just proved, eitherψ(d)=0orψ(d)=φ(d).But
d|nψ(d)=n, since the order of each element is a divisor ofn,and∑
d|nφ(d)=n,
by Proposition 24. Hence we must haveψ(d)=φ(d)for everyd|n. In particular, the
groupGhasψ(n)=φ(n)elements of ordern.
The condition of Lemma 32 is also necessary. For letGbe a finite cyclic group of
ordern, generated by the elementa,andletdbe a divisor ofn.Anelementx∈Ghas
order dividingdif and only ifxd=1. Thus the elementsakofGof order dividingd
are given byk=jn/d, withj= 0 , 1 ,...,d−1.
We now return from group theory to number theory.
Proposition 33For any prime p, the multiplicative groupF×pof the fieldFpis cyclic.
Proof PutG =F×pand denote the order ofGbyn. For any divisordofn,the
polynomialtd−1 has at mostdroots inFp. Hence there are at mostdelements ofG
whose order dividesd. The result now follows from Lemma 32.