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?


1 Answer 1


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$).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.