欧拉定理
这个是成立的
其中m为n的欧拉函数的倍数都可以,其中欧拉函数的定义如下: 欧拉函数的值为小于n的这n-1个数中与n互质的整数的个数
举个例子
当n=9时 小于9并与9互质的数有 1 2 4 5 7 8 故可以取m=6 2^6=64%9=1
证明可以网上找 不会的也可以问我
希望能够帮到你追问怎么扯到欧拉函数了。不懂。
回答晕 我证明给你看吧
假设所有小于n并且与n互质的数构成的集合为S={1,2....n-1} 设S集合共有m个元素 下面证明2^m%n=1
考察S1={2*k|k属于S}
显然对于任何a属于S1,有gcd(a,n)=1
且对于任何两个属于S1的不同的元素a,b 有n不整除a-b
否则n|(a-b) 假如存在p,q属于S满足a=2p b=2q(这个由S1的定义可以看出) =>n|2(p-q) 又n为奇数 =>n|(p-q) 与S集合定义矛盾
故在模n的情况下S和S1是相等的
=>n|2*1*2*2...*2*(n-1)-1*2...*(n-1)=>n|(2^m-1)*(1*2*...(n-1))
(注其中1*2*...(n-1)
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示S中的所有元素相乘 2*1*2*2...*2*(n-1)表示S1中所有元素相乘)
=>n|(2^m-1)=>2^m%n=1
故m是存在的
或者看下面百度上的
定理内容
在数论中,欧拉定理(也称费马-欧拉定理)是一个关于同余的性质。欧拉定理表明,若n,a为正整数,且n,a互质,(a,n) = 1,则a^φ(n) ? 1 (mod n) 证明
首先证明下面这个命题:
对于集合Zn={x1,x2,...,xφ(n)},其中xi(i=1,2,…φ(n))是不大于n且与n互素的数,即n的一个化简剩余系,或称简系,或称缩系),考虑集合S = {a*x1(mod n),a*x2(mod
n),...,a*xφ(n)(mod n)}
则S = Zn
1) 由于a,n互质,xi也与n互质,则a*xi也一定于n互质,因此
任意xi,a*xi(mod n) 必然是Zn的一个元素
2) 对于Zn中两个元素xi和xj,如果xi ? xj
则a*xi(mod n) ? a*xj(mod n),这个由a、n互质和消去律可以得出。
所以,很明显,S=Zn
既然这样,那么
(a*x1 × a*x2×...×a*xφ(n))(mod n)
= (a*x1(mod n) × a*x2(mod n) × ... × a*xφ(n)(mod n))(mod n)
= (x1 × x2 × ... × xφ(n))(mod n)
考虑上面等式左边和右边
左边等于([a^φ(n)] *(x1 × x2 × ... × xφ(n))) (mod n)
右边等于x1 × x2 × ... × xφ(n))(mod n)
而x1 × x2 × ... × xφ(n)(mod n)和n互质
根据消去律,可以从等式两边约去,就得到:
a^φ(n) ? 1 (mod n)