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.
Prime congruence help
-
1You changed the question completely. – 2012-12-09
-
0I wouldn't say completely, I gave you a +1 for effort also – 2012-12-09
-
0The 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. – 2012-12-09
-
0@Ethan, have you by any chance meant minimum $k$, instead of $p$ – 2012-12-09
-
0Three edits in the last 5 seconds, no engagement with my questions. – 2012-12-09
-
0I don't understand how it makes very little sense, you just wrote the question out again, aside from the no solution case I edited. – 2012-12-09
-
0You also mean $a \ne 1$, correct? – 2012-12-09
-
0@labbhattacharjee That was one of my edits -- apparently not. – 2012-12-09
-
0@Ethan, try to realize and *note* that what you ask and what Gerry suggests as possible question is completey different. – 2012-12-09
-
0Not now theres not, I don't think – 2012-12-09
2 Answers
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.
-
0Dirichlets theorems is the case k=1, how does this apply when is greater then 1 – 2012-12-09
-
0If $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$. – 2012-12-09
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.