# Math Help - observations of Gn (invertible classes of Zn)

1. ## observations of Gn (invertible classes of Zn)

Choose a value of n and count the number of elements in Gn (Gn is the set of invertible congurence classes of Zn). Can you discover any rules between n and the number of elements in Gn?

I have so far that if n is prime then [1]n, [2]n, ... , [n-1]n are all in Gn

also if n = 2^m for some integer m, Gn contains all odd elements of Zn

and finally, I know the product of any two elements of Gn is in Gn, for
n >= 2

what conclusions can I draw knowing only this information? What have I missed?

2. Originally Posted by minivan15
Choose a value of n and count the number of elements in Gn (Gn is the set of invertible congurence classes of Zn). Can you discover any rules between n and the number of elements in Gn?

I have so far that if n is prime then [1]n, [2]n, ... , [n-1]n are all in Gn

also if n = 2^m for some integer m, Gn contains all odd elements of Zn

and finally, I know the product of any two elements of Gn is in Gn, for
n >= 2

what conclusions can I draw knowing only this information? What have I missed?
Let $0 < a < n$. Then $a$ is invertible iff $ax\equiv 1(\bmod n)$ for some $x$. But this congruence is solvable if and only if $(a,n)=1$. Thus, all elements relatively prime to $n$ are invertible, there are $\phi(n)$ such elements.