Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How can I find the smallest prime power $p^k$ such that ${p^k} \equiv b\bmod a$ given fixed $k$, $b$, and $a$ where $2\leq k$ and $b \ne 0$, $gcd(a,b)=1$, or say that that no solution exists.

share|cite|improve this question
You changed the question completely. – glebovg Dec 9 '12 at 4:39
I wouldn't say completely, I gave you a +1 for effort also – Ethan Dec 9 '12 at 4:40
The question makes very little sense. It is not clear what is given, and what is variable. I'll assume the problem is, given $a,b,k$, find the smallest prime $p$ and so on. But then for many $a,b,k$ there's no answer, e.g., $b=6$, $a=12$; or $a=5$, $b=2$, $k=4$. Please edit it into a sensible question. – Gerry Myerson Dec 9 '12 at 4:45
@Ethan, have you by any chance meant minimum $k$, instead of $p$ – lab bhattacharjee Dec 9 '12 at 4:46
Three edits in the last 5 seconds, no engagement with my questions. – Gerry Myerson Dec 9 '12 at 4:48
up vote 2 down vote accepted

If $\gcd(a,b)\ne1$, then the only possibility is $p=b$, so you just check that to see if it works.

So assume $\gcd(a,b)=1$.

Then there's the question of whether $b$ is a $k$th power modulo $a$. This is a non-trivial question, not so easy to compute for large $a,b,k$. But if there is a solution to $x^k\equiv b\pmod a$, then, by Dirichlet's Theorem on primes in arithmetic progression, there is a solution where $x$ is prime. Finding the smallest one is probably going to be a question of doing a bunch of primality tests - I don't think there's any formula for getting the smallest.

share|cite|improve this answer
Dirichlets theorems is the case k=1, how does this apply when is greater then 1 – Ethan Dec 9 '12 at 4:56
If $x$ satisfies $x^k\equiv b\pmod a$, then $p^k\equiv b\pmod a$ if $p\equiv x\pmod a$. By Dirichlet there is a prime $p$ with $p\equiv x\pmod a$. – Gerry Myerson Dec 9 '12 at 6:23

Not in general, but when $a = p$ and $b = 0$ it is trivial. If you simply want to prove existence for $a \ne p$ and $b \ne 0$, then consider $p = 7$, $b = 1$ and $a = 3$. This proves existence.

Edit: This is an answer to the original question. The OP changed the question completely.

share|cite|improve this answer

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.