Can $p^{q-1}\equiv 1 \pmod {q^3}$ for primes $p<q$?

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

-
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

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)

-
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