# 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

Let $w>1$ be any integer (not just a prime) and let $q$ be an odd prime and $w^t\equiv 1 \pmod {q^3}$ with $t=q-1$. Let v be a primitive root mod $q^3$ where v^$(q^2)$ = w mod $q^3$( if such a primitive root exists). v^$(q^2 -1)$ = w v^(-1) mod $q^3$ , so v^$(q^2 -1)(q^2)$ = 1 mod $q^3$ ,therefore (w v^(-1))^ $q^2$ = 1 mod $q^3$. If the order of w mod $q^3$ is M then M divides q-1 . [w v^(-1)]^$q^2 M$ = 1 mod $q^3$ so v^($q^2$ M) = 1 mod $q^3$. Yet this implies M = (q-1). So if there exists v , a primitive root mod $q^3$ such that v^($q^2$) = w mod $q^3$ then the order of w mod $q^3$ is (q-1). I hope these observations help..
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 at 2:17
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 at 5:56