# Weak Dirichlet's theorem for powers of primes

Let $p$ be a prime, and let $m$ be an integer coprime to $p$. Then fix a natural number $k>0$. Is there any result that is simpler than the full Dirichlet's theorem that proves the existence of a prime $q$ and a natural number $j>0$ such that $m\equiv q^j\pmod{p^k}$? Obviously Dirichlet's theorem furnishes an infinite number of pairs of the form $(q,1)$, but it's also not an elementary thing to prove.

-
I doubt it. Note, by the way, that the usual proof of Dirichlet's theorem in fact first proves the set of prime powers satisfying a congruence condition has the expected density. Since the set of non-prime prime powers (that is, $q^j$ with $j > 1$) has density 0 among all prime powers, you can remove non-prime prime powers from the count and thus have shown that the primes alone fitting the congruence condition have the expected density. –  KCd Apr 14 '12 at 18:23
If $m$ happens to be a primitive root modulo $p^k$, then this question is equivalent to asking whether there exists a prime $q$ that is a primitive root modulo $p^k$. In theory that's easier than restricting $q$ to be in a single residue class, but I don't know of any easier proof. –  Greg Martin Apr 14 '12 at 19:28
@Harry, the reason why prime powers first appear rather than primes is that when you take a logarithmic derivative of an Euler product your get a Dirichlet series supported on prime powers, not on primes alone. The way non-prime prime powers are suppressed has several variations. One way is that a series over $q^j$ has the terms with $j = 1$ separated out, and what's left is shown to be a Dirichlet series abs. convergent back to $s = 1/2$, so that part can be -- and is -- absorbed into an error term for $s \rightarrow 1$. Alternatively there could be some preliminary lemmas about (continued..) –  KCd Apr 14 '12 at 20:11
summatory functions over primes up to $x$ and prime powers up to $x$ (for the prime number theorem these are denoted $\theta(x)$ and $\psi(x)$, if you want to compare with what is in books), which are shown to have the same asymptotic growth, so attention is focused, for technical reasons, on the sum over prime powers even though the one over primes may be of initial interest. –  KCd Apr 14 '12 at 20:12
Whoa, I never heard of a proof of that using Dirichlet's theorem. By "in general" I assume you mean you want to show $(1/n)\sum_{d|n}\mu(n/d)a^d$ is an integer for every (positive?) integer $a$, not just for prime power $a$. For $a \geq 1$ these sums actually count something. See en.wikipedia.org/wiki/Necklace_polynomial. –  KCd Apr 15 '12 at 4:08