Feb 16

《初等数论》读书笔记：同余

Art of Science 1 Comments

这里的同余包含了同余和同余方程两个章节。

基本的同余概念可以从带余除法中推导出来。使用带余除法，我们可以得到同余式的相关运算性质。

接下来，我们引入同余类和剩余系的概念。剩余系主要是介绍了既约剩余系。我们从既约剩余系的定义中引出了Euler函数。Euler函数是一个积性函数，也就是说如果(m1,m2)=1，那么$\varphi(m_1m_2)=\varphi(m_1)\varphi(m_2)$。Euler函数有如下的计算式 $\varphi(m)=m\prod_{p|m}(1-\frac{1}{p})$，特别的，当m=pk时，我们有$\varphi(p^k)=p^{k-1}(p-1)$。我们还有\sum_{d|m}\varphi(d)=m，我们可以从中看出Mobius函数的一点影子。

接下来，我们由一个性质得到了一个重要的定理：Fermat-Euler定理。这个性质是，对于一个模m，它的任何一个既约剩余系中所有元素的乘积模m是相同的，也可以表述为(a,m)=1时，x遍历m的既约剩余系当且仅当ax遍历m的既约剩余系。我们得到$a^{\varphi(m)}\equiv 1\pmod{m}$，以及当m=p时，对于任意的a，我们有$a^p\equiv a\pmod{p}$。前面的式子被称为Fermat小定理，后面的式子被称为Euler定理。

Wilson定理是如下的内容$r_1\cdots r_{p-1}\equiv -1\pmod{p}$，也就是对于一个素数p>3，它的既约剩余系中所有数的乘积模p为-1。特别的，我们有$(p-1)!\equiv -1\pmod{p}$。事实上，p不取1,2,4,pk,2pk时，p的既约剩余系的积模p得1。Wilson虽然不能用来高效地检验素数，但是可以被用来简化运算。

同余方程是多项式同余的形式。其最简单的形式是一次同余方程。我们可以用带余除法和辗转相除法得到其解。中国剩余定理用来求解一次同余方程组。对于一个一次同余方程组$x\equiv a_j\pmod{m_j},1\leq j\leq k$，这里m1,...,mk两两既约。那么其解为$x\equiv M_1M_1^{-1}a_1+\cdots+M_kM_k^{-1}a_k\pmod{m}$，m=m1...mk，m=mjMj，以及$M_j^{-1}$是Mj模mj的逆。这个解的正确性容易带入验证。如果m1,...,mk并非两两既约，则可以化为各个方程都是模pk的形式更加方便。

关于模为素数的二次同余方程，我们只需要讨论$x^2\equiv d\pmod{p}$的形式。对于模p，如果一个d能使得方程有解，那么我们称d为模p的二次剩余；否则d就是模p的二次非剩余。我们可以用Euler判别法来进行判断。如果$d^{(p-1)/2}\equiv 1\pmod{p}$，那么d就是模p的二次剩余；如果$d^{(p-1)/2}\equiv -1\pmod{p}$，那么d就是模p的二次非剩余。

我们还可以引进Legendre符号和Jacobi符号来进行进一步的研究。Gauss二次互反律也是进一步的探讨对象。具体内容可以参见原书或者nmbr.rar。

Feb 13

《初等数论》读书笔记：整除

Art of Science 0 Comments

一上来作者介绍了Peano公理。这个公理告诉我们，自然数就是一个有起点的、存在后继的无限整数集合。自然数的性质都可以通过这个抽象的定义来推导。我们一般使用1,2,3,...，是因为它本身具有代表性。至于0的问题，一般在不涉及的情况下不考虑。从Peano公理我们得到了数学归纳法和两个自然数的原理：最小和最大自然数原理。数学归纳法在数论当中可以用来证明多项的命题，也可以用来证明取值范围是固定连续整数域的恒等式或者命题。

接下来是整除的概念，我们一般是把它和带余除法结合起来看。从基本定义我们就可以推导很多有用的性质。从整除我们得到一类非常有用的数：素数。素数具有很多的性质。关于素数的判定也是一个很重要的课题，一般而言我们有试除法、Fermat素性检验、Miller-Rabin素性检验。A.K.S算法是第一个被证明的可以在多项式时间内检验素数的算法。

接下来作者介绍了公约数和公倍数的理论。我们又得到了互素的概念。这在书中仅仅是一个先头的简单介绍，作者接着引进了带余除法的概念。这是一个非常有用的概念，我们可以通过它进行很多讨论余数的证明。整数分类也是来自于带余除法。有了带余除法的概念之后，我们就可以讨论很多情况下余数的性质。带余除法是初等数论中极其重要的内容。

接下来就是辗转相除法。这也是一个来自于带余除法的内容。

我们现在可以建立最大公约数理论。带余除法、辗转相除法和整系数线性组合是3种很容易被引进的方法。我们需要了解的是，一个集合中数的最大公约数就是这些数的整系数线性组合中最小的那一个，也就是$(a_1,\cdots,a_k)=\min\{s=a_1x_1+\cdots+a_kx_k:x_j\in Z(1\leq j\leq k),s>0\}$。

现在进入到了算术基本定理，我们现在可以用素数的性质来对整数进行分析。由于算术基本定理的存在，我们一定可以通过分析素数的性质来得到相关整数的性质。这里需要介绍一下除数和函数$\sigma(n)=\prod_{j=1}^{r}\frac{p_j^{a_j+1}-1}{p_j-1}$。

对于本章最后的[x]函数的分析，就不再过多的叙述，因为都是很普通的内容。而对于n!的分解式，要能够体会其中蕴含的缩小规模的递归思想。

