Upper bounds on the order of a number in prime fields

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

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

• 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.
– C.P.
Apr 5, 2019 at 19:15
• For $k \ne 2$ you can consider generalized repunit primes: primes of the form $(k^n-1)/(k-1)$ 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.

• 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?
– C.P.
Apr 6, 2019 at 15:09
• 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. Apr 6, 2019 at 18:45
• I do believe it is true, but how can we prove that $j$ is usually $e^m$ ?
– C.P.
Apr 7, 2019 at 12:09
• 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. Apr 7, 2019 at 15:50