质数、循环节、原根

TODO 

  数学学习网站要找

http://oeis.org/?language=chineseS   整数数列线上大全

 

TODO

《信息安全数学基础》

离散数学

初等数论    浦东图书馆借

 

倍数和约数

       6能被2整除，也能被3整除。则6是2的倍数，也是3的倍数；2是6的约数，3游是6的倍数。倍数和约数是成对出现的，不能单独讲。

       6的所有约数中，3最大，则3是6的最大约数。

       2的倍数可以有很多，4,6,8,10...

 

最大公约数(GCF,HCF greatest/highest common factor)或GCD， greatest common divisor

      定义：也叫最大公因数、最大公因子。指几个整数的约数中最大的那个约数。

      表示：a和b的最大公约数(a,b)；a,b,c,d的最大公约数(a,b,c,d)。

           如12和20的最大公约数：12的约数有2,3,4,6，12 ；20的约数有2,4,5,10，20。取2者最大的那个共有约数为：4

     

最小公倍数(LCM least common multiple)

       是几个数的倍数，并且最小的那个。

       表示：a,b,c的最小公倍数[a,b,c].

              如12和20的LCM=60

       计算：

• 质因数分解法  共有的质因数相乘再乘以各自有的质因数。如[12,20]=[2*2*3,2*2*5]=2*2*3*5=60
• 短除法（计算机中常用）
• 辗转相除法

HCF和LCM的应用实例见：

http://www.baike.com/wiki/%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B0&prd=so_1_doc

如把一块砖长20厘米，宽12厘米，厚6厘米。要堆成正方体至少需要这样的砖头多少块？  T 

 

 HCF和LCM的计算：

          质因数/质约数：一个数的因数/约数中为质数的数。

任何一个整数都能用质因数乘积表示。所以质数是所有整数的爸爸。

1。质因数分解法  例子如上

      HCF 共有的质因数相乘如[12,20]=[2*2*3,2*2*5]=2*2=4

      LCM  共有的质因数相乘再乘以各自有的质因数。如[12,20]=[2*2*3,2*2*5]=2*2*3*5=60

2。短除法

      HCF先用这几个数的公约数连续去除，一直除到所有的商互质为止，然

后把所有的除数连乘起来，所得的积就是这几个数的最大公约数。

 LCM所有的除数和商连乘起来，所得的积就是这几个数的最小公倍数

如下图：

 

3。辗转相除法/欧几里得算法

 例如，求（319，377）：

∵ 319÷377=0（余319）

∴（319，377）=（377，319）；

∵ 377÷319=1（余58）

∴（377，319）=（319，58）；

∵ 319÷58=5（余29），

∴ （319，58）=（58，29）；

∵ 58÷29=2（余0），

∴ （58，29）= 29；

∴ （319，377）=29.

可以写成右边的格式。

用辗转相除法求几个数的最大公约数，可以先求出其中任意两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为止。最后所得的那个最大公约数，就是所有这些数的最大公约数。

 

有理数和无理数

  有理数：整数和分数。其中分数即为2个整数的比，而2个整数的比的结果一定是有限小数，或无限循环小数。（有限小数和无限循环小数一定可以用分数表示）.如1,2,3,0.8888...,4.232323

  注：无限循环小数的分数表示见有道笔记的推导。

  很显然，对于有限小数0.a=a/10^a的长度。对于无限循环小数0.abbb...=（ab-a)/n个9m个0。a为小数中不循环的部分，b为小数中循环的部分，n表示不循环的数字长度，m为循环的数字长度。

 无理数：无限不循环小数。如√2=1.414213562…………，e 拍=3.1415926...

所以数的有理还是无理指的是是否可以表示成分数，即2个整数的比值。“理”即表示“比”。无理数叫做“无比数”，有理数叫做“有比数”。无理数由毕达哥拉斯的弟子希伯斯发现。

 

奇素数

       既是奇数，又是素数。即除了2之外的素数都是奇素数。

 

互质

     几个数的公因数只有1时，称这几个数互质。如7,10,13互质，8,10不是互质。

可见，互质的HCF=(a,b)=1，互质的LCM=[a,b]=a*b。

互斥没有传递性，如10,13,15.10,13互斥，13,15互斥，10,15不互斥。

 

同余

     若 a 除以 n 和 b 除以 n 的余数相同，则称 a 和 b 对模 n 同余，记作 a≡b (mod n)；

     含义：a和b之间相差n的整数倍。a≡b (mod n)<=>a和b之间相差n的整数倍

               因为：a=np+余数，b=np+余数  => a-b=n(p-q), p和q是整数.

