# Distribution of primes remainders

Naively, I would expect the natural density the number of a fixed prime $p$ with remainder $m$ to the other primes to be uniform

$$d(p,m) = \limsup\limits_{n\rightarrow\infty} \frac{a(n,m)}{n} = \frac{1}{p-1}$$

where $A(n,m) =\{ x \equiv p \ ( \bmod \ m), x\in\mathbb{P}_{<n} \}$, and $a(n,m)=|A(n,m)|$ and $1 \le m \le p-1$. A trivial test for small primes at $n<10^6$ seems to suggest that this may be true:

p m A(10**6, m)/n
3 1 0.499770694795
3 2 0.500216566027
5 1 0.249904456164
5 2 0.249968152055
5 3 0.250515936712
5 4 0.249598715891
7 1 0.166411883105
7 2 0.166437361461
7 3 0.166946928584
7 4 0.166488318174
7 5 0.166946928584
7 6 0.166755840913


Is there a way to show this is true for all primes and their remainders?

-

This fact about the distribution of primes has been proved. In fact it is a consequence of Dirichlet's analytic proof of his theorem on primes in arithmetic progressions.

What is proved is that a certain definition of "density" of sets of primes lying in a given invertible class mod $N$ is $\frac{1}{\phi(N)}$. In other words the primes are distributed uniformly amongst the classes of $\left(\mathbb{Z}/N\mathbb{Z}\right)^{\times}$ (except a few bad primes that divide $N$).

Your findings show this for $N$ prime.

There is a far reaching generalization of this called the Cebotarev Density theorem. The point is that the arithmetic group $\left(\mathbb{Z}/N\mathbb{Z}\right)^{\times}$ can be realised as the cyclotomic Galois group Gal$(\mathbb{Q}(\zeta_N)/\mathbb{Q})$. In fact there is a particular way to construct an isomorphism by assigning to each prime number it's Frobenius element, a very important element of the Galois group that measures arithmetic properties of splitting of primes in extensions.

Dirichlet's corollary now becomes that, for this particular extension of number fields, the prime numbers are uniformly distributed between the $[\mathbb{Q}(\zeta_N):\mathbb{Q}] = \phi(N)$ elements of the Galois group according to their corresponding Frobenius elements.

Cebotarev stated and proved the situation for any Galois extension of number fields $L/K$, except he found that you really need an abelian Galois group in order to get uniform distribution of primes amongst the $[L:K]$ possible Frobenius elements.

Why is this? Well in non-abelian extensions the Frobenius element is in general not well defined...it is really defined by a conjugacy class in the Galois group. In these cases the primes having a given Frobenius conjugacy class of size $k$ have density $\frac{k}{[L:K]}$ rather than $\frac{1}{[L:K]}$ in the abelian case.

-

Yes, this is Dirichlet's theorem on arithmetic progressions

-
No, Dirichlet's theorem only tells you that there are infinitely many primes for each possible coprime to $p$ remainder...nothing about the distribution. It is really a consequence of the proof of Dirichlet's theorem that provides it. For arbitrary number fields there is a generalization (Cebotarev density theorem). – fretty Sep 23 '13 at 14:34
@fretty Your comment seems to provide more information than this answer. Could you expand upon it and (now that I know what I'm looking for) and describe how it fits in with Chebyshev's bias? en.wikipedia.org/wiki/Chebyshev%27s_bias – Hooked Sep 23 '13 at 15:06
Obviously I don't know how much algebraic number theory you know but the wiki page will help: en.wikipedia.org/wiki/Chebotarev's_density_theorem – fretty Sep 23 '13 at 15:09
If you aren't familiar with number fields etc then just see the "relation with Dirichlet's theorem" section. – fretty Sep 23 '13 at 15:09
In fact you can study distribution of primes mod any $N$...there you should find that (apart from finitely many) you get a uniform distribution between the $\phi(N)$ classes of $\left(\mathbb{Z}/N\mathbb{Z}\right)^{\times}$. – fretty Sep 23 '13 at 15:11