> I have answered everyquestion of > chapter zero in the graduate abstract algeb

Question

> I have answered everyquestion of
> chapter zero in the graduate abstract algebra text except
> one...the book is Dummit and Foote 2nd edition...the
> question is section 0.3 number 10, and it states....
>
> Prove that the number of elements in Z/nZ-{0} is thenumber
> given by the
> Euler-Phi (totient) function...
>
> The problem I am having is proving this with just the
> definition of
> Z/nZ-{0}...Now I have already proven that the fundamental
> definition is equivalent to stating the elements ofZ/nZ-{0}
> are precisely those that are relatively prime to n and ifI
> use this fact the proof is trivial, but is it possible to
> prove that the number of elements in Z/nZ-{0} is thetotient
> of n without using the relatively prime proposition?
>
> Without out using the proposition I have established the
> following bounds.
>
> 0 < a <= b < n in this line a and b are elements
> of Z/nZ-{0}...
>
> for ab = 1 mod n, which implies...
>
> ab - 1 = kn....in this line a and b are now integersbut
> still subject to
> the bounds 0 < a <= b < n...
>
> 1 <= k <= ab - 1 < (n-1)^2...
>
> I am not sure where to go from here but I have only given
> the problem a couple of hours of thought....
>
> I guess my main question is am I going in the wrong
> direction...Must one use the relatively prime propositionto
> prove this text question?
>
> thanks in advance and best wishes
> Patrick Rose
>

Explanation / Answer

The totient function is BY DEFINITION the number of positiveintegers less than n and relatively prime to n, and hence if youare showing that something equals the totient function of n thenyou are essentially making a bijection with the set of allrelatively prime integers to n. The fact that invertible elementsof Z/nZ are all relatively prime to n is an important aspect ofthis proposition.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.