# Thread: 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 $\displaystyle 0 < a < n$. Then $\displaystyle a$ is invertible iff $\displaystyle ax\equiv 1(\bmod n)$ for some $\displaystyle x$. But this congruence is solvable if and only if $\displaystyle (a,n)=1$. Thus, all elements relatively prime to $\displaystyle n$ are invertible, there are $\displaystyle \phi(n)$ such elements.