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
@ccorn Hmm, strange why the primality of $p$ should enter into this. Makes me suspicious a large counterexample may exist. –  user7530 Aug 1 '13 at 6:07
show 5 more comments

Your Answer


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

Browse other questions tagged or ask your own question.