# About the existence of primitive root modulo prime

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

• I think you can write down a quick sketch here and underline the problem that you want to ask to be more precise. It would help you to get an answer quickly. :) – Kumar Jul 8 '19 at 14:18
• That's very difficult to read. I suspect though that $xy$ need not necessarily work. – Lord Shark the Unknown Jul 8 '19 at 14:32
• I will make things easier here. So I have an integer $x$ and $d$ is the smallest integer such that $x^{d} \equiv 1$ (mod p). We have another integer $y$ and the smallest integer $e$ such that $y^{e} \equiv 1$ (mod p). Then We want to construct an integer $t$ for which$f = LCM(d, e)$ is the smallest integer such that $t^{f} \equiv 1$ (mod p). That is what I got from there. So what if we take $t = xy$? $x^{k} \equiv 1$ (mod p) if and only if $k$ is a multiple of $d$ and $y^{l} \equiv 1$ (mod p) if and only if $l$ is divisible by $e$. So $LCM(d, e)$ really satisfies the requirements. – shota kobakhidze Jul 8 '19 at 14:47

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.$$

• Note: I checked the outline of the cited proof but I did not verify its correctness. – Bill Dubuque Jul 8 '19 at 18:52
• Thanks for the response. So, as I understood their proof is complicated because of the formal correctness reasons from the point of view of group theory? However, in this case $xy$ works but such reasoning could fail in some similar situations? – shota kobakhidze Jul 8 '19 at 20:43
• @shotakobakhidze Why do you believe that $xy$ works? – Bill Dubuque Jul 8 '19 at 20:59
• Yes, you are right. I realized that it is incorrect if in some step I have only left $y$ which is inverse of $x$ and that fails as you mentioned. Then the answer for them is not $LCM(d, e)$ but 1. Nice point. – shota kobakhidze Jul 8 '19 at 21:13
• @shota kobakhidze: The author avoids the issue of $y$ being the inverse of $x$ by choosing $y$ so that the order of $y$ doesn't divide $d$. Since the equation $x^d=1$ has at most $d$ solutions, such a choice is always possible (assuming $d < p-1$, we have $d\le{\large{\frac{p-1}{2}}}$). – quasi Jul 8 '19 at 21:28

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.

• Well, the main idea is to show that $f>d$. Then we can take $t$ instead of $x$ do the same things and got another $t'$ with $f'>f$. finally we will get the degree equal to $p - 1$ it is the maximal possible value for that. So is it correct in this case? – shota kobakhidze Jul 8 '19 at 15:06
• But the point is that for the originally chosen $x,y$, you don't know that $xy$ is a primitive root. – quasi Jul 8 '19 at 15:08
• I don't say that $xy$ will be a primitive root. I just say that $xy$ has a higher minimal degree $f$ such that $xy^{f} \equiv 1$ (mod p) than $x$. – shota kobakhidze Jul 8 '19 at 15:13
• $LCM(d, e) * GCD(d, e) = de$ we have $GCD(d, e) < e$ , so $LCM(d, e) > d$. If $LCM(d, e)$ is not equal to $p - 1$, I can take $t$ in place of $x$. why can I do it again this for $t$? the same reason why I could do for $x$. I just don't see what can interfere with this. – shota kobakhidze Jul 8 '19 at 15:21
• – shota kobakhidze Jul 8 '19 at 15:24