首页
A
0bazb7po
当前主题：自动模式
查看保存队列
搜索
专栏文章
学习笔记：证明欧拉定理
c
chenxi797
2025/08/26 13:11
算法·理论
参与者 1
已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
当前评论
0 条
当前快照
1 份
快照标识符
@mio4o7z8
此快照首次捕获于
2025/12/02 13:18
3 个月前
此快照最后确认于
2025/12/02 13:18
3 个月前
查看原文
时光机
更新文章
复制链接
复制快照链接
复制正文 Markdown
前置知识：
欧拉函数
什么是欧拉定理？
若
gcd
(
a
,
b
)
=
1
\gcd(a,b) = 1
g
cd
(
a
,
b
)
=
1
，则：
a
φ
(
n
)
≡
1
(
m
o
d
p
)
a^{\varphi(n)} \equiv 1 \ (\bmod \ p)
a
φ
(
n
)
≡
1
(
mod
p
)
简单证明
设集合：
S
=
{
x
∣
1
≤
x
≤
n
,
gcd
(
x
,
n
)
=
1
}
S = \{x \ | \ 1 \le x \le n,\gcd(x,n) = 1\}
S
=
{
x
∣
1
≤
x
≤
n
,
g
cd
(
x
,
n
)
=
1
}
不难看出，集合大小为
φ
(
n
)
\varphi(n)
φ
(
n
)
。
将集合内每一个数
n
n
n
乘以
gcd
(
a
,
n
)
=
1
\gcd(a,n) = 1
g
cd
(
a
,
n
)
=
1
的数
a
a
a
，得到：
x
1
x
2
⋯
x
φ
(
n
)
≡
(
a
x
1
)
(
a
x
2
)
⋯
(
a
x
φ
(
n
)
)
(
m
o
d
n
)
x_1x_2 \cdots x_{\varphi(n)} \equiv (ax_1)(ax_2) \cdots (ax_{\varphi(n)}) \ \ (\bmod \ n)
x
1
x
2
⋯
x
φ
(
n
)
≡
(
a
x
1
)
(
a
x
2
)
⋯
(
a
x
φ
(
n
)
)
(
mod
n
)
把
a
φ
(
n
)
a^{\varphi(n)}
a
φ
(
n
)
提出来，得：
x
1
x
2
⋯
x
φ
(
n
)
≡
a
φ
(
n
)
(
x
1
x
2
⋯
x
φ
(
n
)
)
(
m
o
d
n
)
x_1x_2 \cdots x_{\varphi(n)} \equiv a^{\varphi(n)} (x_1x_2 \cdots x_{\varphi(n)}) \ \ (\bmod \ n)
x
1
x
2
⋯
x
φ
(
n
)
≡
a
φ
(
n
)
(
x
1
x
2
⋯
x
φ
(
n
)
)
(
mod
n
)
消去公因子得：
a
φ
(
n
)
≡
1
a^{\varphi(n)} \equiv 1
a
φ
(
n
)
≡
1
证毕。
相关推荐
评论
共 0 条评论，欢迎与作者交流。
最新优先
最早优先
搜索
正在加载评论...
欧拉函数