数学里面一些比较经典的证明

数学有啥用

有的很古老，简单，但是我觉得很精巧很漂亮，富有启发性
1，√2是个无理数


据说公元前5世纪古希腊的毕达哥拉斯（Pythagoras）发现一个正方形的对角线与边是不可公度量（incommensurable）的，也就是说它们的比不是一个有理数。所谓有理数，就是形如p/q的数，其中p,q是整数，q≠0。

证明用反证法（proof by contradiction）：假设√2是有理数，那么√2=p/q，p,q是互素（即没有公因数大于1）的整数，q≠0。两边平方，得到p^2=2q^2，可知p^2是个偶数，进而得到p也是个偶数，因为p是奇数的话，p^2就是奇数了。设p=2m，带入p^2=2q^2，得到4m^2=2q^2，化简，得到q^2=2m^2，可知q^2是个偶数，进而得到q也是个偶数。p和q都是偶数，与p,q互素的假设矛盾。假设不成立，所以√2是个无理数。

数学有啥用

2 素数（primes）有无穷多个

先简单说一下什么是素数。将自然数(即1，2，3，4，...)按照因数的多少来分类，可以分为三类。第一类是只有一个因数，这一类只有一个数，也就是1；
第二类是只有两个因数，这一类就是素数，它们唯一的两个因数就是1和它们本身；剩下的为第三类。

前面几个素数是2，3，5，7，11，13，17，等等。

据说下面这个证明是出自欧几里得。记得我第一次看到这个证明的时候，我被反证法的强大深深折服了。竟然能够攻击无穷！

用反证法。假设素数有限，不妨将它们按从小到大顺序编号，q1，q2，q3，,,, ，qn。考虑这个数A=q1*q2*q3*...*qn+1。明显A>qn，所以A不是素数，那么A就有除了1和它本身的因数，可以设为p。p≠q1，否则p既整除A又整除q1*q2*q3*...*qn，则p整除两数之差，也就是1，这是不成立的。同样的，p≠q2,q3,...,qn。这就产生了一个新的素数，与假设矛盾，所以素数无穷。

数学有啥用

3  e是个无理数

这里的e是自然对数的底，也叫欧拉数（Euler Number）,定义为一个无穷级数：e=1+1+1/2!+1/3!+1/4!+...

这个证明据说是最初来自傅里叶（Charles Fourier）

e-irrat.dvi (upenn.edu)

这个证明的关键是eq!既是整数又不是整数，从而导出矛盾。过程可以稍微简化一下，在将eq!分成两部分的时候，后半部分可以直接与几何级数1/(q+1)+1/(q+1)^2+1/(q+1)^3+...比较

数学有啥用

4，pi是一个无理数

圆周率pi历史悠久，源远流长。pi比3大一点，可以用有理数22/7等等来近似。据说祖冲之用113/355来近似。但是证明pi是一个无理数是比较晚的事情了。第一个证明pi是无理数的人是17世纪的兰伯特（Johann Heinrich Lambert）,用的是连分数的方法，这里分享一个加拿大籍美国数学家Ivan Niven的证明。个人觉得这个证明初看不明所以，但是越想越觉得巧妙。

A simple proof that $\pi$ is irrational (projecteuclid.org)

佳创兴2015

后三个，我都看不懂。

数学有啥用

5, 最大公约数与欧几里得算法

  顾名思义，最大公约数（the greatest common divisor, GCD），就是两个（或者多个）整数的公约数里最大的那一个。找GCD有一个高效的算法，记载在几何原本里面，称为欧几里得算法（Euclidean Algorithm），国内称为辗转相除法。算法是这样的，例如，要找a和b的GCD（假设a>b）,先进行带余除法，记为a=q1*b+r1, 0≤r1<b; 再对b和r1进行带余除法，记为b=q2*r1+r2, 0≤r2<r1; 再对r1和r2进行带余除法，记为r1=q3*r2+r3; 以此类推，一直到出现余数为0，那么倒数第二个余数就是a和b的GCD。

