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:


  • 1
    $\begingroup$ 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. :) $\endgroup$ – Kumar Jul 8 '19 at 14:18
  • 1
    $\begingroup$ That's very difficult to read. I suspect though that $xy$ need not necessarily work. $\endgroup$ – Lord Shark the Unknown Jul 8 '19 at 14:32
  • $\begingroup$ 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. $\endgroup$ – 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.$

  • $\begingroup$ Note: I checked the outline of the cited proof but I did not verify its correctness. $\endgroup$ – Bill Dubuque Jul 8 '19 at 18:52
  • $\begingroup$ 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? $\endgroup$ – shota kobakhidze Jul 8 '19 at 20:43
  • $\begingroup$ @shotakobakhidze Why do you believe that $xy$ works? $\endgroup$ – Bill Dubuque Jul 8 '19 at 20:59
  • $\begingroup$ 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. $\endgroup$ – shota kobakhidze Jul 8 '19 at 21:13
  • $\begingroup$ @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}}}$). $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – shota kobakhidze Jul 8 '19 at 15:06
  • $\begingroup$ But the point is that for the originally chosen $x,y$, you don't know that $xy$ is a primitive root. $\endgroup$ – quasi Jul 8 '19 at 15:08
  • $\begingroup$ 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$. $\endgroup$ – shota kobakhidze Jul 8 '19 at 15:13
  • $\begingroup$ $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. $\endgroup$ – shota kobakhidze Jul 8 '19 at 15:21
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – shota kobakhidze Jul 8 '19 at 15:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.