Prove or disprove $ p^{r+s}\mid q^{ke} - 1 \iff p^s \mid k$. Let $p$ be an odd prime and $q$ be a power of prime. Suppose $e := \min\{\, e \in \mathbb{N} : p \mid q^e - 1 \,\}$ exists. Put $r := \nu_p(q^e - 1)$ (that is, $p^r \mid q^e - 1$ and $p^{r+1} \nmid q^e - 1$). What I want to prove is the following:

$ \forall k \in \mathbb{N},~ \forall s \in \mathbb{N}_0,~p^{r+s} \mid q^{ke} - 1 \iff p^s \mid k.$

I feel that this is true (but perhaps some upper bounds may needed for $k$ and $s$). How can I prove or disprove this statement?

Example:
If $p = 3,~q = 5$ then $e = 2,~r = 1$.


*

*$5^{1 \cdot 2} - 1 = 2^3 \cdot 3^{1 + 0}$

*$5^{2 \cdot 2} - 1 = 2^4 \cdot 3^{1 + 0} \cdot 13$

*$5^{3 \cdot 2} - 1 = 2^3 \cdot 3^{1 + 1} \cdot 7 \cdot 31$

*$5^{4 \cdot 2} - 1 = 2^5 \cdot 3^{1 + 0} \cdot 13 \cdot 313$

*$5^{5 \cdot 2} - 1 = 2^3 \cdot 3^{1 + 0} \cdot 11 \cdot 71 \cdot 521$



My attempt:
In case $(\Leftarrow)$,
$$\begin{align}
q^{ke} - 1 &= ((q^e - 1) + 1)^k - 1 \\
&= (q^e - 1)^k + k(q^e - 1)^{k - 1} + \dotsb + \binom{k}{2}(q^e - 1)^2 + k(q^e - 1).
\end{align}$$
I can see that the last term is divisible by $p^{r + s}$ from the assumption. But is it true for the former terms?
In case $(\Rightarrow)$, we may start by introducing the quotient and the remainder $k = ap^s + b~(0 \le b < p^s)$ and calculate similar expansion as before. 

I write an answer to reorganize the Slade's second answer for oneself.
What I would like to prove is the following proposition.

Proposition. Let $p$ be an odd prime. For every $t, k \in \mathbb{N}$, if $p \mid t - 1$ then 
  $$\nu_p\left(\frac{t^k - 1}{t - 1}\right) = \nu_p(k).$$

Once this has proved, the substitution $t = q^e$ gives an answer to the original question. Now for the proof.
Proof.
The proof is well-founded induction on $k$ with respect to strict divisibility.
In case $k = 2$. Since $2 \neq p \mid t - 1$ and 
$ \frac{t^k - 1}{t - 1} = t + 1 = (t - 1) + 2$,
the desired identity $\nu_p(\frac{t^k - 1}{t - 1}) = 0 = \nu_p(k)$ holds.
In case $k$ is odd prime. Since $p \mid t - 1$, the congruence relation $t^m - 1 \equiv 0 \pmod{p}$ hold for every $m \in \mathbb{N}$. And hence $(t^m - 1)^2 \equiv 0 \pmod{p^2}$, which is equivalent to $t^{2m} + 1 \equiv 2t^m \pmod{p^2}$. Therefore, as $k$ is odd,
$$\begin{align*}
\frac{t^k - 1}{t - 1} &= t^{k - 1} + \dotsb + t + 1 \\
&= (t^{k - 1} + 1) + (t^{k - 2} + t) + \dotsb + (t^{(k + 1)/2} + t^{(k - 3)/2}) + t^{(t - 1)/2} \\
&= (t^{k - 1} + 1) + (t^{k - 3} + 1)t + \dotsb + (t^2 + 1)t^{(k - 3)/2} + t^{(k - 1)/2} \\
&\equiv 2t^{(k - 1)/2} + 2t^{(k - 3)/2}t + \dotsb + 2tt^{(k - 3)/2} + t^{(k - 1)/2} \pmod{p^2}\\
&= kt^{(k - 1)/2}.
\end{align*}$$
From $p \nmid t$, a fact that $k$ is a prime and this congruence relation, we conclude that
$\nu_p\left(\frac{t^k - 1}{t - 1}\right) = \nu_p(k)$.
In case $k$ is composite number. Suppose $k = ab$ for some $a, b \in \mathbb{N} \setminus \{1\}$. Then from induction,
$$\begin{align*}
\nu_p\left(\frac{t^k - 1}{t - 1}\right) &=
\nu_p\left(\frac{t^{ab} - 1}{t - 1}\right) \\ &= 
\nu_p\left(\frac{(t^a)^b - 1}{t^a - 1}\right) + \nu_p\left(\frac{t^a - 1}{t - 1}\right) \\ &= 
\nu_p(b) + \nu_p(a) = \nu_p(ab) = \nu_p(k).
\end{align*}$$
From induction on $k$, the proposition established. Q.E.D.
