In: Advanced Math
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)?
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
.