# Find a generator for the cyclic group of units

Find a generator for the cyclic group of units in $\mathbb{Z}/(\mathbb{2017Z})$.

attempt: consider $\mathbb{Z}/(\mathbb{2017Z})$ = {$x + \mathbb{2017Z} : x \in \mathbb{Z}$}.

Then a generator is $1 + \mathbb{2017Z}$ for the cyclic groups of units.

Can someone please verify this? Thank you

• fyi, correct notation is $2017\mathbb Z$ – Simon S Nov 9 '15 at 0:44

So there are a total of $\phi(2017)$ elements in your multiplicative group, and since $2017$ is prime $\phi(2017)=2016$. Breaking this down into prime factors we get that $2016=2^53^27$. By Lagrange's theorem, the order of every element divides the order of the group. So we just need to find an element for which the order does not divide $2016$. Try checking this for $2$, i.e. can we get $2^n\equiv 1mod(2107)$ for $n$ that divides $2016$?
The group $(\mathbf Z/2017\mathbf Z)^\times$ is cyclic, of order $2016$. Unfortunately the first natural candidate for a generator, $2$, has order 1008, and so is $3$. It is only with $5$ that we get an element of order $2008$.
You can do that with a hand-held caculator, using the fast exponentiation algorithm, in $15$ multiplications.