a=q1*b+r1

b=q2*r1+r2

r1=q3*r2+r3

...

                     r(n-3)=q(n-1)*r(n-2)+r(n-1)

                                 r(n-2)=q(n)*r(n-1)+r(n)     <---GCD

              r(n-1)=q(n+1)*r(n)+0

证明大致是这样的

  A）为何会出现余数为0？因为b>r1>r2>r3>...是一个严格递减的非负序列
  B) 为何r(n)是a和b的公约数？可以从下往上看：根据最后一行，可知r(n)整除r(n-1),从而整除r(n-2),从而整除r(n-3),...,从而整除b,从而整除a
  C) 为何r(n)是a和b的最大公约数？设d是a和b的任意公约数，可以从上往下看：d整除a，d整除b, 根据第一行，可知d整除r1，从而d整除r2,...,从而d整除r(n)。

数学有啥用

6 巴塞尔问题

数学史上著名的巴塞尔问题（Basel problem）,是求正整数平方的倒数的和，∑(1/n^2)。欧拉最先给出了一个令人意想不到的答案，（pi^2）/6。

欧拉的证明是这样的,首先，

sinx=x-x^3/3!+x^5/5!-x^7/7!+...

两边除以x

sinx/x=1-x^2/3!+x^4/5!-x^6/7!+...       （1）

注意到函数sinx/x的零点是x=pi,-pi,2pi,-2pi,3pi,-3pi,4pi,-4pi,...，根据魏尔斯特拉斯分解定理（Weierstrass factorization theorem），可以将sinx/x写成无穷乘积

sinx/x=(1-x/pi)(1+x/pi)(1-x/2pi)(1+x/2pi)(1-x/3pi)(1+x/3pi)...

        =(1-x^2/pi^2)(1-x^2/4pi^2)(1-x^2/9pi^2)...       （2）

将这个无穷乘积乘出来，可知x^2项的系数是

-1/pi^2-1/4pi^2-1/9pi^2-...=-1/pi^2(1+1/4+1/9+1/16+...)

与（1）式比较，x^2项的系数必须相等，可知

-1/pi^2(1+1/4+1/9+1/16+...)=-1/3!=-1/6

所以

1+1/4+1/9+1/16=pi^2/6

​

​

数学有啥用

7 中国剩余定理

Chinese Remainder Theorem

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？....《孙子算经》

即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。

定理：令n1,n2,...,nk为两两互素的自然数，b1,b2,...,bk∈Z。记N=n1*n2*...*nk。则存在唯一的x(mod N) 使得x≡bi(mod ni)，其中1≤i≤k。

证明：记mi=N/ni。mi有两个性质，首先，mi与ni互素，所以mi存在一个逆(mod ni)，不妨记为yi；然后，当j≠i的时候，注意到mi是nj的倍数。       考虑x=b1*m1*y1+b2*m2*y2+...+bk*mk*yk
       对于任意i,1≤i≤k，有
                                  x≡b1*m1*y1+b2*m2*y2+...+bk*mk*yk (mod ni)
                                    ≡bi*mi*yi (mod ni)
                                    ≡bi (mod ni)
最后，要证明唯一性。假设x和y同时满足同余方程组，则ni整除x-y，而ni两两互素，则N整除x-y，即x≡y (mod N)。


上面这个同余方程组是这样的

x≡2 (mod 3)

x≡3 (mod 5)

x≡2 (mod 7)

用中国剩余定理可以这么解

首先，N=3*5*7=105，m1=N/3=35，m2=N/5=21，m3=N/7=15。

再计算m1≡35≡2(mod 3), y1=2;

         m2≡21≡1(mod 5), y2=1;

         m3≡15≡1(mod 7), y3=1.

最后，x≡2*35*2+3*21*1+2*15*1(mod 105)

           ≡140+63+30(mod 105)

           ≡233(mod 105)

           ≡2*105+23(mod 105)

           ≡23(mod 105)

所以，满足上面这个同余方程组的最小的自然数是23。