# Prime congruence help

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.

-
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

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.

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

-