# Finding cyclic group $\mathbb{Z}_n^\times$ of prime order

It can be proven that multiplicative group of integers modulo $$N$$ defined as

$$\mathbb{Z}^\times_N = \{ i\in \mathbb Z : 1\leq i\leq N−1\; \text{ and }\; \gcd(i,N)=1 \}$$

is cyclic for a prime $$N$$ and that if it is of prime order, then every non-identity element in the group is a generator of this group.

How can I find such $$N$$?

I wrote a simple program and brute-forced for $$i \in \mathbb Z; i\in [1, 300 000]$$ and found no group of prime order so far.

• How about $N=3$? – kccu Jan 19 at 22:38
• If $N$ is prime, then your group has $N-1$ elements , which is a prime only for $N=3$ – Peter Jan 19 at 22:38
• Note that the condition $\gcd(i, N)$ is vacuous if $N$ is prime and $1 \le i \le N-1$, so as per Peter's comment your group has $N-1$ elements. – Rob Arthan Jan 19 at 22:43
• In case you are confused by why only $N = 3$ works, note that the only two consecutive integers which are both prime are $\{2, 3\}$. You That's because $2$ is the only even prime. – jordan_glen Jan 19 at 23:13
• I was rejecting $N = 3$ as a trivial case, heh :) So just to make sure I properly understand implications here: for $\mathbb{Z}_n^\times$, when looking for a generator, we must pick a random number from $[2, N-1]$ and check if it matches Euler's criterion? We can not select $N$ in such a way that we'll know upfront what the generator is. Is that correct? – omnomnom Jan 20 at 8:14