Let $n,a,b$ be integers such that $n$ and $a$ are coprime, and $n$ and $b$ are also coprime. According to the Prime number theorem for arithmetic progressions, the primes which are $a\mod n$ have the same asymptotic density as the primes which are $b\mod n$. Is the same true for semiprimes?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Yes "Riemann", your hypothesis is true.
Landau showed the count of all semiprimes grows as follows: $$ |\{pq \leq x\}| \sim \frac{x}{\log x}(\log \log x). $$
If $\gcd(a,n) = 1$ then a special case of the answer by Lucia here says $$ |\{pq \leq x : pq \equiv a \bmod n\}| \sim \frac{1}{\varphi(n)}\frac{x}{\log x}(\log \log x) $$ because Lucia's result implies that, for each $b, c \in (\mathbf Z/n\mathbf Z)^\times$, the number of semiprimes $pq \leq x$ where $p \equiv b \bmod n$ and $q \equiv c \bmod n$ is asymptotic to $(1/\varphi(n)^2)(x/\log x)(\log\log x)$. You have to be careful about avoiding duplicate counting of the products $pq$ depending on whether or not $b \equiv c \bmod n$. Therefore \begin{align*} |\{pq \leq x : pq \equiv a \bmod n\}| & = \sum_{\substack{(b,c) \bmod n \\ bc \equiv a \bmod n}} |\{pq \leq x : p \equiv b \bmod n, q \equiv c \bmod n\}| \\ & = \sum_{\substack{b \bmod n}} |\{pq \leq x : p \equiv b \bmod n, q \equiv b^{-1}a \bmod n\}| \\ & \sim \sum_{\substack{b \bmod n}} \frac{1}{\varphi(n)^2}\frac{x}{\log x}(\log \log x) \\ & = \frac{1}{\varphi(n)}\frac{x}{\log x}(\log \log x). \end{align*}
There is a more general result. For fixed $k \geq 1$, Landau showed $$ |\{p_1\cdots p_k \leq x\}| \sim \frac{x}{\log x}\frac{(\log \log x)^{k-1}}{(k-1)!} $$ (that is counting $k$-almost primes $p_1\cdots p_k$, not the $k$-tuples $(p_1,\ldots,p_k)$, so order and multiplicity matter when passing between these two methods of counting), and one then expects when $\gcd(a,n) = 1$ that $$ |\{p_1\cdots p_k \leq x : p_1\cdots p_k \equiv a \bmod n\}| \sim \frac{1}{\varphi(n)}\frac{x}{\log x}\frac{(\log \log x)^{k-1}}{(k-1)!}. $$ Such an estimate follows from Lucia's result by estimating $$ |\{p_1\cdots p_k \leq x : p_1 \equiv b_1 \bmod n, \ldots, p_k \equiv b_k \bmod n\}| $$ and summing those estimates over the $\varphi(n)^{k-1}$ different $k$-tuples $(b_1,\ldots,b_k)$ from $(\mathbf Z/n\mathbf Z)^\times$ where $b_1\cdots b_k \equiv a \bmod n$ (let $b_1, \ldots, b_{k-1}$ be arbitrary units mod $n$ and then $b_k \bmod n$ is determined by the congruence $b_1\cdots b_k \equiv a \bmod n$).
