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
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
1  
@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
2  
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
2  
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 (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..

share|improve this answer
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 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 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 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 at 23:31
1  
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

Your Answer

 
discard

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.