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.
Weak Dirichlet's theorem for powers of primes
6
$\begingroup$
number-theory
-
1If you'd like to read$a$direct proof of this fact about Necklace polynomials, see Concrete Mathematics, Graham-Knuth-Patashnik, Chapter 4. – 2012-04-15