同余其他定理

1.反身性。a≡a (mod n)；

2.互换性。a≡b (mod n)；=>b≡a(mod n)；

3.传递性。a≡b (mod n)；b≡c (mod n)；=>a≡c(mod n)；  过程a-b=nx,b-c=ny,x,y为整数=>a-c=n(x+y).

4.加减性。a≡b (mod n)；c≡d (mod n)；=>a+c≡b+d (mod n),a-c=b-d (mod n)

5.常数乘积性或者说消去律。a≡b (mod n)；<=>ap≡bp (mod n),p为整数。

                 充分性证明，因为a-b=nx,x为整数，(a-b)p=nxp.

                 用1和6也能证明，因为p≡p (mod n)，a≡b (mod n) => ap≡bp (mod n) 

                必要性证明，ap-bp=(a-b)p=nx=>a-b=nx/p,一定找得到x使x/p为整数，所以a和b互余。

6.乘积性。a≡b (mod n)；c≡d (mod n)；=>ac≡bd (mod n).证明，因为a-b=nx,c-d=ny,x,y为整数=>ac-bd=

        (nx+b)(ny+d)-bd=n(nxy+dx+by),ac-bd相差n的整数倍，所以ac和bd对n互余。

 

欧拉函数 Euler's totient function

     小于 n 的正整数中与 n 互质的数的数目，记为 φ(n)。如φ(6)=2。因为小雨6的正整数有：1,2,3,4，5。只有1,5和6互质。

 

TODO欧拉函数的数学表达和计算未完成

 

 

剩余系

      对全体自然数，按照除以 n 的余数可以分成 n 类，每一类构成的集合叫做 剩余类

；在每一个剩余类中取一个数，构成的集合叫做 完全剩余系

；在每一个和 n 互质的剩余类中取一个数，构成的集合叫 简化剩余系.。

易见，一个模 n 的简化剩余系中有 φ(n) 个元素。如n=10,123456789中只有简化剩余系1379和10互质，则n的简化剩余系中有4个元素。而 φ(10)=4。 

 

对于任意质数 φ(n)=n-1。因为小于n的所有数中，所有数都和n互质。

 

费马大定理/费马最后定理

     费马大定理之所以出名不是因为定理本身，而是证明定理过程中衍生出各种科学和理论。

      当n>2时，不存在正整数使x^n+y^n=z^n。

由来，费尔马在读丢番图的名著《算术》的法文译本时，他在书中有关于毕达哥拉斯不定方程 x2＋ y2 ＝z2。联想到x^n+y^n=z^n的情况，并调皮的说“我已经证明，但纸张不够，所以没写下”。后人去实现他的证明而引发的几世纪的证明。

      欧拉已证明n=3和4的情况。TODO

     TODO

      因为任何一个大于2的整数，如果不是4的倍数，就一定是某一奇素数或它的倍数。因此，只要能证明n＝4以及n是任一奇素数时都没有正整数解，费尔马大定理就完全证明了。n＝4的情形欧拉已经证明过了，所以，问题就集中在证明n等于奇素数的情形了。 

https://www.zhihu.com/question/30507123/answer/48482143

1770年，欧老师证明了，的时候猜想成立。

1823年，勒让德证明，的时候猜想成立。

1832年，狄利克雷想证明的时候猜想成立，可惜失败了。不过他证明了是成立的。

1839年，拉梅证明，的时候猜想成立。

然后就有了重大突破。

1850年，库默尔证明，的时候，除了37、59、67以外，猜想都是成立的。

接下来100多年间，都没有神马进展了。

计算机时代来临后，数（程）学（序）家（猿）们开始暴力验证了。

1955年，范迪维尔以电脑计算证明了时猜想成立。

1976年，瓦格斯塔夫以电脑计算证明了时猜想成立。

1985年，罗瑟以电脑计算证明了时猜想成立。

1987年，格朗维尔以电脑计算证明了时猜想成立。

1995年，怀尔斯最终用非暴力方式证明了的时候成立。至此费马猜想最终变成了费马定理。证明的过程，绝非我等凡夫俗子能够理解，其中用到了谷山－志村猜想。

 

欧拉函数/费马-欧拉定理

     若 a 和 m 互质，则 (mod m)。白话就是如果a和m互质，则a的φ(m)次方对于m的余数是1。

证明：设m的简化剩余系为：.(xi和m互质，任意2个x都不相等,包含了一个数除以m所有的余数情况)。长度为m-1.

