0
$\begingroup$

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?

  • 1
    @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.2011-12-29

3 Answers 3

1

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.

3

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.

  • 1
    @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$.2011-12-28
3

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.

Now, expanding on Qiaochu's answer:

  • $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?

  • 1
    @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.2011-12-29