Counting an orbit length in $\mathbb{Z}/q^{\alpha}\mathbb{Z}$

Question

After working a lot of examples, I came up with the following conjecture:

"Let $p, q$ be unequal primes, and $\alpha \geq 0, a$ integers. Suppose $l > 1$ is the multiplicative order of $p$ modulo $q^{\alpha}$, and $d$ the largest power of $q$ which divides $a$. If $d < \alpha$, then the smallest number $t$ for which $p^ta \equiv a$ (mod $q^{\alpha}$) is exactly $l/q^d$."

Using these online calculators http://ptrow.com/perl/calculator.pl and http://users.otenet.gr/~bpapa/multiplicativeorder.htm may quickly convince you that my claim is true (or may allow you to find a counterexample).

Since $p^l \equiv 1$ we have $t \leq l$, and it is pretty clear that $t$ must divide $l$ as well. When $d = 0$, the assertion is obvious since $a$ can be canceled from both sides of a congruence.

Proving the general statement has so far eluded me. I've briefly tried showing that $p^{l/q^d}-1$ is divisible by $q^{\alpha - d}$ but not by $q^{\alpha-d+1}$ (which would complete the proof), but it doesn't seem trivial. Another approach may be to look at the quotient $\frac{p^l-1}{p^{l/q^d-1}}$ and write this as a sum of powers of $p$.

Does anyone see an obvious reason why the above conjecture is true? Any suggestions for an approach to take in proving it would be very helpful as well.

Answer 1

The conjecture is not quite true: By Dirichlet's theorem there is a prime of any possible order modulo $q^\alpha$, i.e. $l$ can be any number dividing $q^{\alpha-1}(q-1)$. Since $d$ can be any number between $0$ and $\alpha$ (both bounds included) $l/q^d$ is not always an integer.

The following is a bit messy and might contain some mistakes. Please read carefully:

$t$ is actually equal to the order of $p$ modulo $q^{\alpha-d}$ and is independent of $a$. Let $\zeta$ be a primitive root of unity for all powers of $q$. Then

\begin{equation} \large p=\zeta^{x\cdot q^{\alpha-1}(q-1)/l}, \end{equation} with $x$ coprime to $l$. So $t$ is the smallest integer such that $q^{\alpha-d-1}(q-1)$ divides $tx q^{\alpha-1}(q-1)/l$. We can omit $x$ in this condition because: It can only be divisible by $q$ if $l$ is not, so $q^{\alpha-1}(q-1)/l$ is automatically divisible by $q^{\alpha-d-1}$. If $\gcd(q-1,x)=d$ then $q^{\alpha-1}(q-1)/l$ is already divisible by $d$. So we are looking for the smallest $t$ such that $tq^{d}/l$ is an integer! In particular your conjecture is true if $l$ is divisible by $q^{d}$.