对任意xi和xj都有， (mod m)，即任意xi之间都不互余。（反证法：如果axi和axj互余，则由上方互余定理5得xi和xj互余，然而前提条件可知：xi,xj是m的简化剩余系，一定不会对m互余，所以假设不成立，axi和axj不关于m互余；也可以利用互余相差量做反证法推导得到此结论）

因为xi是m的所有的余数集合了，并且axi之间两两都不互余=>axi集合也是m的简化剩余系。

即对于xi中的每个元素，有且都有一个axk与之对应，使xi和axk对于m互余。

注：不是xi中的任意元素都与axi对m互余。而是和axk互余，xk不一定就是xi.

利用互余定理6（xi和axk互余，xm和axn互余...=>xi*xm与axk*axn互余），

把2个简化剩余系中的所有元素相乘得：

(mod m)

再次利用互余定理5，因为x1*x2*x3...≡a的φ(m)次方再乘以x1*x2*x3...,所以  a的φ(m)次方和1对m互余。

所以如果a和m互质，则a的φ(m)次方对于m的余数是1。

 

x1*x2*x3≡xp*xq*xr*a^3 (mod m)  ，去除任意数量的集合的元素可以找到这个等式成立。

 

 

 

欧拉小定理/费马小定理  若 p 为质数，且 a 和 p 互质，则 (mod p)

证明利用欧拉函数/费马-欧拉定理，当p为质数时φ(p)=p-1.所以...

 

 

------------------------------以下为TODO------------------------------

问：x0|x 表示什么？

问：ordn(a)表示什么？

 

 

orda(n)表示使a^k≡1(mod n)成立的最小k 的值。

 

设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。（其中φ(m)表示m的欧拉函数）^[1] 

假设一个数g对于P来说是原根，那么g^i mod P的结果两两不同。（TODO 为什么？？用反证法证明之...）,且有 1<g<P, 0<i<P,那么g可以称为是P的一个原根,归根到底就是g^(P-1) = 1 (mod P)当且当指数为P-1的时候成立.(这里P是素数). 

简单来说，g^i mod p ≠ g^j mod p （p为素数） 

其中i≠j且i, j介於1至(p-1)之间 

则g为p的原根。 

求原根目前的做法只能是从2开始枚举，然后暴力判断g^(P-1) = 1 (mod P)是否当且当指数为P-1的时候成立 

而由于原根一般都不大，所以可以暴力得到.

性质/原根 编辑

1）可以证明，如果正整数(a,m) = 1和正整数 d 满足a^d≡1(mod 7)，则 d 整除 φ(m)。因此Ordm(a)整除φ(m)。在例子中，当a= 3时，我们仅需要验证 3 的 1 、2、3 和 6 次方模 7 的余数即可。 

2）记δ = Ordm(a)，则a^1，……a^(δ-1)模 m 两两不同余。因此当a是模m的原根时，a^0,a^1，……a^(δ-1)构成模 m 的简化剩余系。 

3）模m有原根的充要条件是m= 1,2,4,p,2p,p^n，其中p是奇质数，n是任意正整数。 

4）对正整数(a,m) = 1，如果 a 是模 m 的原根，那么 a 是整数模n乘法群（即加法群 Z/mZ的可逆元，也就是所有与 m 互素的正整数构成的等价类构成的乘法群）Zn的一个生成元。由于Zn有 φ(m)个元素，而它的生成元的个数就是它的可逆元个数，即 φ(φ(m))个，因此当模m有原根时，它有φ(φ(m))个原根。

 

什么是同余的阶  T

a和模m互质，使a^d≡1(modm)成立的最小正整数d称为a对模m的阶(指数),例如

1^1≡1(modn),1对模n的阶为1
2^2≡1(mod3),2对模3的阶为2；
5^6≡1(mod7),5对模7的阶为6；
2^3≡1(mod7),2对模7的阶为3.
等等。

 

原根

    设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。

根据上面模的阶的定义，即如果对于m和a，使得a^φ(m)≡1(mod m)  的 a的值就是m的一个原根。

这个a可以有多个，最小的那个a(最小的那个原根)记作“Ord”

 

 

TODO

数论四大定理

       威尔逊定理、TODO

  http://www.baike.com/wiki/%E5%A8%81%E5%B0%94%E9%80%8A%E5%AE%9A%E7%90%86&prd=so_1_doc

       欧拉定理、T

       孙子定理、TODO

http://www.baike.com/wiki/%E5%AD%99%E5%AD%90%E5%AE%9A%E7%90%86&prd=so_1_doc?bcsi_scan_50cf319c8a3b1a7d=9XzsW+qMhPMKcKqnLFLqnF/parMvAAAA4o2OFg==

      费马小定理 T