谁知道费尔马小定理?能否求证?

谁知道费尔马小定理?能否求证?
谁知道费尔马小定理?
能否求证?

谁知道费尔马小定理?能否求证?
费马小定理,若p是素数且a是整数则a^p≡a(mod p),特别的若a不能被p整除,则a^(p-1)≡1(mod p).
这可以用数学归纳法证明.
a=1显然成立.
假设对a成立,就是a^p≡a(mod p),则对a+1,(a+1)^p,由二项式定理,除了第一项a^p和1以外,其他各项系数都能被p整除,所以(a+1)^p≡a^p+1(mod p),而a^p≡a(mod p),所以(a+1)^p≡a+1(mod p).所以费马小定理得证.

费马小定理
费马小定理是数论中的一个定理,其内容为:假如a是一个整数，p是一个质数的话，那么 $a^p\; \backslash equiv\; a\; \backslash p\; mod$
假如a不是p的倍数的话，那么这个定理也可以写成 $a^\; \backslash equiv\; 1\; \backslash p\; mod$ 。（符号的应用请参见模运算）
关于费马定理的...

全部展开

费马小定理
费马小定理是数论中的一个定理,其内容为:假如a是一个整数，p是一个质数的话，那么 $a^p\; \backslash equiv\; a\; \backslash p\; mod$
假如a不是p的倍数的话，那么这个定理也可以写成 $a^\; \backslash equiv\; 1\; \backslash p\; mod$ 。（符号的应用请参见模运算）
关于费马定理的历史
皮埃尔•德•费马于1636年发现了这个定理，在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个质数的要求，但是这个要求实际上是不存在的。与费马无关的有一个中国猜想，这个猜想是中国数学家提出来的，其内容为：当且仅当当2p=2(mod p)，p才是一个质数。
假如p是一个质数的话，则2p = 2(mod p)成立（这是费马小定理的一个特殊情况）是对的。但反过来，假如2p = 2(mod p)成立那么p是一个质数是不成立的（比如341符合上述条件但不是一个质数）。因此整个来说这个猜想是错误的。一般认为中国数学家在费马前2000年的时候就已经认识中国猜测了，但也有人认为实际上中国猜测是1872年提出的，认为它早就为人所知是出于一个误解。
关于费马定理证明
假如a 差不能被p整除的话 ， 那么假如x>0和x和p的最 大 公约数为1的话(a,p互素) ， 则x•a与x•a 的差也不能被n整除(也就是说x.a,x.a,.....(p-1).a 不是模n同余的)。取A为所有小于p 的整数的集（A中的数都不能被p整除），
B为A中所有元素除以a所获得的数集。任何两个A 的元素的差都不能被p整除而又有相同的余数，由此任何两个B中的元素的差也无法被p整除。由此 可得
而试图在p-1个元素里取p-1个不同的元素，则必定是相同的
则A集合中元素的乘积，和B集合中元素的乘积一定是模p同余的
即 1.a ×2.a x×3.a......(p-1).a=1×2×3×4......×（p-1)(mod p)
(p-1)!=ap-1(p-1)!(mod p)
在这里W=1•2•3•...•(p-1)。(威尔逊定理）
由于gcd((p-1),p)=1,两边同除以(p-1)!,即可得到费马小定理

费马定理的推广
费马小定理是欧拉定理的一个特殊情况：假如n和a的最大公约数是1的话，那么
$a^\{\backslash varphi\; (n)\}\; \backslash equiv\; 1\; \backslash pmod$
在这里φ(n)是“欧拉商数”。“欧拉商数”的值是所有小于n的自然数中与n没有公约数的数的量。假如n是一个质数，则φ(n) = n-1，即费马小定理。 在费马小定理的基础上费马提出了一
种测试质数的算法。
费马定理的实际应用
如上所述，中国猜测只有一半是正确的，符合中国猜测但不是质数的数被称为“伪质数”。
假如所有符合1 < b < p的b p都满足下列条件的话：
$b^\; \backslash equiv\; b\; \backslash mod\; p$
则p必定是一个质数。
实际上没有必要测试所有的小于p的自然数，只要测试所有的小于p的质数就可以了。
这个算法的缺点是它非常慢，运算率高。

收起