MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For relatively prime numbers $n$, let $ord_m(n)$ denote the order of $n$ modulo $m$, that is, the smallest number $k$ such that $m\mid(n^k-1)$. Now let $q$ and $r$ be two distinct prime numbers. Dose there exists a prime number $p$ such that $ord_p(q)<ord_p(r)$?

(Note: this question can be asked even if $q$ and $r$ aren't prime, as long as we avoid situations like $r=q^2$.)

share|cite|improve this question
Could we try to find a prime $p$ such that $r$ is a primitive root mod $p$, but $q$ is not ? – Dietrich Burde Jun 29 '13 at 18:38
Yes it is a good idea. – Ali Jun 29 '13 at 18:43
Proving this by that method seems difficult. If Artin's conjecture is false for $r$, this method cannot work - There is a finite list of primes that $r$ is a primitive root modulo, and you can use Dirchlet's theorem on primes in arithmetic progressions to find a distinct prime $q$ that is also a primitive root modulo each such prime. Since Artin's conjecture can't be proven, this is problematic. On the other hand, were the Artin conjecture known with $p$ restricted to lie in a given conjugacy class, we could just force $q$ to be a quadratic residue mod $p$ and solve the problem. – Will Sawin Jun 29 '13 at 20:09
Yes, good point. My first impression was, that this could be just the problem with the whole question. – Dietrich Burde Jun 29 '13 at 20:21
Ali, your usage of notation $\mathit{ord}$ makes it hard for me to absorb your question. Is your notation somewhere standard? It seems to me to be in a conflict with more common usages of $\mathit{ord}$. – Włodzimierz Holsztyński Jun 29 '13 at 22:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.