最后是容斥原理和$\pi(x)$的分析。容斥原理更多的是使用在组合数学当中。而$\pi(x)$的计算需要相应的推导，具体内容可以参见书中。或者可以参见我的另外一个笔记：nmbr.rar。

Jan 22

无限递降法

Art of Science 0 Comments

无限递降法就是一种特殊的反证法，它利用了最小自然数原理。先假设存在一个最小解，然后在这个最小解的基础上推出一个更小的解，再结合最小自然数原理得到矛盾，从而证明命题。

无限递降法经典的一个例子就是证明x4+y4=z2没有正整数解。

我们假定存在一个正整数解，那么其中必定存在一个解x0,y0,z0使得z0最小。我们得到必有(x0,y0)=1，否则会推出一个更小的解。由于$x_0^2,y_0^2,z_0$是方程x2+y2=z2的一个本原解，所以x0和y0必然是一奇一偶，不妨设2|y0，以及(y0,z0)=1。

我们有$(2z_0,2y_0^2)=2(z_0,y_0^2)=2$，由此及2不整除$z_0-y_0^2$即得$(z_0-y_0^2,z_0+y_0^2)=1$。我们又有

$(z_0-y_0^2)(z_0+y_0^2)=x_0^4$

令$z_0-y_0^2=u^4,\quad z_0+y_0^2=v^4$。这里v>u>0,(u,v)=1，u,v都是奇数。进而有

$y_0^2=(v^2-u^2)\frac{v^2+u^2}{2}$

我们又得到(v2-u2,(v2+u2)/2)=1，因为(v2-u2,v2+u2)|(2v2,2u2)=2(v2,u2)=2，又u,v都是奇数，所以2不整除(v2+u2)/2，所以(v2-u2,(v2+u2)/2)=1。

我们再令v2-u2=a2,(v2+u2)/2=b2，这里a>0,b>0,(a,b)=1,2|a,2不整除b。由u,v满足的条件及a,b得0<b<v<z0，及u,a,v是方程x2+y2=z2的本原解且2|a。因此得到u=r2-s2, a=2rs, v=r2+s2。所以r4+s4=b2，而b<z0，与z0的最小性矛盾，命题得证。

无限递降法对于构造的要求很高，确实不是一个很好用的方法。

Jan 19

SRM 410 Div1 - WifiPlanet

Art of Science 1 Comments

题目在这里可以找到。

题目的大概意思是说，在整数格点的平面上有一个简单多边形（顶点坐标均为有理数），问其内部有多少格点。题目保证不会有格点出现在边界上。

三角剖分是不现实的，我们只能选择简单一些的梯形剖分。进而，我们需要计算一条直线下方的格点数目。这里的转化都比较简单，直接略过。接着，我们就把问题转化为了求一个这样的式子：

$\displaystyle\sum_{i=0}^{n-1}\left\lfloor\frac{a+di}{m}\right\rfloor$

这是一个相当有趣的求值。显然，O(n)的算法并不能让我们满意。对于这个经典的问题，我们有$O(\sqrt{n})$和$O(\log n)$两种算法。$O(\sqrt{n})$由于细节问题很多，我介绍的是$O(\log n)$的算法。对$O(\sqrt{n})$算法有兴趣的同学可以查看相关的论文。

考察这个式子，首先，a和d都应该满足大于等于0，小于m的条件。否则我们可以通过变形得到新的a'和d'。我们如果要在$O(\log n)$时间内计算出它的值，一定要设法缩小它的规模。我们将这个式子呈现在平面坐标系中，发现这其实就是求下面的一个图中

所有蓝色点的数目。所有的水平直线表示用来截取的y=km的常函数，红色的点则是(i,a+di)。问题到现在就是求每个点向下引射线，一共和这些直线能够有多少交点。显然，这些直线一共有$l=\left\lfloor\frac{a+dn}{m}\right\rfloor$条。那么，我们对每条直线进行观察，发现如果我们只是求一条直线上有多少交点，是可以在O(1)的时间之内计算的。对于一条直线y=km，我们可以求出所有的交点数是$\left\lfloor\frac{a+dn-km}{d}\right\rfloor$。

至此，问题的规模已经被缩小了，我们得到新的式子：

$\displaystyle\sum_{i=0}^{n-1}\left\lfloor\frac{a+di}{m}\right\rfloor=\sum_{k=0}^{l-1}\left\lfloor\frac{a+dn-km}{d}\right\rfloor$

这里，我们需要对等式的右边进行一些细节处理，因为a+dn和m可能大于d。这样，我们成功的把问题规模缩小了，而这是一个类似取模的缩小方式，我们自然得到每次问题的规模至少被缩小到原来的一半，那么算法的复杂度就是$O(\log n)$级别的。

Jan 17

POJ1091 - 跳蚤

Art of Science 0 Comments

完整的题目描述在这里。

题目给出了n和m，要求出满足最大公约数(x1,x2,...,xn,m)=1且xi不超过m的这样的x1,...,xn的组数。xi都是正整数。

如果n=1，那就是求欧拉函数$\varphi(m)$。我们可以联想其形式：$\varphi(m)=m\prod_{p|m}(1-\frac{1}{p})$。那么当n>1时我们也来类比一下相对应的公式。

令$\varphi(m,n)$表示题目中所要求的答案。我们发现，当m为素数时，$\varphi(m,n)=m^n-1$。这是显然的，因为除了(m,m,...,m,m)这一组数字以外，其余的都是可行的解。那么m不为素数时，我们把m的各个素因数分开考虑。如果某个素因数被n个数所共有，那么一共就少了$m^n\frac{1}{p^n}$种方案，考察m所有的素因数，我们得到$\varphi(m,n)=m^n\prod_{p|m}(1-\frac{1}{p^n})$。

至此，问题解决。