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