0
$\begingroup$

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.

  • 1
    You changed the question completely.2012-12-09
  • 0
    I wouldn't say completely, I gave you a +1 for effort also2012-12-09
  • 0
    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.2012-12-09
  • 0
    @Ethan, have you by any chance meant minimum $k$, instead of $p$2012-12-09
  • 0
    Three edits in the last 5 seconds, no engagement with my questions.2012-12-09
  • 0
    I 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
  • 0
    You 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
  • 0
    Not now theres not, I don't think2012-12-09

2 Answers 2

2

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.

  • 0
    Dirichlets theorems is the case k=1, how does this apply when is greater then 12012-12-09
  • 0
    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$.2012-12-09
1

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.