Skip to content

《简明数论》的简明笔记(上):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)。
      • 从算法的角度看似无意义?

3 Comments

  1. CmYkRgB123 wrote:

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

    Thursday, October 2, 2008 at 01:04 | Permalink
  2. evalls wrote:

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

    Thursday, October 2, 2008 at 22:01 | Permalink
  3. 5l2 wrote:

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

    Monday, October 6, 2008 at 00:54 | Permalink

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*