欧拉函数、欧拉定理、费马小定理

xiaoxiao2021-03-01  19

生病了,耽搁了两天。明天开始继续和队友们一起奋战。。。

总结一下,自己以前学过的数论方面的知识。

今天小小的搜索一下,计算机数论真的是很庞大的一个领域。推荐一本书《计算数论》。准备买了、

这里先浅议下欧拉定理和欧拉函数。

很久以前以为他俩一个意思()

欧拉函数:

定义:用于计算 p(n),比n小的所有与n互质的数。

计算公式:p(n)=n*(1-1/p1)*(1-1/p2)....*(1-1/pk)【p1,p2,pk都是n的素因子】

另:若n=p1^q1*p2^q2*.....*pk^qk

则,p(n)=(p1-1)*p1^(q1-1)*(p1-1)*p2^(q2-1)......*(pk-1)*pk^(qk-1)

性质:若m,n互质,φ(mn)=φ(m)φ(n)。当n为奇数时,φ(2n)=φ(n)

编程实现:

//求与n互质的个数 #include<iostream> #include<math.h> #include<stdio.h> using namespace std; int main() { int n,m; while(cin>>n) { int i;m=n; for(i=2;i<=(int)sqrt(double(n)+0.5);i++) { if(n%i==0) m-=m/i; while(n%i==0) n/=i;//找公因子 if(n==1) break; } if(n>1) m-=m/n;//去重 cout<<m<<endl; } }

欧拉定理:

a,m互质,a^φ(m)≡1(mod m)

例:2,3互质,那么,2^2%3=1

推论:对于互质的数a、n,满足a^(φ(n)+1) ≡ a (mod n)

费马小定理:

假如p是质数,且(a,p)=1,那么 a^(p-1) ≡1(mod p) 假如p是质数,且a,p互质,那么 a的(p-1)次方除以p的余数恒等于1

费马大定理:

当整数n > 2时,关于x, y, z的不定方程 x^n + y^n = z^n. 无正整数解

威尔逊定理:

当仅当p是素数:( p -1 )! ≡ -1 ( mod p )

相关资源:垃圾分类数据集及代码
转载请注明原文地址: https://www.6miu.com/read-3649966.html

最新回复(0)