本页使用了标题或全文手工转换

费马小定理

维基百科,自由的百科全书
跳到导航 跳到搜索

费马小定理数论中的一个定理:假如是一个整数是一个质数,那么是p的倍数,可以表示为

如果a不是p的倍数,这个定理也可以写成

[1]

这个书写方式更加常用。(符号的应用请参见同馀。)

历史[编辑]

皮埃尔·德·费马

皮埃尔·德·费马于1636年发现了这个定理。在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个素数(质数)的要求。

1736年,欧拉出版了一本名为“一些与素数(质数)有关的定理的证明”(拉丁文:Theorematum Quorundam ad Numeros PRIMOS Spectantium Demonstratio)”[2]的论文集,其中第一次给出了证明。但从莱布尼茨未发表的手稿中发现他在1683年以前已经得到几乎是相同的证明。

有些数学家独立提出相关的假说(有时也被错误地称为中国的假说),当成立时,p是质数。这是费马小定理的一个特殊情况。然而,这一假说的前设是错的:例如,,而341=11×31是一个伪素数(质数)。所有的伪素数(质数)都是此假说的反例。

卡迈克尔数[编辑]

所述,中国猜测仅有一半是正确的。符合中国猜测但不是素数(质数)的数被称为伪素数(质数)。

更极端的反例是卡迈克尔数: 假设与561互质,则被561除都余1。这样的数被称为卡迈克尔数,561是最小的卡迈克尔数。Korselt在1899年就给出了卡迈克尔数的等价定义,但直到1910年才由卡迈克尔(Robert Daniel Carmichael)发现第一个卡迈克尔数:561。1994年William Alford、Andrew Granville及Carl Pomerance证明了卡迈克尔数有无穷多个。

证明[编辑]

方法一[编辑]

若n不能整除,则n也不能整除。取整数集为所有小于构成的完全剩余系,即中不存在两个数同余),中所有的元素乘以a组成的集合。因为中的任何两个元素之差都不能被p整除,所以B中的任何两个元素之差也不能被p整除。

换句话说,,考虑个数,将它们分别除以p,馀数分别为,则集合{r1,r2,r3,...,rp-1}为集合{1,2,3,...,(p-1)}的重新排列,即1,2,3,....,(p-1)在馀数中恰好各出现一次;这是因为对于任两个相异k*a而言(k=1,2,3....(p-1)),其差不是p的倍数(所以不会有相同馀数),且任一个k*a亦不为p的倍数(所以馀数不为0)。因此

在这里W=1·2·3·...·(p-1),且(W, p) = 1,因此将整个公式除以W即得到:

[3]

方法二[编辑]

考虑二项式系数,n不为p或0,由于分子有质数p,但分母不含p,故分子的p能保留,不被约分而除去,即恒为p的倍数。

再考虑(b+1)p的二项式展开,模p,则

因此

令b=a-1,即得[3]

方法三[编辑]

抽象代数教科书中,费马小定理常作为教授拉格朗日定理时的一个简单例子[4]。显然只需考虑 情形。此时模 所有非零的余数,在同余意义下对乘法构成一个群,这个群的阶是 。考虑群中的任何一个元素 ,根据拉格朗日定理, 的阶必整除群的阶。证毕。

应用[编辑]

  • 计算除以13的馀数

故馀数为3。

  • 证明对于任意整数a而言,恒为2730的倍数。13减1为12,12的正因数有1, 2, 3, 4, 6, 12,分别加1,为2, 3, 4, 5, 7, 13,其中2, 3, 5, 7, 13为质数,根据定理,为2的倍数、为3的倍数、为5的倍数、为7的倍数、为13的倍数,即2*3*5*7*13=2730的倍数。

推广[编辑]

欧拉定理[编辑]

费马小定理是欧拉定理的一个特殊情况:如果 ,那么

这里 欧拉函数。欧拉函数的值是所有小于或等于 的正整数中与 互质的数的个数。假如 是一个素数(质数),则 ,即费马小定理。

证明 上面证明费马小定理的群论方法,可以同理地证明欧拉定理。考虑所有与 互素的数,这些数模 的余数所构成的集合,记为 ,并将群乘法定义为相乘后模 的同余。显然 是一个群,因为它对群乘法封闭(若 ),含幺元(即“1”),且任何一个元素 的逆元素也在集合中(因为若 则由群乘法封闭性任何 的幂次都在 中,所以 这个有限集的子集)。根据定义, 的阶是 ,于是根据拉格朗日定理, 中任何一个元素的阶必整除 。证毕。

卡迈克尔函数[编辑]

卡迈克尔函数比欧拉函数更小。费马小定理也是它的特殊情况。

多项式除法[编辑]

除式:

余式: 就这? n=0时为除式,用数学归纳法证明余式。[5]

Python程式码[编辑]

 1 >>> n =221
 2 >>>a = 38
 3 >>>pow(a ,n -1,n)
 4 1
 5 
 6 """221 may be a prime number."""
 7 
 8 import random
 9 def isprime(n,k=128):
10     if n<2:
11         return False
12     for _ in range(k):
13         a = random.randrange(1,n)
14         if pow(a,n-1,n)!=1:
15             return False
16     return True

参见[编辑]

参考[编辑]

  1. ^ Fermat's Little Theorem.WolframMathWorld.(英文)
  2. ^ A proof of certain theorems regarding prime numbers
  3. ^ 3.0 3.1 许介彦. 费马小定理 (PDF). 科学教育月刊 (私立大叶大学电机工程学系). 2006年10月, (第293期): 37–44. (原始内容 (PDF)存档于2015-04-18). 
  4. ^ 聂灵沼; 丁石孙. 代数学引论 第二版. 北京: 高等教育出版社. 2000: 第33页. ISBN 7-04-008893-2. 
  5. ^ 黄嘉威. 多项式除法解高次同余. 数学学习与研究. 2015, (9): 第104页.