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. 
 A: Let $x=q^e-1$.  We have $q^{ke}-1 = \exp(k\cdot\ln (1 + x))-1$.  Because $\nu_p (x)\geq 1$, we have $\nu_p (\ln (1 + x)) = \nu_p(x)\geq 1$ (look at power series), so that $k\cdot \ln(1+x)$ is in the radius of convergence of the $p$-adic exponential (here we use the fact that $p$ is odd).
Looking again at the power series, we have $\nu_p(q^{ke}-1) = \nu_p (\exp(k\cdot\ln (1 + x))-1) = \nu_p(k\cdot\ln (1 + x)) = \nu_p(k) + \nu_p(q^e-1)$, which is exactly what we wanted to show.
A: Suppose that $p$ divides $q^n-1$.  Let $t=q^n$.  We have that $p \mid (t-1)$, and we want to show that $\nu_p (t^k-1) = \nu_p (t-1) + \nu_p (k)$.  We may assume that $k$ is prime, as the statement follows from this case by induction on the number of prime factors.
What we need to check is that $\nu_p (\frac{t^k-1}{t-1}) = \delta_{k,p}$.  This is straightforward when $k=2$ ($t+1$ cannot have an odd factor in common with $t-1$), so we will further assume that $k$ is an odd prime.
We compute the quantity $\frac{t^k-1}{t-1}=t^{k-1} + \cdots + 1$ modulo $p^2$.  Since $p$ divides $t^{\frac{j-1}{2}}-1$ for all odd $j$, we have $(t^{\frac{j-1}{2}}-1)^2 \equiv 0 \pmod{p^2}$, or $t^{j-1} + 1 \equiv 2t^{\frac{j-1}{2}} \pmod{p^2}$.
We have $t^{k-1} + \cdots + 1 = (t^{k-1} + 1) + t(t^{k-3} + 1) + \cdots + t^{\frac{k-3}{2}} (t^2+1) + t^{\frac{k-1}{2}}$.  By the above formula, taken modulo $p^2$ this is $2t^{\frac{k-1}{2}} + 2t \cdot t^{\frac{k-3}{2}} + \cdots + 2t^{\frac{k-3}{2}} \cdot t + t^{\frac{k-1}{2}} = kt^{\frac{k-1}{2}}$.
Since $(t,p)=1$, this last fact tells us exactly what we want.
I believe that we can use a similar proof to show that, if $4$ divides $q^n-1$, then $\nu_2 (q^{kn}-1) = \nu_2 (q^n-1) + \nu_2 (k)$.  This reflects the fact that the $p$-adic exponential converges on $p\mathbb{Z}_p$ for $p\neq 2$, but the $2$-adic exponential only converges on $4\mathbb{Z}_2$.
Note that there are strong parallels here to the Fibonacci sequence, which also has the property that if $p\mid F_n$, then $\nu_p (F_{kn}) = \nu_p(F_n) + \nu_p (k)$ (with the same caveat for $p=2$).  The proof is similar, and uses the Lucas numbers (or $p$-adic analysis, take your pick).
A: 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.
