0
$\begingroup$

Suppose $d_1, d_2$ are two fixed coprime integers, $\frac{d_1}{d_2} \neq \pm 1$. Given any $n > 0$, can we find a prime number $p$ such that the order of $d_1d^{-1}_2$ in the multiplicative group of the field $\mathbb{Z}/p\mathbb{Z}$ be greater than $n$?

$\endgroup$
7
  • $\begingroup$ If $d_1/d_2 \ne \pm 1$, the order $\mod p$ is clearly at least $\log p/\log 2$, so yes. $\endgroup$ Oct 3, 2012 at 2:48
  • $\begingroup$ Hi, Felipe, how do you see the order is at least logp/log2? I am not a number theorist, so I might be a little slow on this. $\endgroup$
    – Xiaolei Wu
    Oct 3, 2012 at 2:56
  • 1
    $\begingroup$ I'm not sure how Felipe got $\log p / \log 2$, but if $d_1^m \equiv d_2^m \mod p$ then $|d_1^m - d_2^m| = p k \ge p$. So, at least one of $|d_1|^m, |d_2|^m$ has to be at least $p$. Choosing $p$ larger than $\max(|d_1|,|d_2|)^m$ means the order has to be greater than $m$. $\endgroup$ Oct 3, 2012 at 3:08
  • $\begingroup$ Hi, Felipe. I actually think you are wrong now. There are always elements in Z/pZ has order 2 since the multiplicative group has order p-1 which is an even number if p is odd. $\endgroup$
    – Xiaolei Wu
    Oct 3, 2012 at 3:20
  • $\begingroup$ Thank you, Douglas Zare. I see your proof now. I think I am going to close this question soon since it is actually very easy. $\endgroup$
    – Xiaolei Wu
    Oct 3, 2012 at 3:29

1 Answer 1

1
$\begingroup$

The answer to your question is "yes" (cf. Douglas Zare's comment). In fact, for all sufficiently large primes $p$, the order of $d_1 d_2^{-1}$ is greater than $n$. Here, "sufficiently large" means greater than $|d_1|^n$ and $|d_2|^n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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