费马小定理
费马小定理是数论中的一个定理。其内容为假如a是一个整数，p是一个质数的话，那么<math>a^p \equiv a \pmod</math>
假如a不是p的倍数的话，那么这个定理也可以写成
<math>a^ \equiv 1 \pmod</math>
这个书写方式更加常用些。（符号的应用请参见模运算。）
历史
皮埃尔•德•费马于1636年发现了这个定理，在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个质数的要求。这个要求实际上不存在。
与费马无关的有一个中国猜想。这个猜想是中国数学家提出来的。其内容为如果，而且只有当2p = 2(mod p)成立时p才是一个质数。
假如p是一个质数的话，则2p = 2(mod p)成立（这是费马小定理的一个特殊情况）是对的。但反过来，假如2p = 2(mod p)成立那么p是一个质数是不成立的（比如341符合上述条件但不是一个质数）。因此整个来说这个猜想是错误的。
一般认为中国数学家在费马前2000年的时候就已经认识中国猜测了。但也有人认为实际上中国猜测是1872年提出的，认为它早就为人所知是出于一个误解。
证明
假如a和b 的 差不能被n整除的话 ， 那么假如x>0和x和n的最 大 公约数为1 的 话 ， 则x•a与x•b 的 差也不能被n整除。取A为所有小于p 的 整数的集（A中的数都不能被p整除），B为A中所有元素乘 以a所获得的 数的 集。任何两 个A中 的元素的差都不能被p整除。由此任何两个B中的元素的差也无法被p整除。由此
<math>1 \cdot 2 \cdot 3 \cdot \dots \cdot (p-1) \equiv (1 \cdot a)\cdot(2 \cdot a)\cdot\dots\cdot ((p-1) \cdot a) \pmod,</math>
既
<math>W \equiv W\cdot a^ \pmod,</math>
在这里W=1•2•3•...•(p-1)。将整个公式除以W既得到：
<math>a^ \equiv 1 \pmod</math>
广义
费马小定理是欧拉定理的一个特殊情况：假如n和a的最大公约数是1的话，那么
<math>a^{\varphi (n)} \equiv 1 \pmod</math>
在这里φ(n)是欧拉商数。欧拉商数的值是所有小于n的自然数中与n没有公约数的数的量。假如n是一个质数，则φ(n) = n-1，即费马小定理。
在费马小定理的基础上费马提出了一种测试质数的算法。
实际应用
如上所述，中国猜测只有一半是正确的，符合中国猜测但不是质数的数被称为伪质数。
假如所有符合1 < b < p的b p都满足下列条件的话：
<math>b^ \equiv b \mod p</math>
则p必定是一个质数。
实际上没有必要测试所有的小于p的自然数，只要测试所有的小于p的质数就可以了。
这个算法的缺点是它非常慢，运算率高。 费尔马小定理
费马小定理是数论中的一个定理。其内容为假如a是一个整数，p是一个质数的话，且a、p互素
则
a^p≡1(mod p) 帮顶
页:
[1]