The Question:
Let n be a positive integer and let $G_n = \left\{[a] ∈ \mathbb{Z}_n ; \text{gcd}(a,n) = 1\right\}$ be the group of invertible elements in (Zn,·), where ”·” represents the product (mod n).
Prove that $(G_{125},·)$ is a group with 100 elements. Use Lagrange’s theorem to find all possible sizes of subgroups of $G_{125}$. Hence prove that [2] is a generator for $(G_{125}, ·)$. (You may use without checking the following identities (mod 125): $2^{10} ≡24,2^{20} ≡76,2^{25} ≡57$)
My Attempt: We can see that $\left|G_{125}\right| = 100$ by using the fact that only multiples of 5 in $\mathbb{Z}_{125}$ are not in $G_{125}$, of which there are 25.
By Lagrange, the order of a subgroup $<d>$ of $G$ divides the order of $G$. So the set of all possible sizes of subgroups in $G_{125}$ $:= \left\{a ; \text{gcd}\left(a,100\right) = a, a\in\mathbb{Z}\right\} = \left\{1,2,4,5,10,20,25,50,100\right\}$
At this point I'm stuck. The logic I tried using is that if [2] (mod 125) is a generator of $G_{125}$ then the cyclic subgroup $<[2]>$ should have the same order as $G_{125}$, that is, $2^{\text{ord}\left(G_{125}\right)}≡1$ (mod 125).
It's clear from above that the order of this subgroup can only be one of the numbers from the set of possible sizes of subgroups. It's not going to be any of the first 7 elements (simple calculations and the hint given in the question show this).
So I'm left with 50 and 100. How do I show that the order of $<[2]>$ is 100 and not 50? ($2^{50}$ and $2^{100}$ are huge unusable numbers.)
Or am I using the wrong method of proving that [2] generates $G_{125}$?
Best Answer
Hint if $\, 2^{\large n}\equiv 1\pmod{\!125}$ then ditto $\!\bmod 5\,$ so $\,4\mid n,\,$ by $\,2\,$ has order $4$. But $\,4\nmid 50$.
Or $\bmod 5^{\large 3}\!:\ 2^{\large 50} = (2^{\large 10})^{\large 5}\equiv (-1\!+\!25)^{\large 5}\equiv (-1)^{\large 5}\, $ via Binomial Theorem (other terms $\equiv 0)$