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.

  • 2
    $\begingroup$ Why should $l$ be divisible by $q^d$? If you take $p=19$, $q^\alpha=9$ then $l=1$ and $t=1$ for any choice of $a$ but $d$ depends only on $a$ (for $a=3$ it is $1$ and hence $l/q^d=1/3$) $\endgroup$
    – MichalisN
    Commented Jul 27, 2013 at 18:24
  • $\begingroup$ okay, it doesn't have to be in the case $p \equiv 1$ (mod $q^{\alpha}$). but it seemed like the quotient was an integer for every example I tried. I wonder if that's like a degenerate case, or if there's a counterexample with $t > 1$. $\endgroup$
    – D_S
    Commented Jul 27, 2013 at 18:37

1 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}$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .