Skip to content

Tag Archives: 数学

《简明数论》的简明笔记(上):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不等式:,; 其实重点在于:O(π(x))=x/log x,O(p_n)=n log n。 (π(x)即不大于x的素数个数;p_n即第n个素数。) 数论函数:[完全]积性函数的充要条件; 除数和函数; F(n)=∑_{d|n}f(d) 保持f(n)的积性。(除数即Divisor) Mobius函数:; 事实上与容斥原理很有关联; 引理: 集合A中与K互质的元素个数,其中A_d是A中被d整除的子集; 将A取不超过x的实数,K取不超过的所有素数的乘积,可得,这样可以在已知不超过的素数的前提下求π(x)。 从算法的角度看似无意义?