费马小定理,欧拉定理和广义欧拉定理
参考
费马小定理
设 p p p 为素数，且 p ∤ a p \nmid a p∤a 则 a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1 \pmod p ap−1≡1(modp)
证明
因为
p
∤
a
p\nmid a
p∤a，所以
a
,
2
a
,
…
,
(
p
−
1
)
a
a,2a,\ldots,(p-1)a
a,2a,…,(p−1)a 模
p
p
p 恰好是
1
,
2
,
…
,
p
−
1
1,2,\ldots,p-1
1,2,…,p−1 的一个排列。
因此
a
p
−
1
(
p
−
1
)
!
≡
(
p
−
1
)
!
(
m
o
d
p
)
.
a^{p-1}(p-1)!\equiv(p-1)!\pmod p.
ap−1(p−1)!≡(p−1)!(modp).
又因为
p
∤
(
p
−
1
)
!
p\nmid(p-1)!
p∤(p−1)!，可约去
(
p
−
1
)
!
(p-1)!
(p−1)!，得到
a
p
−
1
≡
1
(
m
o
d
p
)
.
\boxed{a^{p-1}\equiv1\pmod p}.
ap−1≡1(modp).
欧拉定理
设 m ≥ 1 m \geq 1 m≥1且 ( a , m ) = 1 (a, m) = 1 (a,m)=1，则 a φ ( m ) ≡ 1 ( m o d m ) a^{\varphi(m)} \equiv 1 \pmod m aφ(m)≡1(modm)
证明
因为
(
a
,
m
)
=
1
(a,m)=1
(a,m)=1，所以设
r
1
,
r
2
,
…
,
r
φ
(
m
)
r_1,r_2,\ldots,r_{\varphi(m)}
r1,r2,…,rφ(m)
是模
m
m
m 的一个既约剩余系。
先证明
a
r
1
,
a
r
2
,
…
,
a
r
φ
(
m
)
ar_1,ar_2,\ldots,ar_{\varphi(m)}
ar1,ar2,…,arφ(m)模
m
m
m 仍构成一个既约剩余系
因为
(
a
,
m
)
=
1
(a,m)=1
(a,m)=1
所以
(
a
r
i
,
m
)
=
1
(ar_i,m)=1
(ari,m)=1
反证
假设
a
r
1
,
a
r
2
,
…
,
a
r
φ
(
m
)
ar_1,ar_2,\ldots,ar_{\varphi(m)}
ar1,ar2,…,arφ(m)模
m
m
m 不构成一个既约剩余系
则存在
互异的
r
i
和
r
j
r_i和r_j
ri和rj
使得
a
r
i
≡
a
r
j
(
m
o
d
m
)
ar_i\equiv ar_j\pmod m
ari≡arj(modm)
则
a
(
r
i
−
r
j
)
≡
0
(
m
o
d
m
)
a(r_i-r_j)\equiv0\pmod m
a(ri−rj)≡0(modm)
由于
(
a
,
m
)
=
1
(a,m)=1
(a,m)=1
所以
r
i
≡
r
j
(
m
o
d
m
)
r_i\equiv r_j\pmod m
ri≡rj(modm)
和
r
1
,
r
2
,
…
,
r
φ
(
m
)
r_1,r_2,\ldots,r_{\varphi(m)}
r1,r2,…,rφ(m)
是模
m
m
m 的一个既约剩余系矛盾。
因此
a
r
1
,
a
r
2
,
…
,
a
r
φ
(
m
)
ar_1,ar_2,\ldots,ar_{\varphi(m)}
ar1,ar2,…,arφ(m)
模
m
m
m 仍构成一个既约剩余系。
于是
a
φ
(
m
)
r
1
r
2
⋯
r
φ
(
m
)
≡
r
1
r
2
⋯
r
φ
(
m
)
(
m
o
d
m
)
a^{\varphi(m)}r_1r_2\cdots r_{\varphi(m)} \equiv r_1r_2\cdots r_{\varphi(m)} \pmod m
aφ(m)r1r2⋯rφ(m)≡r1r2⋯rφ(m)(modm)。
又因为每个
r
i
r_i
ri 都与
m
m
m 互质，所以
(
r
1
r
2
⋯
r
φ
(
m
)
,
m
)
=
1
(r_1r_2\cdots r_{\varphi(m)},m)=1
(r1r2⋯rφ(m),m)=1
可以约去，得到
a
φ
(
m
)
≡
1
(
m
o
d
m
)
a^{\varphi(m)}\equiv1\pmod m
aφ(m)≡1(modm)
广义欧拉定理
a b ≡ a r + ( ( b − r ) m o d T ) ( m o d m ) , r ≥ s \boxed{ a^b\equiv a^{\,r+((b-r)\bmod T)}\pmod m, \qquad r\ge s } ab≡ar+((b−r)modT)(modm),r≥s
其中
s
,
T
s,T
s,T 为
s
=
{
0
,
(
a
,
m
)
=
1
,
max
p
∣
(
a
,
m
)
⌈
v
p
(
m
)
v
p
(
a
)
⌉
,
(
a
,
m
)
≠
1
,
s= \begin{cases} 0, & (a,m)=1,\\[6pt] \displaystyle \max_{p\mid(a,m)} \left\lceil \frac{v_p(m)}{v_p(a)} \right\rceil, & (a,m)\ne1, \end{cases}
s=⎩
⎨
⎧0,p∣(a,m)max⌈vp(a)vp(m)⌉,(a,m)=1,(a,m)=1,
T
=
{
ord
m
0
(
a
)
,
m
0
>
1
,
1
,
m
0
=
1.
T= \begin{cases} \operatorname{ord}_{m_0}(a), & m_0>1,\\[6pt] 1, & m_0=1. \end{cases}
T=⎩
⎨
⎧ordm0(a),1,m0>1,m0=1.
其中
m
0
m_0
m0是与
a
a
a互质最大的m因子。
s , T s,T s,T 满足
s
≤
max
p
∣
m
v
p
(
m
)
≤
φ
(
m
)
\boxed{s\le\max_{p\mid m}v_p(m)\le\varphi(m)}
s≤p∣mmaxvp(m)≤φ(m)
T
≤
λ
(
m
0
)
≤
φ
(
m
0
)
≤
φ
(
m
)
\boxed{T\le\lambda(m_0)\le\varphi(m_0)\le\varphi(m)}
T≤λ(m0)≤φ(m0)≤φ(m)
且有整除链
且有整除链
且有整除链
T
∣
λ
(
m
0
)
∣
φ
(
m
0
)
∣
φ
(
m
)
\boxed {T | \lambda(m_0) |\varphi(m_0) | \varphi(m)}
T∣λ(m0)∣φ(m0)∣φ(m)
证明
由
s
,
T
s,T
s,T 的定义，数列
a
0
,
a
1
,
a
2
,
…
(
m
o
d
m
)
a^0,a^1,a^2,\ldots\pmod m
a0,a1,a2,…(modm)
从第
s
s
s 项开始以
T
T
T 为周期，因此
a t + T ≡ a t ( m o d m ) , t ≥ s . a^{t+T}\equiv a^t\pmod m, \qquad t\ge s. at+T≡at(modm),t≥s.
取 r ≥ s r\ge s r≥s，且 b ≥ r b\ge r b≥r。
由带余除法，
b − r = q T + ρ , b-r=qT+\rho, b−r=qT+ρ,
其中
ρ = ( b − r ) m o d T , 0 ≤ ρ < T . \rho=(b-r)\bmod T, \qquad 0\le\rho<T. ρ=(b−r)modT,0≤ρ<T.
因此
b = r + q T + ρ . b=r+qT+\rho. b=r+qT+ρ.
于是
a b = a r + q T + ρ . a^b =a^{r+qT+\rho}. ab=ar+qT+ρ.
由于
r
≥
s
r\ge s
r≥s，已经进入循环区，所以指数每增加
T
T
T，
模
m
m
m 的结果不变，即
a r + q T + ρ ≡ a r + ρ ( m o d m ) . a^{r+qT+\rho} \equiv a^{r+\rho} \pmod m. ar+qT+ρ≡ar+ρ(modm).
代入
ρ
=
(
b
−
r
)
m
o
d
T
\rho=(b-r)\bmod T
ρ=(b−r)modT，得到
a b ≡ a r + ( ( b − r ) m o d T ) ( m o d m ) \boxed{ a^b\equiv a^{\,r+((b-r)\bmod T)} \pmod m } ab≡ar+((b−r)modT)(modm)
例1 用广义欧拉定理证明欧拉定理
因为
(
a
,
m
)
=
1
(a,m)=1
(a,m)=1，所以
s
=
0
s=0
s=0，取
T
=
φ
(
m
)
,
b
=
φ
(
m
)
,
r
=
0.
T=\varphi(m),b=\varphi(m), r=0.
T=φ(m),b=φ(m),r=0.
于是
a
φ
(
m
)
≡
a
φ
(
m
)
m
o
d
T
=
a
0
=
1
(
m
o
d
m
)
.
a^{\varphi(m)} \equiv a^{\,\varphi(m)\bmod T} =a^0 =1\pmod m.
aφ(m)≡aφ(m)modT=a0=1(modm).
因此
a
φ
(
m
)
≡
1
(
m
o
d
m
)
.
\boxed{a^{\varphi(m)}\equiv1\pmod m}.
aφ(m)≡1(modm).
例2 用广义欧拉定理证明欧拉降幂公式
a b ≡ a φ ( m ) + ( b m o d φ ( m ) ) ( m o d m ) , b ≥ φ ( m ) . \boxed{ a^b\equiv a^{\,\varphi(m)+(b\bmod\varphi(m))} \pmod m }, \qquad b\ge\varphi(m). ab≡aφ(m)+(bmodφ(m))(modm),b≥φ(m).
由广义欧拉定理
a
b
≡
a
r
+
(
(
b
−
r
)
m
o
d
T
)
(
m
o
d
m
)
,
r
≥
s
.
a^b\equiv a^{\,r+((b-r)\bmod T)}\pmod m, \qquad r\ge s.
ab≡ar+((b−r)modT)(modm),r≥s.
取
r
=
φ
(
m
)
.
r=\varphi(m).
r=φ(m).
由
s
≤
φ
(
m
)
,
T
∣
φ
(
m
)
,
s\le\varphi(m),\qquad T\mid\varphi(m),
s≤φ(m),T∣φ(m),
可知
r
≥
s
r\ge s
r≥s，且
(
b
−
φ
(
m
)
)
m
o
d
T
=
b
m
o
d
T
.
(b-\varphi(m))\bmod T=b\bmod T.
(b−φ(m))modT=bmodT.
因此
a
b
≡
a
φ
(
m
)
+
(
b
m
o
d
T
)
(
m
o
d
m
)
≡
a
φ
(
m
)
+
(
b
m
o
d
φ
(
m
)
)
(
m
o
d
m
)
.
\begin{aligned} a^b &\equiv a^{\,\varphi(m)+(b\bmod T)} \pmod m\\ &\equiv a^{\,\varphi(m)+(b\bmod\varphi(m))} \pmod m. \end{aligned}
ab≡aφ(m)+(bmodT)(modm)≡aφ(m)+(bmodφ(m))(modm).
故得到欧拉降幂公式：
a
b
≡
a
φ
(
m
)
+
(
b
m
o
d
φ
(
m
)
)
(
m
o
d
m
)
,
b
≥
φ
(
m
)
.
\boxed{ a^b\equiv a^{\,\varphi(m)+(b\bmod\varphi(m))} \pmod m }, \qquad b\ge\varphi(m).
ab≡aφ(m)+(bmodφ(m))(modm),b≥φ(m).
openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构
更多推荐
11
0- 0
已为社区贡献1条内容
所有评论(0)