没有合适的资源?快使用搜索试试~ 我知道了~
首页2012年麻省理工数论课程精华:基本概念与应用
2012年麻省理工数论课程精华:基本概念与应用
需积分: 10 3 下载量 194 浏览量
更新于2024-07-04
收藏 15.76MB PDF 举报
麻省理工学院的本科数论课程笔记,18.781-Theory of Numbers,春季2012,由Abhinav Kumar 教授主讲,是公开可获取的学习资源。这些笔记涵盖了数论的广泛内容,旨在引导学生探索这个数学领域中的基本概念和美学。数论,作为数学的基础分支,研究的是整数集Z(包括正负整数)及其性质,同时也涉及自然数集N,特别是其中的基本运算如加法、减法、乘法和除法。 课程从入门开始,定义了数论的核心概念,如迪奥芬特方程,探讨了整数的可除性和最大公约数(GCD)。教授强调了数论的重要性,指出它是构建其他高级数学理论的基石,比如实分析中的 Dedekind 切割,进而发展到有理数集 Q,再进一步至实数集 R。数论被视为数学皇冠上的明珠,它的应用不仅限于纯粹的数学,还服务于天文学和其他自然科学,展现了其优雅和深远的影响。 数论的技术手段来自多种数学领域,包括代数、分析、几何、拓扑、逻辑,以及计算机科学。这意味着学习数论的学生将接触到一系列丰富的工具,如群论、环论、域论、复数结构等。课程可能涉及到费马大定理、素数分布、同余理论、椭圆曲线密码学等现代数论的热点话题,这些都是当前IT行业中的关键技术基础,对于理解加密算法、网络安全等领域至关重要。 这些笔记提供了深入理解数论的系统框架,适合对数学有兴趣的本科生或研究生,以及希望在IT行业从事密码学、信息安全或算法设计的从业者。通过阅读和学习这些资料,学生们不仅可以掌握数论的核心概念,还能培养抽象思维能力,提升解决复杂问题的能力。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/85235585/bg11.jpg)
Lecture 4
(Definition) Complete Residue System:
A
complete residue system mod m
is a collection of integers
a
1
. . . a
m
such that
a
i
6≡ a
j
mod m
if
i = j
and any
integer n is congruent to some a
i
mod m
(Definition) Reduced Residue System:
A
reduced residue system mod m
is
a collection of integers
a
1
. . . a
k
such that
a
i
6≡ a
j
mod m
if
i = j
and
(a
i
, m) = 1
for all
i
, and any integer
n
coprime to
m
must be congruent to some
a
i
mod m
.
Eg., take any complete residue system mod
m
and take the subset consisting of
all the integers in it which are coprime to
m
- these will form a reduced residue
system
Eg. For m = 12
complete = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
reduced = {1, 5, 7, 11}
(Definition) Euler’s Totient Function:
The number of elements in a reduced
residue system mod
m
is called
Euler’s totient function
:
φ(m)
(ie., the number
of positive integers ≤ m and coprime to m)
Theorem 15 (Euler’s Theorem).
If (a, m) = 1, then a
φ(m)
≡ 1 mod m
Proof.
Lemma 16.
If
(a, m) = 1
and
r
1
. . . r
k
is a reduced residue system mod
m
,
k = φ(m)
,
then ar
1
. . . ar
k
is also a reduced residue system mod m.
Proof.
All we need to show is that
ar
i
are all coprime to
m
and distinct mod
m
,
since there are
k
of these
ar
i
and
k
is the number of elements in any residue
system mod
m
. We know that if
(r, m) = 1
and
(a, m) = 1
then
(ar, m) = 1
.
Also, if we had
ar
i
≡ ar
j
mod m
, then
m|ar
i
− ar
j
= a(r
i
− r
j
)
. If
(a, m) = 1
then m|r
i
− r
j
⇒ r
i
≡ r
j
mod m, which cannot happen unless i = j.
Choose a reduced residue system
r
1
. . . r
k
mod m
with
k = φ(m)
. By lemma,
ar
1
. . . ar
k
is also a reduced residue system. These two must be permutations of
6
6
1
FFermat, Euler, Wilson, Linear Congruences
![](https://csdnimg.cn/release/download_crawler_static/85235585/bg12.jpg)
each other mod m (ie., ar
i
≡ r
j(i)
mod m).
r
1
r
2
. . . r
k
≡ ar
1
ar
2
. . . ar
k
(mod m)
r r . . . r ≡ a
φ(m)
1 2 k
r
1
r
2
. . . r
k
(mod m)
(r
1
r
2
. . . r
k
, m) = 1 ⇒ can cancel
a
φ(m)
≡ 1 (mod m)
Corollary 17 (Fermat’s Little Theorem).
a
p
≡ a (mod p) for prime p and integer a
Proof.
If
p - a
(ie.,
(a, p) = 1
) then
a
φ(p)
≡ 1 mod p
by Euler’s Theorem.
φ(p) =
p − 1 ⇒ a
p−1
≡ 1 mod p ⇒ a
p
≡ a mod p
. If
p|a
, then
a ≡ 0 mod p
so both
sides are 0 ≡ 0 mod p.
Proof by induction.
Lemma 18 (Freshman’s Dream).
(x + y)
p
≡ x
p
+ y
p
(mod p) x, y ∈ Z, prime p
Use the Binomial Theorem.
p−1
(x + y)
p
= x
p
+ y
p
+
X
p
x
k
y
p−k
k
k=1
≡0 mod p
We saw that
p
is divisible by p 1
k
for ≤ k ≤
|
p − 1
{z
, so
}
(x + y)
p
≡ x
p
+ y
p
(mod p)
Induction base case of
a = 0
is obvious. Check to see if it holds for
a + 1
assuming it holds for a
(a + 1)
p
− (a + 1) ≡ a
p
+ 1 − (a + 1) (mod p)
≡ a
p
− a (mod p)
≡ 0 (mod p)
(a + 1)
p
≡ (a + 1) (mod p)
This is reversible (if holds for
a
, then also for
a −1
), and so holds for all integers
by stepping up or down
2
![](https://csdnimg.cn/release/download_crawler_static/85235585/bg13.jpg)
Proposition 19
(Inverses of elements mod
m
)
.
If
(a, m) = 1
, then there is a unique
integer b mod m such that ab ≡ 1 mod m. This b is denoted by
1
a
or a
−1
mod m
Proof of Existence.
Since
(a, m) = 1
we know that
ax + my = 1
for some integers
x, y, and so ax ≡ 1 mod m. Set b = x.
Proof of Uniqueness.
If
ab
1
≡ 1 mod m
and
ab
2
≡ 1 mod m
, then
ab
1
≡ ab
2
mod m ⇒ m|a(b
1
− b
2
). Since (m, a) = 1, m|b
1
− b
2
⇒ b
1
≡ b
2
mod m.
Theorem 20 (Wilson’s Theorem). If p is a prime then (p − 1)! ≡ −1 mod p
Proof. Assume that p is odd (trivial for p = 2).
Lemma 21. The congruence x
2
≡ 1 mod p has only the solutions x ≡ ±1 mod p
Proof.
x
2
≡ 1 mod p
⇒ p|x
2
− 1
⇒ p|(x − 1)(x + 1)
⇒ p|x ± 1
⇒ x ≡ ±1 mod p
Note that x
2
≡ 1 mod p ⇒ (x, p) = 1 and x has inverse and x ≡ x
−1
mod p
{1 . . . p −1}
is a reduced residue system mod
p
. Pair up elements
a
with inverse
a
−1
mod p. Only singletons will be 1 and −1.
(p − 1)! ≡ (a
1
· a
−1
1
)(a
1 1
2
· a
−
2
) . . . (a
k
· a
−
k
)(1)(−1) (mod p)
≡ −1 (mod p)
Wilson’s Theorem lets us solve congruence x
2
≡ −1 mod p
Theorem 22.
The congruence
x
2
≡ −1 mod p
is solvable if and only if
p = 2
or
p ≡ 1 mod 4
3
![](https://csdnimg.cn/release/download_crawler_static/85235585/bg14.jpg)
Proof. p = 2
is easy. We’ll show that there is no solution for
p ≡ 3 mod 4
by
contradiction. Assume
x
2
≡ −1 mod p
for some
x
coprime to
p
(
p = 4k + 3
).
Note that
p − 1 = 4k + 2 = 2(2k + 1)
so (x
2
)
2k+1
≡ (−1)
2k+1
≡ −1 mod p. But also,
(x
2
)
2k+1
≡ x
4k+2
≡ x
p−1
≡ 1 mod p
So 1 ≡ −1 mod p ⇒ p|2, which is impossible since p is an odd prime.
If p ≡ 1 mod 4:
(p − 1)! ≡ −1 (mod p) by Wilson’s Theorem
(1)(2) . . . (p − 1)
≡ −1 (mod p)
p
1 · 2 . . .
− 1 p + 1
. . . p )
|
2
− 1 ≡ −1 (mod p
{z
x
}|
2
show that second
equals
{z
factor
the first
p
}
− 1 ≡ (−1)1 (mod p)
p − 2 ≡ (−1)2 (mod p)
.
.
.
p + 1 p 1
≡ (−1)
−
(mod p)
2 2
p + 1
p−1
p 1
. . . (p − 1) ≡ (−1)
2
1 · 2 . . .
|
2
−
second
{z
factor
}
2
(mod p)
| {z
x
}
p−1
2
is even
since
p ≡ 1 mod 4
, and so second factor equals the first factor, so
x =
p−1
!
2
solves x
2
≡ −1 mod p if p ≡ 1 mod 4.
Theorem 23. There are infinitely many primes of form 4k + 1
Proof.
As in Euclid’s proof, assume finitely many such primes
p
1
. . . p
n
. Con-
sider the positive integer
N = (2p p . . . p )
2
1 2 n
+ 1
N
is an odd integer
> 1
, so it has an odd prime factor
q = p
i
, since each
p
i
divides
N − 1
.
q|N ⇒ (2p . . . p )
2
≡ −1 mod q
, so
x
2
1 n
≡ −1 mod q
has a
solution and so by theorem q ≡ 1 mod 4, which contradicts q = p
i
.
6
6
4
剩余138页未读,继续阅读
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/b3e701b6e4484ae888d2c4e4f05f02ce_m0_66201040.jpg!1)
![](https://csdnimg.cn/release/wenkucmsfe/public/img/user-vip.1c89f3c5.png)
醒过来摸鱼
- 粉丝: 2w+
- 资源: 4
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 解决本地连接丢失无法上网的问题
- BIOS报警声音解析:故障原因与解决方法
- 广义均值移动跟踪算法在视频目标跟踪中的应用研究
- C++Builder快捷键大全:高效编程的秘密武器
- 网页制作入门:常用代码详解
- TX2440A开发板网络远程监控系统移植教程:易搭建与通用解决方案
- WebLogic10虚拟内存配置详解与优化技巧
- C#网络编程深度解析:Socket基础与应用
- 掌握Struts1:Java MVC轻量级框架详解
- 20个必备CSS代码段提升Web开发效率
- CSS样式大全:字体、文本、列表样式详解
- Proteus元件库大全:从基础到高级组件
- 74HC08芯片:高速CMOS四输入与门详细资料
- C#获取当前路径的多种方法详解
- 修复MySQL乱码问题:设置字符集为GB2312
- C语言的诞生与演进:从汇编到系统编程的革命
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)