若
p
p
p为质数，且
(
a
,
p
)
=
1
(a,p)=1
(a,p)=1，那么则有
a
p
−
1
≡
1
(
m
o
d
p
)
a^{p-1}equiv1pmod p
ap−1≡1(modp)
应用
一般用于求模质数意义下的逆元，
定理两边同时除以
a
a
a有
a
p
−
2
≡
1
a
(
m
o
d
p
)
a^{p-2}equivfrac{1}{a}pmod p
ap−2≡a1(modp)，
则此时
a
p
−
2
a^{p-2}
ap−2即为
a
a
a的逆元。
还可以简化模意义下乘方运算的指数，当指数较大时，
a
c
≡
a
c
m
o
d
(
p
−
1
)
(
m
o
d
p
)
a^cequiv a^{cmod (p-1)}pmod p
ac≡acmod(p−1)(modp)。
欧拉定理
若
(
a
,
m
)
=
1
(a,m)=1
(a,m)=1，那么则有
a
ϕ
m
≡
1
(
m
o
d
m
)
a^{phi m}equiv1pmod m
aϕm≡1(modm)
发现当
m
m
m为质数时，
ϕ
m
=
m
−
1
phi m=m-1
ϕm=m−1，则恰好是费马小定理。其实欧拉定理正是费马小定理的扩展。
应用
与费马小定理类似，可以用于求乘法逆元和简化模意义下乘方运算的指数。
扩展欧拉定理
a
c
≡
{
a
c
m
o
d
ϕ
p
,
(
a
,
p
)
=
1
a
c
,
(
a
,
p
)
≠
1
,
c
<
ϕ
p
a
c
m
o
d
ϕ
p
+
ϕ
p
,
(
a
,
p
)
≠
1
,
c
≥
ϕ
p
a^cequiv egin{cases} a^{cmod phi p} ,&(a,p)=1\ a^c, & (a,p)
eq1,c<phi p\ a^{cmodphi p+phi p},&(a,p)
eq1,cgeqphi p\ end{cases}
ac≡⎩⎪⎨⎪⎧acmodϕp,ac,acmodϕp+ϕp,(a,p)=1(a,p)�=1,c<ϕp(a,p)�=1,c≥ϕp
(
m
o
d
p
)
pmod p
(modp)