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