4-5 数论基础.

Presentation on theme: "4-5 数论基础."— Presentation transcript:

1 4-5 数论基础

2 Problem TJ2-13 Prove that the two principles of mathematical induction are equivalent.
𝑺 𝒏 𝟎 ,∀𝒌≥ 𝒏 𝟎 𝑺 𝒌 →𝑺 𝒌+𝟏 →∀𝒏≥ 𝒏 𝟎 𝑺 𝒏 等价？ B 𝑺 𝒏 𝟎 ,∀𝒌≥ 𝒏 𝟎 𝑺 𝒏 𝟎 …𝑺 𝒌 →𝑺 𝒌+𝟏 →∀𝒏≥ 𝒏 𝟎 𝑺 𝒏 A<=>B

3 Problem TJ2-13 A=>B 能被A（WMI）所证明的S(n)，一定也能被B（SMI）所证明 显然，因为
∀𝒌≥ 𝒏 𝟎 𝑺 𝒌 →𝑺 𝒌+𝟏 ⇒∀𝒌≥ 𝒏 𝟎 𝑺 𝒏 𝟎 …𝑺 𝒌 →𝑺 𝒌+𝟏 理由：𝑨→𝑪⇒𝑨∧𝑩→𝑪

4 Problem TJ2-13 A<=B 能被B（SMI）所证明的S(n)，一定也能被A（WMI）所证明 关键步骤：
令𝑇 𝑛 ≐∀𝑘, 𝑛 0 ≤𝑘≤𝑛, 𝑆 k 利用WMI证明𝑇(𝑛): Base：𝑇 𝑛 0 =𝑆 𝑛 0 ，显然成立 H：假设对于𝑘≥ 𝑛 0 , 𝑇(𝑘)成立 I： ∵𝑇(𝑘)成立，即𝑆 𝑛 0 ,𝑆 𝑛 1 ,…,𝑆 𝑘 成立， ∴由SMI可知𝑆 𝑘+1 成立 ∴ 𝑇(𝑘+1)成立 ∴ ∀n≥ 𝑛 0 , 𝑇(𝑛)成立 ∴ ∀n≥ 𝑛 0 , 𝑆 𝑛 成立

5 Problem TJ 2-29: Prove that there are an infinite number of primes of the form 6n+5. TJ 2-30: Prove that there are an infinite number of primes of the form 4n-1. 基本思路一致 假设特定形式的质数个数有限，构造一个新的数（具有新的特定形式的 质因子），推出矛盾 例：(4n-1)/(4n+3) 假设形如4n-1的质数个数有限，分别为 𝑝 1 , 𝑝 2 ,…, 𝑝 𝑛 令合数𝑁= 4𝑝 1 𝑝 2 … 𝑝 𝑛 −1，显然N不能被 𝑝 1 , 𝑝 2 ,…, 𝑝 𝑛 整除，所以必然存 在一个质数p，使得𝑝|𝑁 𝑝≠2⇒𝑝≥3 任意𝑝≥3必然形如：4𝑛+1或4𝑛−1 任意形如4𝑛+1的数相乘所得结果仍然形如4𝑛+1，而N形如4𝑛−1，所以N必然包含一个不 属于 𝑝 1 , 𝑝 2 ,…, 𝑝 𝑛 的形如4𝑛−1的质因子。（矛盾） 假设不成立

6 Problem TJ 2-29: Prove that there are an infinite number of primes of the form 6n+1.

7 Problem TJ 2-29: Prove that there are an infinite number of primes of the form 6n+1.

8 The Circle Group The complex numbers satisfying the equation 𝑧 𝑛 = 1 are called the nth roots of unity. A generator for the group of the nth roots of unity is called a primitive nth root of unity. 𝐠𝐜𝐝 𝒌,𝒏 =𝟏

9 Cyclotomic polynomial(分圆多项式)
primitive nth root of unity 𝑥 4 −1= 𝑥−1 𝑥−𝑖 𝑥+1 (𝑥+𝑖) n=4

