# Determine a generator $g$ of the group $\mathbb{Z}_p^\times$ given some elements and their inverses

Is there a way of finding a generator of a multiplicative group $G = \mathbb{Z}_{41723027}^\times$ given some elements of the group :

S = $\{ 4, y=1063, 1064, y^{-1}=12049830, 41723026 \}$

In the exersice it says as additional information that there is exactly one generator in this set.

Can you explain me why there is only one generator and give some outline of the method I should use to find this generator?

-
Unlikely because finding the multiplicative inverse of $y \bmod p$ is easy with the Euclidean algorithm but finding a primitive root is not (though the least one is frequently quite small). –  lhf Dec 27 '11 at 18:59
I assume you mean the group $G = (\mathbb{Z}/p\mathbb{Z})^\times$. Finding the generators of this group for $p\in\mathbb{N}$ is hard, however, if $p$ is a power of an odd prime, twice that, $2$, or $4$ then the group is generated by one element, and the generators are called primitive roots modulo $n$. –  Alex Becker Dec 27 '11 at 19:00
–  Alex Becker Dec 27 '11 at 19:00
does that mean the generator is 4 ?? –  user21953 Dec 29 '11 at 17:36
@Turan x^41723026=1 for any x so what you have written doesn't fully prove 4 isn't a generator. You probably meant Euler's criterion which would prove it. –  David Marquis Dec 29 '11 at 19:24

That $S$ contains exactly one generator for the group is a promise to us by the author; this is just meant to make our calculations simpler. Think of this as a multiple choice question where exactly one option is the correct generator and our job is to figure out which.

• $4 = 2^2$ cannot be a generator; why?

• Since $41723026 \equiv -1 \pmod {41723027}$, it follows that this just generates the subgroup $\{ \pm 1 \}$; so this is not a generator.

• Finally, $y$ is a generator if and only if $y^{-1}$ is also one. Since we are promised that $S$ contains a unique generator, neither can be the generator we are looking for.

What does that leave us with?

-
@Svrivatsan 4 = 2^2 cannot be a generator because 1063 = y is a prime number and cannot be expressed as a power of 2 Why if y is a generator must y^-1 must be also ? The only element remains in the set is y^-1 so this must be a generator. How I can prove it? Can you recommend me a website to read about primitive elements except wikipedia? –  gosom Dec 28 '11 at 17:35
Every power of $y$ is also a power of $y^{-1}$; hence the subgroup generated by $y$ is contained in the subgroup generated by $y^{-1}$. In the opposite direction, $\langle y^{-1} \rangle \subseteq \langle y \rangle$. Putting together both of these observations, $\langle y^{-1} \rangle = \langle y \rangle$. This is true for all $y$. Now specialise for the case when $y$ or $y^{-1}$ is a generator. –  Srivatsan Dec 29 '11 at 3:20
@gosom Your reasoning for $4$ makes no sense; you should only ask whether $1063 = 2^a$ modulo $p$ (for some $a$). So whether $1063$ is prime or not is not relevant to the matter. –  Srivatsan Dec 29 '11 at 3:22
The general approach to testing if x is a primitive root is to find the factorization of phi(n) into $p_{1}^{\alpha_{1}}$,...,$p_{k}^{\alpha_{k}}$. In order to be a primitive root, the largest power $p_{i}$ dividing phi(n) also divides the order of x. This test will tell you why 4 is not a primitive root. –  David Marquis Dec 29 '11 at 18:42
@gosom Notice that $4^{\frac{p-1}{2}} = 2^{p-1} = 1$ modulo $p$, so the period of $4$ modulo $p$ is at most $\frac{p-1}{2}$. In particular it is not a generator. –  Srivatsan Dec 29 '11 at 18:43

The crucial bit of information is that exactly one element of $S$ is a generator. The way to do this problem is by process of elimination: show that every element except one can't be a generator, so the one that remains must be a generator.

-
I think that the number of generators is Φ(|G|) = Φ(|41723026|) and since 41723026 = 2 * 1987 * 10499 Φ(|G|) = 1 * 1986 * 10498 definetely not 1 Am i right? –  gosom Dec 28 '11 at 0:09
@gosom The problem doesn't say there is one generator for the group, just that there is only one generator for the group contained in the set $S$. –  Keenan Kidwell Dec 28 '11 at 0:20

This is somewhat of a moot point, but here comes anyway.

If we want to positively exclude the chance that the problem could have several correct answers, then the steps

Step #1: $1063\equiv 41723027\equiv 3\pmod{4}$, both of these are prime;

Step #2: $41723027\equiv 277 \pmod{1063}$, also $277$ is a prime, but $277\equiv 5\pmod 8$;

Step #3: $1063\equiv232\pmod{277}$, $232=8\cdot 29$, and

Step #4: $277\equiv 16=4^2 \pmod{29}$;

give the necessary data to conclude (by repeated applications of quadratic reciprocity) that $1063$ is a quadratic residue modulo $41723027$, and hence cannot be a generator for the same reason that $4$ cannot be one.

-