<s>[INST] 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. 
 [/INST] 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).
</s>