10 Cyclotomic polynomial(分圆多项式)

11 Let k be a positive integer
Let k be a positive integer. There are infinitely many primes congruent to 1 mod k 即对于给定的k>0,kn+1形式的质数存在无穷个 基本思路 假设存在有限个形如kn+1的质数，分别为 𝑝 1 , 𝑝 2 ,…, 𝑝 𝑚 令𝑁= 𝑝 1 𝑝 2 … 𝑝 𝑚 假设𝐴= Φ 𝑘 (𝑁)，且𝑝为A的一个质因子，显然𝑝∉ 𝑝 1 , 𝑝 2 ,…, 𝑝 𝑚 ， 𝑝∤𝑁，𝑝|𝐴 又∵ d|𝑘 Φ 𝑘 (𝑁) = 𝑁 𝑘 −1 ∴𝐴为 d|𝑘 Φ 𝑘 (𝑁) = 𝑁 𝑘 −1的因子 ∴𝑝| 𝑁 𝑘 −1 ∴ 𝑁 𝑘 ≡1 𝑚𝑜𝑑 𝑝 又∵𝒑是质数，且𝑝∤𝑁，由费马小定理可得 𝑁 𝑝−1 ≡1 𝑚𝑜𝑑 𝑝 ∴ 𝑁 𝑘 ≡𝑁 p−1 𝑚𝑜𝑑 𝑝, 而k是使得 𝑵 𝒌 ≡𝟏 𝒎𝒐𝒅 𝒑成立的最小值 即𝑝=𝑘𝑗+1 矛盾

12 k是使得 𝑁 𝑘 ≡1 𝑚𝑜𝑑 𝑝成立的最小值 为什么不会是： 𝒙 𝒏 −𝟏 ≡ 𝒙−𝒂 𝒋 𝒇 𝒙 𝒎𝒐𝒅 𝒑, 𝐣≥𝟑

13 Dirichlet‘s (prime number) theorem
For any two positive coprime integers a and d, there are infinitely many primes of the form a + nd, where n is a non-negative integer. In other words, there are infinitely many primes that are congruent to a modulo d. The theorem extends Euclid's theorem that there are infinitely many prime numbers. 

14 你能想到最naïve的方法？ 暴力？ 从b~ a −1逐个尝试是否是a的因子

15 从b~ a −1逐个尝试是否是a的因子 总共需要多少次尝试？ 𝑎≤ 10 12 ,𝑇≤4000 a −b次Θ( 𝑁 1 2 )
每次除法开销M 整体开销 𝑀∗Θ( 𝑁 ) ∗𝑇 a的二进制位数K= lg 𝑁 除法实现？ 𝑀=Θ 𝐾 lg 𝐾 = Θ lg 𝑁 lg lg 𝑁 𝑀=Θ 𝐾 2 =Θ( lg 2 𝑁 ) 𝑎≤ ,𝑇≤4000 a −b次Θ( 𝑁 )≈ 10 6 每次除法开销M 整体开销 𝑀∗Θ( 𝑁 ) ∗𝑇 a的二进制位数K= lg 𝑁 除法实现？ 𝑀=Θ 𝐾 lg 𝐾 = Θ lg 𝑁 lg lg 𝑁 ≈ 10 2 𝑀=Θ 𝐾 2 =Θ( lg 2 𝑁 ) ≈ 10 3

16 巧用算数基本定理 先素数打表一下，求出1~ 10 6 中所有素数 然后再运用算术基本定理中的(1)
即可求出正因数的个数，然后再除以2，便是对数，最后再暴力求解出[1，b]中 a 的正因数个数，相减便是答案！

17 巧用算数基本定理 最坏情况下开销多少？ 先素数打表一下，求出1~ 10 6 中所有素数 然后再运用算术基本定理中的(1)
即可求出正因数的个数，然后再除以2，便是对数，最后再暴力求解出[1，b]中 a 的正因数个数，相减便是答案！ 最坏情况下开销多少？