6
$\begingroup$

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.

  • 3
    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.2012-04-14
  • 0
    Ah, thanks. $ $2012-04-14
  • 1
    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.2012-04-14
  • 1
    @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..)2012-04-14
  • 2
    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.2012-04-14
  • 0
    @KCd: I was just asking because I was proving the integrality (in general) of Gauss's formula whose value on $q=p^k$ is the the number of irreducible polynomials of degree $m$ in $F_q$. I ended up in a spot where I used Dirichlet's theorem, but I was reluctant to use such powerful technology, which is why I asked if perhaps there was a weaker form of Dirichlet's theorem that I could use instead. It appears that this is not the case.2012-04-14
  • 2
    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 http://en.wikipedia.org/wiki/Necklace_polynomial.2012-04-15
  • 0
    @KCd: The proof where I used Dirichlet's theorem proves it for all $a\in \mathbf{Z}$. You look $\sum_{d|n}\mu(n/d)a^d$ modulo $p^{\operatorname{ord}_p(n)}$. Then it splits into two cases, when $\operatorname{gcd}(p,a)=1$ and otherwise. You can use Dirichlet's theorem for the coprime case, and in the other case, you just follow your nose by looking at when the various Möbius terms vanish.2012-04-15
  • 1
    If 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

0 Answers 0