Skip to main content
added 1468 characters in body
Source Link
KConrad
  • 50.6k
  • 9
  • 195
  • 276

Yes "Riemann", your hypothesis is true. Landau

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). $$$$ |\{pq \leq x : pq \equiv a \bmod n\}| \sim \frac{1}{\varphi(n)}\frac{x}{\log x}(\log \log x) $$ (Applybecause Lucia's result by consideringimplies that, for each $b \in (\mathbf Z/n\mathbf Z)^\times$$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 b^{-1}a \bmod n$,$p \equiv b \bmod n$ and sum those counts over all $b$$q \equiv c \bmod n$ is asymptotic to $(1/\varphi(n)^2)(x/\log x)(\log\log x)$. BeYou have to be careful about avoiding duplicate counting of the products $pq$ depending on whether or not $b \equiv b^{-1}a \bmod n$$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$, which canLandau 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 viewed asarbitrary units mod $b^2 \equiv a \bmod n$.$n$ and then $b_k \bmod n$ is determined by the congruence $b_1\cdots b_k \equiv a \bmod n$).

Yes. 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). $$ (Apply Lucia's result by considering, for each $b \in (\mathbf Z/n\mathbf Z)^\times$, the semiprimes $pq \leq x$ where $p \equiv b \bmod n$ and $q \equiv b^{-1}a \bmod n$, and sum those counts over all $b$. Be careful about avoiding duplicate counting of $pq$ depending on whether or not $b \equiv b^{-1}a \bmod n$, which can be viewed as $b^2 \equiv a \bmod n$.)

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

Source Link
KConrad
  • 50.6k
  • 9
  • 195
  • 276

Yes. 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). $$ (Apply Lucia's result by considering, for each $b \in (\mathbf Z/n\mathbf Z)^\times$, the semiprimes $pq \leq x$ where $p \equiv b \bmod n$ and $q \equiv b^{-1}a \bmod n$, and sum those counts over all $b$. Be careful about avoiding duplicate counting of $pq$ depending on whether or not $b \equiv b^{-1}a \bmod n$, which can be viewed as $b^2 \equiv a \bmod n$.)