Congruences for sums of powers of an integer

For coprime integers $q$ and $e$, let $m(q,e)$ denote the least positive integer $t$ such that there exists a sum of $t$ powers of $q$ which is divisible by $e$. We prove that $m(q,e) \le \lceil e/\operatorname{ord}_e(q) \rceil$ where $\operatorname{ord}_e(q)$ denotes the (multiplicative) order of $q$ modulo $e$. We apply this in order to classify, for any positive integer $r$, the cases where $m(q,e) \geq \frac{e}{r}$ and $e ＞ r^4 - 2r^2$. In particular, we determine all pairs $(q,e)$ such that $m(q,e) \geq \frac{e}{6}$. We also investigate in more detail the case where $e$ is a prime power.