首页 > 代码库 > ACM数论中相关定理（不断更新）
ACM数论中相关定理（不断更新）
费马小定理是数论中的一个重要定理，其内容为： 假如p是质数，且(a,p)=1，那么 a^(p-1) ≡1（mod p）。即：假如a是整数，p是质数，且a,p互质，那么a的(p-1)次方除以p的余数恒等于1。
费马大定理，又被称为“费马最后的定理”，由法国数学家费马提出。它断言当整数n >2时，关于x, y, z的方程 x^n + y^n = z^n 没有正整数解。被提出后，经历多人猜想辩证，历经三百多年的历史，最终在1995年被英国数学家安德鲁·怀尔斯证明。
中国剩余定理的结论：
令任意固定整数为M，当M/A余a，M/B余b，M/C余c，M/D余d，…，M/Z余z时，这里的A，B，C，D，…，Z为除数，除数为任意自然数（[span]如果为0，没有任何意义，如果为1，在孙子定理中没有计算和探讨的价值，所以，不包括0和1）时；余数a，b，c，d，……，z为自然整数时。
1、当命题正确时，在这些除数的最小公倍数内有解，有唯一的解，每一个最小公倍数内都有唯一的解；当命题错误时，在整个自然数范围内都无解。
2、当M在两个或两个以上的除数的最小公倍数内时，这两个或两个以上的除数和余数可以定位M在最小公倍数内的具体位置，也就是M的大小。
3、正确的命题，指没有矛盾的命题：分别除以A，B，C，D，…，Z不同的余数组合个数=A，B，C，D，…，Z的最小公倍数=不同的余数组合的循环周期．
欧拉函数在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler‘s totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。 从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。
φ函数的值 通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数(小于等于1)就是1本身）。 (注意：每种质因数只一个。比如12=2*2*3那么φ（12）=12*（1-1/2）*(1-1/3)=4
若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。
设n为正整数，以 φ(n)表示不超过n且与n互
素的正整数的个数，称为n的欧拉函数值，这里函数
φ：N→N，n→φ(n)称为欧拉函数。
欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。
特殊性质：当n为奇数时，φ(2n)=φ(n), 证明与上述类似。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。