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.

  • 6
    $\begingroup$ How about $N=3$? $\endgroup$ – kccu Jan 19 at 22:38
  • 6
    $\begingroup$ If $N$ is prime, then your group has $N-1$ elements , which is a prime only for $N=3$ $\endgroup$ – Peter Jan 19 at 22:38
  • 3
    $\begingroup$ 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. $\endgroup$ – Rob Arthan Jan 19 at 22:43
  • 1
    $\begingroup$ 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. $\endgroup$ – jordan_glen Jan 19 at 23:13
  • $\begingroup$ 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? $\endgroup$ – omnomnom Jan 20 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.