When you work in Zn* and take repeated powers of an element, as you might have done in showing that 3 generates Z7*, it may seem that you are doing something quite abstract, but actually you were doing this in grade school! If you apply the long division algorithm to find the decimal representation of 1/13, for example, you generate the decimal fraction 0.0769230769230769... That 6-digit sequence 076923 just repeats over and over. When you examine what you are doing, you find you are just taking higher and higher powers of 10 mod 13! That is, the powers of 10 mod 13, namely
10^1 = 10
10^2 = 100 = 9 mo
10^3 = 90 = 12 mod 13
10^4 = 120 = 3 mod 13
10^5 = 30 = 4 mod 13
10^6 = 40 = 1 mod 13,
are exactly the numbers which you run into as you do the long division, at intermediate steps. (I can't show this here, because of the limitations of HTML, but we did it in class, and you can reconstruct it yourself just by dividing 13 into 1.0000... ) Thus the reason that the decimal fraction begins repeating after 6 digits is precisely that 10 has order 6 in Z13*.
The order of any element a in Zn* is just the smallest exponent m such that a^m = 1. The computation above shows that the order of 10 in Z13* is 6. Similarly you can show by computing powers of 2 that the order of 2 in Z13* is 12, which is exactly phi(13), meaning that Z13* is cyclic and has 2 as a generator.
Every element in Zn* has an order: that is, for each a there is some smallest exponent m such that a^m=1. Here is a proof. Starting with a, form the sequence of higher and higher powers: a, a^2, a^3, ... If you keep this up long enough you are sure to find some element which occurs a second time, since there are only a finite number of elements in Zn*, namely phi(n) elements. So there must exist j and k with j<k such that a^j=a^k. But a^j, like every element of Zn*, has an inverse, which is in fact a^(-j) (the jth power of the inverse of a). Multiplying by this inverse on both sides, we have 1=a^(k-j). Thus there is a power of a which is 1, and therefore there is a least power of a which is 1. That least power is the order of a.
A beautiful little theorem says that the order of any element a in Zn* divides phi(n), the number of elements in Zn*. Our example above illustrates this theorem. Working in Z13*, which has order 12, we found 10 has order 6 (which divides 12) and 2 has order 12 (which divides 12). The theorem says that all the other elements of Z13* must have orders which divide 12 also.
Here is a proof of the theorem. Choose any element a in Zn* and form the set of its distinct powers:
S={a, a^2, a^3, ..., a^m}
where m is the order of a. If it happens that m=phi(n), then S is all of Zn*, and obviously m divides phi(n). Otherwise there is some element b in Zn* which is not in S. Form the set
S_b = {ba, ba^2, ba^3, ..., ba^m}
by multiplying each element in S by b. Now the elements of S_b are all different from each other, because the powers of a are all different, and b has an inverse: ba^j=ba^k would imply a^j=a^k. Also the elements of S_b are all different from the elements of S: ba^j=a^k would imply b is a power of a, but it was chosen precisely because it is not a power of a. Thus S and S_b together have 2m elements. If 2m=phi(n), then all the elements of Zn* are accounted for, and once again, m divides phi(n) (the quotient is 2), and we are done. But if there are still more elements of Zn*, not in S or S_b, we choose one of them, call it c, and form
S_c={ca, ca^2, ca^3, ..., ca^m}
As before, these are m new elements, all distinct, and all different from the elements of S and S_b. If S, S_b, and S_c together exhaust Zn*, then 3m=phi(n), m divides phi(n), and we are done. Otherwise keep going. There are only a finite number of elements in Zn*, so this process has to terminate. In any case, Zn* has been split up into some number of sets, each having m elements, so that m divides phi(n).
(1) Use the example of the set generated by 10 in Z13* to illustrate the above theorem. That is, take the set
S={10, 9, 12, 3, 4, 1}
choose a suitable b, form S_b, and point out how the assertions of the proof are verified.
(2) Work in Z17* (i.e, multiplication mod 17) and find the set S generated by the element 4. Then find suitable b, c, ... and the corresponding sets S_b, S_c, ... in this case, and point out how this computation illustrates the proof of the theorem.
There is a "mod p" calculator in the Math 114 folder on the computers in Clapp 402. You can set the value of "p" with the "Set p" button, then do arithmetic in that modulus.