Prove or disprove $ p^{r+s}\mid q^{ke} - 1 \iff p^s \mid k$.

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.