|
|
相关文章推荐
|
斯文的刺猬 · 从费马大定理到现代密码学· 2 年前 · |
|
|
斯文的刺猬 · 费马大定理当n=3时简单证明- 知乎· 2 年前 · |
|
|
斯文的刺猬 · 安德鲁·怀尔斯证明费马大定理原文- 知乎· 2 年前 · |
|
|
斯文的刺猬 · 密码学-07-欧拉函数乘积公式推导· ...· 2 年前 · |
|
|
斯文的刺猬 · 数论——欧拉函数_bggl的博客-CSDN博客· 2 年前 · |
\because ac\equiv bc(mod~m)\\ \therefore ac-bc\equiv0(mod~m)\\ \therefore(a-b)c\equiv0(mod~m)\\ \because (c,m)=1\\ \therefore c在模m下存在逆元c^{-1}\\ \therefore (a-b)cc^{-1}=0(mod~m)\\ \therefore a-b\equiv0(mod~m)\\ \therefore a\equiv b(mod~m)\\
∵
a
c
≡
b
c
(
m
o
d
m
)
∴
a
c
−
b
c
≡
0
(
m
o
d
m
)
∴
(
a
−
b
)
c
≡
0
(
m
o
d
m
)
∵
(
c
,
m
)
=
1
∴
c
在
模
m
下
存
在
逆
元
c
−
1
∴
(
a
−
b
)
c
c
−
1
=
0
(
m
o
d
m
)
∴
a
−
b
≡
0
(
m
o
d
m
)
∴
a
≡
b
(
m
o
d
m
)
再来第二个引理：
给定一个数m，和对应的一个完全剩余系\{a_1,a_2,a_3...,a_{m-1}\}\\ \forall(c,m)=1,\{a_1c,a_2c,a_3c,a_{p-1}c\}在模m下也是一个完全剩余系\\ 给 定 一 个 数 m ， 和 对 应 的 一 个 完 全 剩 余 系 { a 1 , a 2 , a 3 . . . , a m − 1 } ∀ ( c , m ) = 1 , { a 1 c , a 2 c , a 3 c , a p − 1 c } 在 模 m 下 也 是 一 个 完 全 剩 余 系
证明：
假设在\{a_1c,a_2c,a_3c,a_{p-1}c\}中,\exists a_ic\equiv a_jc(mod~m)(i\neq j)\\ 则根据引理1，可知a_i\equiv a_j(mod~m)\\ 与条件中的a_i,a_j是属于一个完全剩余系下矛盾，所以假设不成立\\ 得证：\{a_1c,a_2c,a_3c,a_{p-1}c\}的每一个值在模m下都不相等\\ 根据抽屉原理可知\{a_1c,a_2c,a_3c,a_{p-1}c\}也是一个完全剩余系。 假 设 在 { a 1 c , a 2 c , a 3 c , a p − 1 c } 中 , ∃ a i c ≡ a j c ( m o d m ) ( i = j ) 则 根 据 引 理 1 ， 可 知 a i ≡ a j ( m o d m ) 与 条 件 中 的 a i , a j 是 属 于 一 个 完 全 剩 余 系 下 矛 盾 ， 所 以 假 设 不 成 立 得 证 ： { a 1 c , a 2 c , a 3 c , a p − 1 c } 的 每 一 个 值 在 模 m 下 都 不 相 等 根 据 抽 屉 原 理 可 知 { a 1 c , a 2 c , a 3 c , a p − 1 c } 也 是 一 个 完 全 剩 余 系 。
再来第二个引理：
给定一个数m，和对应的一个完全剩余系\{a_1,a_2,a_3...,a_{m-1}\}\\ \forall(c,m)=1,\{a_1c,a_2c,a_3c,a_{p-1}c\}在模m下也是一个完全剩余系\\ 给 定 一 个 数 m ， 和 对 应 的 一 个 完 全 剩 余 系 { a 1 , a 2 , a 3 . . . , a m − 1 } ∀ ( c , m ) = 1 , { a 1 c , a 2 c , a 3 c , a p − 1 c } 在 模 m 下 也 是 一 个 完 全 剩 余 系
证明：
假设在\{a_1c,a_2c,a_3c,a_{p-1}c\}中,\exists a_ic\equiv a_jc(mod~m)(i\neq j)\\ 则根据引理1，可知a_i\equiv a_j(mod~m)\\ 与条件中的a_i,a_j是属于一个完全剩余系下矛盾，所以假设不成立\\ 得证：\{a_1c,a_2c,a_3c,a_{p-1}c\}的每一个值在模m下都不相等\\ 根据抽屉原理可知\{a_1c,a_2c,a_3c,a_{p-1}c\}也是一个完全剩余系。 假 设 在 { a 1 c , a 2 c , a 3 c , a p − 1 c } 中 , ∃ a i c ≡ a j c ( m o d m ) ( i = j ) 则 根 据 引 理 1 ， 可 知 a i ≡ a j ( m o d m ) 与 条 件 中 的 a i , a j 是 属 于 一 个 完 全 剩 余 系 下 矛 盾 ， 所 以 假 设 不 成 立 得 证 ： { a 1 c , a 2 c , a 3 c , a p − 1 c } 的 每 一 个 值 在 模 m 下 都 不 相 等 根 据 抽 屉 原 理 可 知 { a 1 c , a 2 c , a 3 c , a p − 1 c } 也 是 一 个 完 全 剩 余 系 。
接下来就是证明费马小定理了：
对于一个素数p，我们先构造一个模p的完全剩余系\{0, 1,2,3,...,p-1\}。\\ 对于\forall a,满足(a,p)=1，则\{0, a,2a,3a,...,(p-1)a\}也是一个完全剩余系\\ \therefore 1\times2\times3...\times(p-1)\equiv a\times2a\times3a...\times(p-1)a(mod~p)\\ (p-1)!\equiv a^{p-1}(p-1)!(mod~p)\\ \because ((p-1)!,p)=1， 引理1\\ \therefore a^{p-1}=1(mod~p)\\
对
于
一
个
素
数
p
，
我
们
先
构
造
一
个
模
p
的
完
全
剩
余
系
{
0
,
1
,
2
,
3
,
.
.
.
,
p
−
1
}
。
对
于
∀
a
,
满
足
(
a
,
p
)
=
1
，
则
{
0
,
a
,
2
a
,
3
a
,
.
.
.
,
(
p
−
1
)
a
}
也
是
一
个
完
全
剩
余
系
∴
1
×
2
×
3
.
.
.
×
(
p
−
1
)
≡
a
×
2
a
×
3
a
.
.
.
×
(
p
−
1
)
a
(
m
o
d
p
)
(
p
−
1
)
!
≡
a