如果需要数学竞赛或者大学数论number theory学科的辅导代写或者代考请随时练习我们，如果您在学习
- MAT417H1: Analytic Number Theory
- Math 675 Analytic Theory of Numbers lsa.umich.edu
或者类似的课程欢迎随时联系我们，UprivateTA™协助您在三分钟之内高质量搞定数论作业。
The sieve of Eratosthenes
The inclusion-exclusion principle or the Möbius inversion formula can in theory be used to calculate $\pi(x)$. For sufficiently large $x$, let us write
$$
P=\prod_{p \leqslant \sqrt{x}} p
$$
then an integer $n, \sqrt{x}<n \leqslant x$, is a prime number if, and only if, $(n, P)=1$. Thus we may write
$$
\pi(x)-\pi(\sqrt{x})+1=\sum_{n \leqslant x} \delta((n, P))=\sum_{d \mid P} \mu(d)\left\lfloor\frac{x}{d}\right\rfloor .
$$
At this stage, if we content ourselves with estimating $\lfloor x / d\rfloor$ using $x / d+O(1)$, we obtain
$$
\pi(x)-\pi(\sqrt{x})+1=x \prod_{p \leqslant \sqrt{x}}\left(1-\frac{1}{p}\right)+O\left(2^{\pi(\sqrt{x})}\right) .
$$
By Mertens’ formula, the main term in this estimate equals
$$
\left{2 \mathrm{e}^{-\gamma}+o(1)\right} x / \ln x
$$
but Chebyshev’s estimates show that the error term is larger than any power of $x$.
Brun’s combinatorial sieve
The sieve of Eratosthenes is based on the identity
$$
\mu * \mathbf{1}=\delta \text {. }
$$
Brun’s idea consists in introducing two auxiliary functions $\mu_1, \mu_2$, satisfying
$$
\mu_1 * \mathbf{1} \leqslant \delta \leqslant \mu_2 * 1
$$
and vanishing sufficiently often so that the number of terms in the resulting formula analogous to (4.1) is not prohibitive.
Brun’s initial choice, leading to what is customarily referred to in the literature as Brun’s pure sieve, is the following.
(Brun). Denote by $\chi_t$ the characteristic function of the set of integers $n$ such that $\omega(n) \leqslant t$. Then, for any integer $h \geqslant 0$, the functions defined by
$$
\mu_i(n):=\mu(n) \chi_{2 h+2-i}(n) \quad(i=1,2)
$$
satisfy the inequalities.
Proof. Since $\mu_i * 1(n)$ only depends on the squarefree kernel of $n$, it is enough to consider the case when $\mu(n)^2=1$. If $\omega(n)=k$, then, for each $r, 0 \leqslant r \leqslant k$, it is clear that $n$ has exactly $\left(\begin{array}{l}k \ r\end{array}\right)$ divisors $d$ such that $\omega(d)=r$. We can thus write, for any given $t \geqslant 0$,
$$
\mu \chi_t * \mathbf{1}(n)=\sum_{d \mid n, \omega(d) \leqslant t} \mu(d)=\sum_{r \leqslant t}(-1)^r\left(\begin{array}{l}
k \
r
\end{array}\right)=(-1)^t\left(\begin{array}{c}
k-1 \
t
\end{array}\right),
$$
where the last equality is easily obtained by induction on $t$.
Application to twin primes
Here we illustrate the results of the previous paragraph with Brun’s theorem on twin primes.
It is obvious that the difference between two consecutive odd primes must be at least 2 . When it is exactly 2 , we say that these primes are twins, such as ${3,5},{5,7},{11,13},{17,19},{29,31}$, etc. A famous conjecture asserts the existence of infinitely many twin primes.
Let us write
$$
\mathcal{J}:={p: p+2 \text { is prime }} \quad \text { and } \quad J(x):=|\mathcal{J} \cap[1, x]| .
$$
On the basis of an analytic approach, and in agreement with a heuristic probabilistic calculation, Hardy \& Littlewood (1922) conjectured that
$$
J(x) \sim 2 \prod_{p>2}\left(1-\frac{1}{(p-1)^2}\right) \frac{x}{(\ln x)^2} \quad(x \rightarrow \infty) .
$$
By Brun’s pure method, we establish the following result.
Theorem 4.5 (Brun). As $x$ tends to infinity, we have
$$
J(x) \ll x\left(\frac{\ln _2 x}{\ln x}\right)^2
$$
下面是一些经典的Quadratic Reciprocity题目
