4-5 数论基础

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

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

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 , 𝑆 𝑛 成立

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的质因子。（矛盾） 假设不成立

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

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

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. 𝐠𝐜𝐝 𝒌,𝒏 =𝟏

Cyclotomic polynomial(分圆多项式) primitive nth root of unity 𝑥 4 −1= 𝑥−1 𝑥−𝑖 𝑥+1 (𝑥+𝑖) n=4 https://en.wikipedia.org/wiki/Cyclotomic_polynomial

Cyclotomic polynomial(分圆多项式) https://en.wikipedia.org/wiki/Cyclotomic_polynomial

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 矛盾

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

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.  https://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arithmetic_progressions#CITEREFNeukirch1999

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

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

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

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