About the existence of primitive root modulo prime

Question

I was reading the theorem about the existence of an integer $t$, the primitive root modulo prime. The proof seemed a bit confusing. I mean the construction part. Why did not they immediately take $t = xy$ instead of $t = x^{m'}y^{m}$? I think $xy$ also satisfies the requirements. Thanks in advance. Here is the link of the proof:

http://www.math.stonybrook.edu/~scott/blair/Proof_Theorem_5.html#B

Answer 1

Let $x\in \{1,...,p-1\}$, and let $d$ be the order of $x$.

If $d=p-1$, then $x$ is a primitive root, and we're done.

Suppose $d < p-1$.

The plan is to find some element of $t\in\{1,...,p-1\}$ whose order exceeds $d$, and then iterate, using $t$ as the new $x$.

As the author argues, there exists $y\in\{1,...,p-1\}$ whose order doesn't divide $d$.

Let $e$ be the order of $y$.

If $e > d$, we can let $t=y$.

Since $e\not\mid d$, we can't have $e=d$.

Suppose $e < d$.

Your claim is that we can let $t=xy$.

Unfortunately, this doesn't always work.

As you correctly observed, since $e\not\mid d$, we get $\text{gcd}(d,e) < e$, hence $$ \text{lcm}(d,e) = \frac{de}{\text{gcd}(d,e)} = d\left(\frac{e}{\text{gcd}(d,e)}\right) > d $$ Let $f$ be the order of $xy$.

Clearly $f{\,|\,}\bigl(\text{lcm}(d,e)\bigr)$.

However, noting Bill Dubuque's post, and correcting my earlier answer, it's not automatic that $f=\text{lcm}(d,e)$.

In fact, we can't even claim $f > d$.

As an example, letting $p=31,x=7,y=23$, we get

• $x$ has order $d=15$.$\\[4pt]$
• $y$ has order $e=10$.$\\[4pt]$
• $xy$ has order $f=6$.

This shows that your idea of using $xy$ for the next iteration doesn't always work.

Answer 2

Generally it is not true that in an abelian group that if $\,x,y\,$ have order $\,j,k\,$ then $xy$ has order $\,{\rm lcm}(j,k),\,$ e.g. consider the case $\,y = x^{-1}.\,$ But it is true that there exists some element of order $\,{\rm lcm}(j,k),\,$ and this is what is proved there (see here for a few other proofs of order lcm-closure)

Remark $ $ Their proof can be simplified. By here: $ $ if $\,x,y\,$ have order $\,d,e\,$ then there are coprime $\,m',m\in \Bbb N\,$ with $\,(d,e)={m'}\,{m},\ (d/m',\,e/m)=1\,$ so $\,x^{\large m'},\, y^{\large m}$ have coprime orders $\,d/m',\, e/m\,$ therefore their product has order $\ (d/m')(e/m) = de/(d,e) = {\rm lcm}(d,e)$.

Unlike many proofs, the linked proof does not require expensive prime factorization. Instead it employs only gcds so it yields an efficient algorithm to compute $\,m',m.$