# 二平方和

$$a^2\equiv-b^2\pmod p,$$

$$(\frac{a^2}{p})= (\frac{-1}{p})(\frac{b^2}{p}).$$

$$(\frac{a^2}{p})=(\frac{b^2}{p})=1$$

$$(\frac{-1}{p})=1.$$

$(a^2)^{2k-1}\equiv(-b^2)^{2k-1}\pmod p,$

$a^{p-1}\equiv-b^{p-1}\pmod p.$

$$p\bigm|(a^2+b^2)$$, 注意到 $$(a^2+b^2)\bigm|(a^{p-1}+b^{p-1})$$(因为 $$p-1=2(2k-1)$$), 于是

$p\bigm|(a^{p-1}+b^{p-1}).$

$$(\frac{a^2}{p})= -(\frac{b^2}{p}).$$

$$(\frac{a^2}{p})= (\frac{b^2}{p})=0.$$

$$a^2+b^2=d^2(a_1^2+b_1^2).$$

$$p\bigm|d^2(a_1^2+b_1^2).$$

$$(p,a_1^2+b_1^2)=1,$$

$$p\bigm|d^2,$$

$$p\bigm|d.$$

$$n=(a+bi)(a-bi).$$

$$a+bi=(a_1+b_1i)(a_2+b_2i)\cdots(a_l+b_li),$$

$$a-bi=(a_1-b_1i)(a_2-b_2i)\cdots(a_l-b_li),$$

$$n=(a_1^2+b_1^2)(a_2^2+b_2^2)\cdots(a_l^2+b_l^2).$$

$$\prod_{i=0}^{n}F_i=F_{n+1}-2.$$

$$a_1=m(m+1)$$

$$a_2=a_1(a_1+1)=m(m+1)(m(m+1)+1)$$

$$n=\prod_{i=1}^{l}p_i.$$

$$\varphi(n)=1.$$

$$\varphi(n)=\prod_{i=1}^{l}(p_i-1)$$

$$\Bbb P := \{2,3,5,7,\dotsc\}.$$

$$\pi(x) := \#\{p\leq x|p\in\Bbb P \}$$

$$n$$ 有下述的分解式

$$n=\prod_{i=1}^{\pi(x)}p_i^{\alpha_i},$$

$$n=u^2v,$$

$$v=\prod_{i=1}^{\pi(x)}p_i^{\beta_i},$$

$$x\leqslant\sqrt{x}2^{\pi(x)},$$

$$\pi(x) \geqslant \frac{\log x}{\log 4},$$

$$\lim_{x\rightarrow\infty}\pi(x)=\infty.$$

$\sum_{i=k+1}^\infty\frac 1{p_i}\leqslant\frac 12.$

$$\sum_{i=k+1}^\infty\frac x{p_i}\leqslant\frac x2.$$

$$N(x)\leqslant\sqrt{x}2^k.$$

$N(x)\geqslant x-\sum_{p=k+1}^\infty\frac xp\geqslant\frac x2,$

$\sqrt{x}2^k\geqslant\frac x2$

$$n!=\prod p^{\sum\left[\frac n{p^i}\right]},$$

$$\sum_{i\geqslant1}\left[\frac n{p^i}\right]<\sum_{i\geqslant1}\frac n{p^i}=\frac{n}{p-1}\leqslant n,$$

$$n!<(\prod p)^n.$$

$\sigma:\{1,2,\dotsc,2^N\}\to\{0,1,2,\dotsc,N\}^l$

$n\mapsto\Big(\alpha_1,\alpha_2,\dotsc,\alpha_l\Big),$

$N\geqslant\log_2n = \sum_{i=1}^l \alpha_i\log_2p_i\geqslant\sum_{i=1}^l\alpha_i\geqslant \max\Big\{\alpha_1,\alpha_2,\dotsc,\alpha_l\Big\},$

Suppose there are a total of  $$N$$ primes, $$2=p_1<p_2<\dotsb<p_N$$, and pick $$K$$ such that $$2^K>(K+1)^N$$. Consider the mapping $$f:\{1,\dotsc,2^K\}\to\{0,\dotsc,K\}^N$$ defined by

$f(x):=(k_1,\dotsc,k_N),$

where $$x=p_1^{k_1}\dotsm p_N^{k_N}$$ is the prime factorization of $$x$$. Here, the fact that $$f(x)\in\{0,\dotsc,K\}^N$$ follows from

$K\geqslant\log_2x=\sum_{n=1}^Nk_n\log_2p_n\geqslant\sum_{n=1}^N k_n \geqslant \max\{k_1,\dotsc,k_N\}.$

Then $$f$$ is injective by the fundamental theorem of arithmetic, which contradicts the pigeonhole principle. $$\Box$$

[2012.10.14 收入Dustin G. Mixon 的证明]