Question

Show that the numbers 1, 3, 3^2 , . . . , 3^15 and 0 for a complete system of residues (mod 17). Do the numbers 1, 2, 2^2 , . . . , 2^15 and 0 constitute a complete system of residues (mod 17)?

Answer 1

Since is a cyclic group of order , the set is a complete set of residue modulo if and only if has order .

Now, by Fermat's little theorem, we have . On the other hand, , which implies . Therefore, .

By Lagrange's theorem, the order of any element in must divide the order of the group itself. Thus, if does not have order , its order will be one of . In any case, it must satisfy which is not the case. Hence, has order .

As explained above, this shows that is a complete system of residues modulo .

For the set , we notice that . Thus, has order . Therefore, is not a complete system of residues modulo .