Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For prime $q$ can it be that $$ p^{q-1}\equiv 1 \pmod{q^k} $$ for some prime $p<q$ and for $k\ge 3$?

There doesn't seem to be a case with $k=3$ and $q<90000$, and I also checked for small solutions with $3<k\le 20$ and found none.

If we remove the condition $p<q$ then there are always solutions, e.g. $15441^{16}\equiv 1 \pmod{17^5}$. Also for $k=2$ there are many, e.g. $71^{330} \equiv 1 \pmod {331^2}$.

share|improve this question
I don't know. Agree about removal of condition $p\lt q$, use Hensel lifting and the Dirichlet theorem on primes in arithmetic progressions. –  André Nicolas Jul 31 '13 at 21:29
Short Pari/GP command line for probing more $q$ (adjust the range for $q$): k=3;forprime(q=3,1000,g=znprimroot(q^k)^(q^(k-1));h=g;for(j=1,q-2,p=lift(h);if(‌​p<q && ispseudoprime(p), print(p," ",q));h*=g)) –  ccorn Aug 1 '13 at 1:23
@Zander: Do you really mean $3< k\leq 20$ or $3< p \leq 20$? Testing higher $k$ when nothing is found for $k=3$ seems to make no sense to me. –  ccorn Aug 1 '13 at 2:01
If the requirement "$p$ prime" is dropped, there is precisely one $1<p<q\leq 100000$ with prime $q$, namely $(p,q)=(68,113)$ with $k=3$. –  ccorn Aug 1 '13 at 2:24
Assuming (without proof) the heuristics associated with Daniel Fischers argument, I figure that, given $q^k$, the probabilistic density of suitable $p$ is about $\frac{1}{q^{k-2}\log q}$. For fixed $k>3$ this indicates that the number of suitable $(p,q^k)$ pairs should be finite. For $k=3$ an infinite number of solutions seems "not implausible". Still searching, yet nothing found for $q$ up to $347000$. –  ccorn Aug 1 '13 at 12:34

1 Answer 1

Let $w>1$ be any integer and let $q$ be an odd prime and $w^{q-1}$ $\equiv 1 \pmod {q^3}$. Let v be a primitive root mod $q^3$ where $v^h$ $\equiv w \pmod {q^3}$. So $v^{h(q-1)}$ $\equiv 1\pmod {q^3}$. Therefore h=$q^2 k$ ; k >= 1. Assume k> 1 , then $w^{(q-1)/k}$ $\equiv 1\pmod {q^3}$ ; $v^{q^2 k-k}$ $\equiv(w/v^k) \pmod {q^3}$ , so $v^{(q^2 k -k)(q^2)}$ $\equiv 1 \pmod {q^3}$ ,therefore $(w/v^k)^{q^2}$ $\equiv 1\pmod {q^3}$. If the order of w mod $q^3$ is M then given $(w/v)^{q^2 M} $ $ \equiv 1 \pmod {q^3}$ ; $v^{q^2 M}$ $\equiv 1 \pmod {q^3}$. Yet this implies M = (q-1). Then the order of w mod $q^3$ is not <(q-1) contradiction. So k = 1. And $v^{q^2}$ $\equiv w \pmod q^3$. The order of w mod $q^3$ is (q-1). If w = p a prime < q then $p^{q-1}$ $\equiv 1 \pmod {q^3}$ where (q-1) is the order of p. p = (q-v); $(q-v)^q$ $\equiv(q-v)\pmod {q^3}$. So ($q^2$ $v^{q-1}$ -$v^q$) $\equiv(q-v)\pmod {q^3}$. Therefore $v^{q-1}$ ($q^2$-v) $\equiv (q-v)\pmod{q^3}$ ; $(-v q)\equiv (q^2-v q)\pmod{q^3}$ ; $q^2 \equiv 0 \pmod{q^3}$ Contradiction , so if p < q the order of p mod $q^3$ can not be (q-1)

share|improve this answer
Where have you used the hypothesis that the variables are to be prime? How do you account for the examples in the question and comments? –  Gerry Myerson Aug 15 '14 at 5:52
Moreover, where did $w^{(q^4+1)/(w+1)}$ come from? You aren't asserting $$q^4+1=(q+1)(q^3-q^2+q-1)$$ are you? –  Gerry Myerson Aug 17 '14 at 2:17
Sorry ,I should have said; let q^4 =U ,w^U=W mod (q^3). So (q^4-q^3+q^2-q+1)= Y ; w^Y =1 mod q^3 ; ((q^5)+1)/(q+1) =b , w^b=1 mod q^3, w^(q^5 + 1) =1 mod q^3 and w^(q^5-1) = 1 mod q^3.Therefore w^2 =1 mod q^3 –  user128932 Aug 19 '14 at 21:32
I reformatted your answer so I could read it, but I can't reformat comments. Please see how I edited your answer, and repost your comment in legible form. Or if your comment is meant to be a correction to your answer, then please edit it in to your answer (with proper formatting). –  Gerry Myerson Aug 19 '14 at 23:31
Firstly, I think you mean $\frac{q^5+1}{q+1}$, not $\frac{q^5+1}{w+1}$. Secondly, I think you mean $q^4-q^3+q^2-q+1=T$, since that is $\frac{q^5+1}{q+1}$. Thirdly, $w^T\equiv w$ mod $q^3$: how do you get that to be $\equiv 1$? Lastly, how are $u,v,y$ relevant? –  whacka Aug 22 '14 at 5:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.