Let $k$ be a fixed integer and for any prime number $p$ larger than $k$, let $\text{Order}(k,p)$ be the order of $k$ in $\mathbb{F}_p$ (i.e., $\text{Order}(k,p)$ is the least integer $n$ such that $k^n \equiv 1 \bmod{p}$).

Question. Give an upper bound to the sequence $$v_n=\inf_{t>n}\left(\text{Order}(k,p_t)\right),$$ where the $p_t$'s are the enumeration of all prime numbers in increasing order.

Fermat's little theorem provides the bound $v_n\leq p_n - 1$. Can a bound of $p_n^\epsilon$ be shown, for any $\epsilon>0$? Experiments suggest a bound of $\log(p_n)$.


2 Answers 2


This is not an answer, but maybe it's useful.

For example, take $k=2$. If $2^q-1$ is a Mersenne prime, it is $p_m$ where $q \sim \log_2 m$. Of course $\text{Order}(2, 2^q-1) = q$, so $v_n \le q$ if $n \le m$. If there are infinitely many Mersenne primes we will have $$\liminf_{n \to \infty} \frac{v_n}{\log_2(n)} \le 1$$

  • 1
    $\begingroup$ Yes, actually up to the generalized Mersenne conjectures you could have iterated log. Although I believed it not equivalent to such a conjecture, but I don't have any insight. It doesn't help for $k\neq 2$ though. $\endgroup$
    – C.P.
    Apr 5, 2019 at 19:15
  • $\begingroup$ For $k \ne 2$ you can consider generalized repunit primes: primes of the form $(k^n-1)/(k-1)$ $\endgroup$ Apr 5, 2019 at 22:51

Rephrasing, you are calling $ v_n $ the smallest integer $m$ such that $ k^m - 1$ has a prime factor not among the first $n$ enumerated primes.

If you have the standard numbering (primes in increasing order), then $v_n$ is going to look like $m$ or less right up until you hit the largest prime factor of $k^m - 1$, which presumably is larger than any prime factor of the same form for smaller values of $m$. Since these primes are often large, this accords with your observed values. This is because prime factors of $k^m - 1$ as $m$ varies are often larger than a fixed power (expect at least one of them to be larger than $k^{m/2} -1$).

However, let's pretend you pick the unluckiest enumeration, so that the first n primes are the factors of the first m numbers of the form $k^m - 1$. Zsigmondy says that for each m, a new prime appears as a factor of $k^m-1$ (unless m=6 and k=2). So $v_n$ will eventually be less than $n$, and conjecturally less than $n/log n$, even if you are unlucky.

Gerhard "The Fortunes Of Number Theory" Paseman, 2019.04.05.

  • $\begingroup$ Thank you for your comment, I have edited my question since I only care about standard numbering. I don't really understand your rephrasing. What is the link between the fact that $k^m-1$ has a prime factor which not among the first $n$ enumerated primes and the evolution of the $\text{Order}(k,p_i)$ sequence? $\endgroup$
    – C.P.
    Apr 6, 2019 at 15:09
  • $\begingroup$ If k has order m in a field of characteristic p (so k is not zero mod p), then p divides k^m - 1 and for n smaller than m p does not divide k^n - 1. Since you are doing inf over large primes, for primes q smaller than the largest prime p_j dividing any k^n - 1 up to k^m - 1, all v_i for i up to j will be m or less. j is usually like exp(m), as you have observed. Gerhard "Will Do The Slow Climb" Paseman, 2019.04.06. $\endgroup$ Apr 6, 2019 at 18:45
  • $\begingroup$ I do believe it is true, but how can we prove that $j$ is usually $e^m$ ? $\endgroup$
    – C.P.
    Apr 7, 2019 at 12:09
  • $\begingroup$ I would look at prime values of m and try to get a result that says that a large prime divisor exists among the set of k^m - 1 where prime m comes from a small interval. Right now, the best results talk about factors of cyclotomic polynomials for a single exponent, but you don't need such a strong requirement: you just need a nice sprinkling of large factors. Gerhard "To Go With The Frosting" Paseman, 2010.04.07. $\endgroup$ Apr 7, 2019 at 15:50

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.