费马小定理 (英語:Fermat's little theorem )是数论 中的一个定理。假如
a
{\displaystyle a}
是一个整数 ,
p
{\displaystyle p}
是一个質数 ,那么
a
p
−
a
{\displaystyle a^{p}-a}
是
p
{\displaystyle p}
的倍数,可以表示为
a
p
≡
a
(
mod
p
)
{\displaystyle a^{p}\equiv a{\pmod {p))}
如果
a
{\displaystyle a}
不是
p
{\displaystyle p}
的倍数 ,这个定理也可以写成更加常用的一种形式
a
p
−
1
≡
1
(
mod
p
)
{\displaystyle a^{p-1}\equiv 1{\pmod {p))}
[1] [註 1] 費馬小定理的逆敘述不成立,即假如
a
p
−
a
{\displaystyle a^{p}-a}
是
p
{\displaystyle p}
的倍数,
p
{\displaystyle p}
不一定是一个質数 。例如
2
341
−
2
{\displaystyle 2^{341}-2}
是
341
{\displaystyle 341}
的倍数,但
341
=
11
×
31
{\displaystyle 341=11\times 31}
,不是質数 。滿足費馬小定理的合數被稱為费马伪素数 。
皮埃爾·德·費馬 皮埃爾·德·費馬 于1636年发现了这个定理。在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个素数的要求。
1736年,歐拉 出版了一本名為“一些與素數有關的定理的證明”(拉丁文:Theorematum Quorundam ad Numeros PRIMOS Spectantium Demonstratio)”[2] 的論文集,其中第一次给出了證明。但從萊布尼茨 未發表的手稿中發現他在1683年以前已經得到幾乎是相同的證明。
有些數學家獨立提出相關的假說(有時也被錯誤地稱為中國猜想 ),當
2
p
≡
2
(
mod
p
)
{\displaystyle 2^{p}\equiv 2{\pmod {p))}
成立時,p是質數。這是費馬小定理的一個特殊情況。然而,這一假說的前設是錯的:例如,
2
341
≡
2
(
mod
341
)
{\displaystyle 2^{341}\equiv 2{\pmod {341))}
,而341=11×31是一個偽素數 。所有的偽素數都是此假說的反例。
如上 所述,中國猜想仅有一半是正确的。符合中國猜想但不是素数的数被称为伪素数。
更极端的反例是卡迈克尔数:
假設
a
{\displaystyle a}
與561互质,則
a
560
{\displaystyle a^{560))
被561除都余1。这样的数被称为卡邁克爾數,561是最小的卡邁克爾数。Korselt在1899年就给出了卡邁克爾數的等价定义,但直到1910年才由卡邁克爾 (Robert Daniel Carmichael)发现第一个卡邁克爾数:561。1994年William Alford、Andrew Granville及Carl Pomerance证明了卡邁克爾数有无穷多个。
(i)若
a
{\displaystyle a}
是整数,
p
{\displaystyle p}
是质数,且
gcd
(
a
,
p
)
=
1
{\displaystyle \gcd(a,p)=1}
。若
p
{\displaystyle p}
不能整除
x
−
y
{\displaystyle x-y}
,则
p
{\displaystyle p}
不能整除
a
(
x
−
y
)
{\displaystyle a(x-y)}
。取整數集
A
{\displaystyle A}
为所有小於
p
{\displaystyle p}
的正整数集合 (
A
{\displaystyle A}
构成
p
{\displaystyle p}
的完全剩余系,即
A
{\displaystyle A}
中不存在两个数同余
p
{\displaystyle p}
),
B
{\displaystyle B}
是
A
{\displaystyle A}
中所有的元素乘以
a
{\displaystyle a}
组成的集合。因为
A
{\displaystyle A}
中的任何两个元素之差都不能被
p
{\displaystyle p}
整除,所以
B
{\displaystyle B}
中的任何两个元素之差也不能被
p
{\displaystyle p}
整除。
換句話說,
gcd
(
a
,
p
)
=
1
{\displaystyle \gcd(a,p)=1}
,考慮
1
×
a
,
2
×
a
,
3
×
a
,
.
.
.
.
(
p
−
1
)
×
a
{\displaystyle 1\times a,2\times a,3\times a,....(p-1)\times a}
共
(
p
−
1
)
{\displaystyle (p-1)}
個數,將它們分別除以
p
{\displaystyle p}
,餘數分別為
r
1
,
r
2
,
r
3
,
.
.
.
.
,
r
p
−
1
{\displaystyle r_{1},r_{2},r_{3},....,r_{p-1))
,則集合
{
r
1
,
r
2
,
r
3
,
.
.
.
.
,
r
p
−
1
}
{\displaystyle \{r_{1},r_{2},r_{3},....,r_{p-1}\))
為集合
{
1
,
2
,
3
,
…
,
(
p
−
1
)
}
{\displaystyle \{1,2,3,\ldots ,(p-1)\))
的重新排列,即
1
,
2
,
3
,
…
,
(
p
−
1
)
{\displaystyle 1,2,3,\ldots ,(p-1)}
在餘數中恰好各出現一次;這是因為對於任兩個相異
k
∗
a
{\displaystyle k*a}
而言(
k
=
1
,
2
,
3
,
…
,
(
p
−
1
)
{\displaystyle k=1,2,3,\ldots ,(p-1)}
),其差不是
p
{\displaystyle p}
的倍數(所以不會有相同餘數),且任一個
k
∗
a
{\displaystyle k*a}
亦不為
p
{\displaystyle p}
的倍數(所以餘數不為0)。因此
1
⋅
2
⋅
3
⋅
⋯
⋅
(
p
−
1
)
≡
(
1
⋅
a
)
⋅
(
2
⋅
a
)
⋅
⋯
⋅
(
(
p
−
1
)
⋅
a
)
(
mod
p
)
,
{\displaystyle 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 {p)),}
即
W
≡
W
⋅
a
p
−
1
(
mod
p
)
,
{\displaystyle W\equiv W\cdot a^{p-1}{\pmod {p)),}
在这里
W
=
1
⋅
2
⋅
3
⋅
…
⋅
(
p
−
1
)
{\displaystyle W=1\cdot 2\cdot 3\cdot \ldots \cdot (p-1)}
,且
(
W
,
p
)
=
1
{\displaystyle (W,p)=1}
,因此将整个公式除以
W
{\displaystyle W}
即得到:
a
p
−
1
≡
1
(
mod
p
)
{\displaystyle a^{p-1}\equiv 1{\pmod {p))}
[3]
也即
a
p
≡
a
(
mod
p
)
{\displaystyle a^{p}\equiv a{\pmod {p))}
(ii)若
p
{\displaystyle p}
整除
a
{\displaystyle a}
,则显然有
p
{\displaystyle p}
整除
a
p
{\displaystyle a^{p))
,即
a
p
≡
a
≡
0
(
mod
p
)
{\displaystyle a^{p}\equiv a\equiv 0{\pmod {p))}
。
若
p
{\displaystyle p}
为质数,
n
{\displaystyle n}
为整数,且
p
≥
n
{\displaystyle p\geq n}
。考慮二項式係數
(
p
n
)
=
p
!
n
!
(
p
−
n
)
!
{\displaystyle {\tbinom {p}{n))={\tfrac {p!}{n!(p-n)!))}
,並限定
n
{\displaystyle n}
不為
p
{\displaystyle p}
或
0
{\displaystyle 0}
,則由於分子有質數
p
{\displaystyle p}
,但分母不含
p
{\displaystyle p}
,故分子的
p
{\displaystyle p}
能保留,不被約分而除去,即
(
p
n
)
{\displaystyle {\tbinom {p}{n))}
恆為
p
{\displaystyle p}
的倍數[4] 。
再考慮
(
b
+
1
)
p
{\displaystyle (b+1)^{p))
的二項式展開,模
p
{\displaystyle p}
,則
(
b
+
1
)
p
≡
(
p
p
)
b
p
+
(
p
p
−
1
)
b
p
−
1
+
(
p
p
−
2
)
b
p
−
2
+
⋯
+
(
p
2
)
b
2
+
(
p
1
)
b
1
+
(
p
0
)
b
0
(
mod
p
)
{\displaystyle (b+1)^{p}\equiv {\dbinom {p}{p))b^{p}+{\dbinom {p}{p-1))b^{p-1}+{\dbinom {p}{p-2))b^{p-2}+\dots +{\dbinom {p}{2))b^{2}+{\dbinom {p}{1))b^{1}+{\dbinom {p}{0))b^{0}{\pmod {p))}
≡
(
p
p
)
b
p
+
(
p
0
)
b
0
(
mod
p
)
{\displaystyle \equiv {\dbinom {p}{p))b^{p}+{\dbinom {p}{0))b^{0}{\pmod {p))}
≡
b
p
+
1
(
mod
p
)
{\displaystyle \equiv b^{p}+1{\pmod {p))}
因此
(
b
+
1
)
p
≡
b
p
+
1
(
mod
p
)
{\displaystyle (b+1)^{p}\equiv b^{p}+1{\pmod {p))}
≡
(
b
−
1
)
p
+
1
+
1
(
mod
p
)
{\displaystyle \equiv (b-1)^{p}+1+1{\pmod {p))}
≡
(
b
−
2
)
p
+
1
+
1
+
1
(
mod
p
)
{\displaystyle \equiv (b-2)^{p}+1+1+1{\pmod {p))}
≡
(
b
−
3
)
p
+
1
+
1
+
1
+
1
(
mod
p
)
{\displaystyle \equiv (b-3)^{p}+1+1+1+1{\pmod {p))}
…
{\displaystyle \dots }
≡
1
+
1
+
⋯
+
1
+
1
⏟
b
+
1
(
mod
p
)
{\displaystyle \equiv {\begin{matrix}\underbrace {1+1+\dots +1+1} \\b+1\end{matrix)){\pmod {p))}
≡
b
+
1
(
mod
p
)
{\displaystyle \equiv b+1{\pmod {p))}
令
a
=
b
+
1
{\displaystyle a=b+1}
,即得
a
p
≡
a
(
mod
p
)
{\displaystyle a^{p}\equiv a{\pmod {p))}
。[3]
在抽象代数 教科书中,费马小定理常作为教授拉格朗日定理时的一个简单例子[5] 。显然只需考虑
(
a
,
p
)
=
1
{\displaystyle (a,p)=1}
情形。此时模
p
{\displaystyle p}
所有非零的余数,在同余意义下对乘法构成一个群,这个群的阶是
p
−
1
{\displaystyle p-1}
。考虑群中的任何一个元素
b
{\displaystyle b}
,根据拉格朗日定理,
b
{\displaystyle b}
的阶必整除群的阶。证毕。
計算
2
100
{\displaystyle 2^{100))
除以13的餘數
2
100
≡
2
12
×
8
+
4
(
mod
13
)
{\displaystyle 2^{100}\equiv 2^{12\times 8+4}{\pmod {13))}
≡
(
2
12
)
8
⋅
2
4
(
mod
13
)
{\displaystyle \equiv (2^{12})^{8}\cdot 2^{4}{\pmod {13))}
≡
1
8
⋅
16
(
mod
13
)
{\displaystyle \equiv 1^{8}\cdot 16{\pmod {13))}
≡
16
(
mod
13
)
{\displaystyle \equiv 16{\pmod {13))}
≡
3
(
mod
13
)
{\displaystyle \equiv 3{\pmod {13))}
故餘數為3。
證明對於任意整數a而言,
a
13
−
a
{\displaystyle a^{13}-a}
恆為2730的倍數。
易由
a
p
−
1
≡
1
(
mod
p
)
{\displaystyle a^{p-1}\equiv 1{\pmod {p))}
推得
a
n
(
p
−
1
)
+
1
≡
1
n
⋅
a
≡
a
(
mod
p
)
{\displaystyle a^{n(p-1)+1}\equiv 1^{n}\cdot a\equiv a{\pmod {p))}
,其中
n
{\displaystyle n}
為正整數。
故對指數13操作如下:13減1為12,12的正因數有1, 2, 3, 4, 6, 12,分別加1,為2, 3, 4, 5, 7, 13,其中2, 3, 5, 7, 13為質數,根據定理的延伸表達式,
a
13
−
a
{\displaystyle a^{13}-a}
為2的倍數、為3的倍數、為5的倍數、為7的倍數、為13的倍數,即2*3*5*7*13=2730的倍數。 费马小定理是欧拉定理 的一个特殊情况:如果
(
a
,
n
)
=
1
{\displaystyle (a,n)=1}
,那么
a
φ
(
n
)
≡
1
(
mod
n
)
{\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n))}
这里
φ
(
n
)
{\displaystyle \varphi (n)}
是欧拉函数 。欧拉函数的值是所有小于或等于
n
{\displaystyle n}
的正整数中与
n
{\displaystyle n}
互質 的数的个数。假如
n
{\displaystyle n}
是一个素数,则
φ
(
n
)
=
n
−
1
{\displaystyle \varphi (n)=n-1}
,即费马小定理。
证明 上面证明费马小定理的群论方法,可以同理地证明欧拉定理。
考虑所有与
n
{\displaystyle n}
互素的数,这些数模
n
{\displaystyle n}
的余数所构成的集合,记为
S
{\displaystyle {\cal {S))}
,并将群乘法定义为相乘后模
n
{\displaystyle n}
的同余。显然
S
{\displaystyle {\cal {S))}
是一个群,因为它对群乘法封闭(若
(
a
,
n
)
=
1
{\displaystyle (a,n)=1}
和
(
b
,
n
)
=
1
{\displaystyle (b,n)=1}
则
(
a
b
,
n
)
=
1
{\displaystyle (ab,n)=1}
),含幺元(即“1”),且任何一个元素
a
{\displaystyle a}
的逆元素也在集合中(因为若
a
∈
S
{\displaystyle a\in {\cal {S))}
则由群乘法封闭性任何
a
{\displaystyle a}
的幂次都在
S
{\displaystyle {\cal {S))}
中,所以
⟨
a
⟩
{\displaystyle \langle a\rangle }
是
S
{\displaystyle {\cal {S))}
这个有限集的子集)。根据定义,
S
{\displaystyle {\cal {S))}
的阶是
φ
(
n
)
{\displaystyle \varphi (n)}
,于是根据拉格朗日定理,
S
{\displaystyle {\cal {S))}
中任何一个元素的阶必整除
φ
(
n
)
{\displaystyle \varphi (n)}
。证毕。
卡邁克爾函數比欧拉函数更小。费马小定理也是它的特殊情况。
a
λ
(
n
)
≡
1
(
mod
n
)
{\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n))}
因為
p
|
x
p
−
x
⇒
p
k
|
(
x
p
−
x
)
k
{\displaystyle p|x^{p}-x\Rightarrow p^{k}|(x^{p}-x)^{k))
所以由
x
N
(
mod
(
x
p
−
x
)
k
)
{\displaystyle x^{N}{\pmod {(x^{p}-x)^{k))))
的結果可以得出
x
N
(
mod
p
k
)
{\displaystyle x^{N}{\pmod {p^{k))))
的結果
用多項式除法 可以得出
x
N
{\displaystyle x^{N))
除以
(
x
p
−
x
)
k
{\displaystyle (x^{p}-x)^{k))
的次數少於
p
k
{\displaystyle p^{k))
的餘式
例如
3
∣
x
3
−
x
{\displaystyle 3\mid x^{3}-x}
,由多項式除法得到
x
5
=
(
x
2
+
1
)
(
x
3
−
x
)
+
x
{\displaystyle x^{5}=(x^{2}+1)(x^{3}-x)+x}
,則
x
5
≡
x
(
mod
3
)
{\displaystyle x^{5}\equiv x{\pmod {3))}
這個餘式的一般結果是:
x
p
k
≡
∑
i
=
1
k
(
−
1
)
i
−
1
(
k
i
)
x
p
k
−
(
p
−
1
)
i
(
mod
p
k
)
{\displaystyle \displaystyle x^{pk}\equiv \sum _{i=1}^{k}(-1)^{i-1}{\binom {k}{i))x^{pk-(p-1)i}{\pmod {p^{k))))
(除式)
x
p
k
+
(
p
−
1
)
n
≡
∑
i
=
1
k
(
−
1
)
i
−
1
(
n
+
i
−
1
i
−
1
)
(
n
+
k
k
−
i
)
x
p
k
−
(
p
−
1
)
i
(
mod
p
k
)
{\displaystyle \displaystyle x^{pk+(p-1)n}\equiv \sum _{i=1}^{k}(-1)^{i-1}{\binom {n+i-1}{i-1)){\binom {n+k}{k-i))x^{pk-(p-1)i}{\pmod {p^{k))))
n=0时为除式,用数学归纳法 证明余式。[6]
求
x
1000
(
mod
5
2
)
{\displaystyle x^{1000}{\pmod {5^{2))))
x
10
+
4
n
≡
(
n
+
2
)
x
6
−
(
n
+
1
)
x
2
(
mod
5
2
)
{\displaystyle x^{10+4n}\equiv (n+2)x^{6}-(n+1)x^{2}{\pmod {5^{2))))
x
1000
≡
249
x
8
−
248
x
4
≡
24
x
8
−
23
x
4
(
mod
5
2
)
{\displaystyle x^{1000}\equiv 249x^{8}-248x^{4}\equiv 24x^{8}-23x^{4}{\pmod {5^{2))))
^ Fermat's Little Theorem (页面存档备份 ,存于互联网档案馆 ).WolframMathWorld.(英文)
^ A proof of certain theorems regarding prime numbers . [2012-12-11 ] . (原始内容存档 于2015-06-16).
^ 3.0 3.1 許介彥. 費馬小定理 (PDF) . 科學教育月刊 (私立大葉大學電機工程學系). 2006年10月, (第293期): 37–44 [2015-04-18 ] . (原始内容 (PDF) 存档于2015-04-18).
^ How is (x+y)^p≡x^p+y^p mod p for any prime number p . Mathematics Stack Exchange. 2018-09-27 [2021-04-26 ] . (原始内容 存档于2022-03-25) (英语) .
^ 聂灵沼; 丁石孙. 代数学引论 第二版. 北京: 高等教育出版社. 2000: 第33页. ISBN 7-04-008893-2 .
^ 黄嘉威. 多项式除法解高次同余 . 数学学习与研究. 2015, (9): 第104页 [2015-07-19 ] . (原始内容存档 于2020-10-20).
成就 相關
以皮埃爾·德·費馬命名的事物列表
懷爾斯對費馬大定理的證明
流行作品中的費馬大定理
費馬獎
《費馬的最後探戈 》(2000年音樂劇)
《費馬大定理 》(科普書籍)