《简明数论》的简明笔记（上）：1~12节

按：数论貌似是我目前还接触太少的领域，遵从vls的推荐借了北大出版社的《简明数论》来浏览，还是很好玩儿的……下面是从中总结的一些比较新鲜的结论。

  • {a_i} 的最大公约数等于 {a_i} 的所有整系数线性组合组成的集合中的最小正整数；
    • 事实上，被最大公约数整除，等价于能表示成整系数线性组合。
  • 一次不定方程 ∑a_i*x_i=c 有解的充要条件是 c|({a_i})；
    • 解一次不定方程的算法（待实现）。
  • x^2+y^2=z^2 的本原解：x=r^2-s^2, y=2rs, z=r^2+s^2；
    • 其中r>s>0, (s,r)=1, 2不整除r+s；
    • 等价地刻画了单位圆周上的有理点。
  • Chebyshev不等式：\frac{x \ln{2}}{3 \ln{x}} < \pi(x) < \frac{6\ln{2}x}{\ln{x}}，\frac{n\ln{n}}{6\ln{2}} < p_n < \frac{8n\ln{n}}{\ln{2}}；
    • 其实重点在于：O(π(x))=x/log x，O(p_n)=n log n。
      • （π(x)即不大于x的素数个数；p_n即第n个素数。）
  • 数论函数：[完全]积性函数的充要条件；
    • 除数和函数\sigma(n)=\prod_{j=1}^{r}\frac{p_j^{a_j+1}-1}{p_j-1}；
    • F(n)=∑_{d|n}f(d) 保持f(n)的积性。（除数即Divisor）
  • Mobius函数：\mu(n)=\left\{ \begin{array}{ll} 1, & n=1\\ (-1)^r, & \text{n is product of }r\text{ distinct primes}\\ 0, & \text{otherwise} \end{array} \right；
      • 事实上与容斥原理很有关联；
      • 引理：\sum_{d|n}\mu(d)=[\frac{1}{n}]
    • 集合A中与K互质的元素个数S(A;K)= \sum_{d|K}\mu(d)|A_d|}，其中A_d是A中被d整除的子集；
    • 将A取不超过x的实数，K取不超过的所有素数的乘积，可得\pi(x)=\pi(\sqrt{x})-1+\sum_{d|K}\mu(d)[\frac{x}{d}]，这样可以在已知不超过的素数的前提下求π(x)。
      • 从算法的角度看似无意义？

October 2, 2008 · Filed under 生活志

3 Comments »

  1. CmYkRgB123 Said,

    October 2, 2008 @ 01:04

    好久没见DD写文章了。
    今天写了一篇，可惜看不懂。

  2. evalls Said,

    October 2, 2008 @ 22:01

    Mobius反演在组合里面还是很有价值的——不过还要扯到偏序集去了。

  3. 5l2 Said,

    October 6, 2008 @ 00:54

    就是二潘的初等数论吧～
    连分数也很有意思～

Leave a Comment