Microsoft Word - Can use the Chinese Remainder Theorem calculate ....doc

Size: px

Start display at page:

Download "Microsoft Word - Can use the Chinese Remainder Theorem calculate ....doc"

篡庞
5 years ago
Views:

1 Can use the Chinese Remainder Theorem to calculate the positive integers of The Euler phi-function and the results of even Goldbach's Conjecture Tong Xin-Ping Keywords calculate Euler's phi-function positive integer even Goldbach's Conjecture result Abstract This paper points out, when the prime numbers p i and p satisfy the p 1,p 2,,p i,, p r < N <p r+1 ;(p r +1)<p<N-p r -1 1 If N p (mod p i ), then p is not answer of the even Goldbach's conjecture 2 If i = 1 ~ r, N / p (mod p i ), then p and (N-p) is a group answer of the even Goldbach's conjecture 3 For w r = p 1 p 2 p r, can use the Chinese Remainder Theorem to calculate every positive integer of The Euler phi-function φ(wr) 4 For N = p i + (N-p i ) = p + (N-p), can use The Chinese Remainder Theorem to calculate results of p of the even Goldbach's conjecture Even N Primes p i and p satisfy the p 1,p 2,,p i,,p r < N <p r+1 (p r +1)<p<N-p r -1, N=p i +(N-p i )=p+(n-p) This paper points out: 1 If N p (mod p i ), then p is not answer of the even Goldbach's conjecture (the abbreviation "1 +1"); 2 If i = 1 ~ r, and N / p (mod p i ), then p and (N-p) is a group answer of "1 +1" ; 3 For w r = p 1 p 2 p r, can use The Chinese Remainder Theorem to calculate every positive integer of the Euler phi-function φ(w r ),4 For N = p i + (N-p i ) = p + (N-p), can use the Chinese Remainder Theorem to calculate results of p of the even Goldbach's conjecture 1 Noun, Terminology, Symbols, Lemma N Even number p i, p r, p r+1 Prime 2 p i p r < N <p r+1 i =1,2,,r r=π( N ) p Primes lying in the closed interval [p r +1, N-p r -1] Because (p r +1)<p<N-p r -1,we have (N-p)>p r N(p i ) The remainder obtained when N is divided by p i N = N(p i )+ n p i, 0 N(p i ) (p i -1) p(p i ) The remainder obtained when p is divided by p i p = p(p i )+ n p i, 0 p(p i ) (p i -1) We have N = p i + (N-p i ) = p + (N-p) When N = 98, 126, 128,, the (N-p i ) are the composite number Thus, "1 +1" is to prove that (N-p) in there must be a prime w r Factorial prime, w r =p 1 p 2 p r φ (w r ) The Euler phi-function φ (w r ) is defined to be the number of positive integers not exceeding w r that are relatively prime to w r The φ(w r ) = (p 1-1) (p 2-1) (p r -1) φ (w r ) They are positive integer in the φ(w r ) Lemma 1 [1] Positive integer a greater than 1 is a prime if and only if it is not divisible by any prime not exceeding a Lemma 2 (The Chinese Remainder Theorem ) let m 1,m 2,,m r be pairwise relatively prime positive integers, Then the system of congruence (1) has a unique solution modulo M=m 1 m 2 m r (1) x a 1 (mod m 1 ) x a 2 (mod m 2 ) 1

2 x a r (mod m r ) 2 Can determine p,(n-p) is answer of "1 +1" Theorem 1 If N p (mod p i ), then p is not "1 +1" answer of N Prove That N p (mod p i ), p i (N-p), (N-p) = k p i Pointed out earlier, (N-p)>p r, We can see k>1, The (N-p) is a composite number The p is not "1 +1" answer Theorem 1 is proved Theorem 2 If i=1~r,n / p(mod pi), then p and (N-p) is the "1 +1" answer of N Prove If i = 1~r, and N / p (mod p i ), All the prime numbers p 1,p 2,,p i,,p r are indivisible (N-p) According to Lemma 1, (N-p)<N, then (N-p) is a prime number, The p and (N-p) is the "1 +1" a set of answers Theorem 2 is proved 3 Can use The Chinese Remainder Theorem to calculate every positive integer of the Euler phi-function φ(w r ) In the formula (1), if i = 1,2,, r m i =p i =p 1,p 2,,p i,,p r a 1 =1; a 2 =1,(p2-1); a 3 =1, 2,,(p 3-1); ; a i =1,2,,(p i -1); ; a r =1,2,,(p r -1)We can obtain (2) Theorem 3 The number of solution of (2) is the product of (p 1-1),(p 2-1),,(p r -1) The result of (2) is defined to be the number of positive integers not exceeding w r that are relatively prime to w r The number of solution of (2) is φ(w r )=(p 1-1)(p 2-1) (p r -1) (2) x 1 (mod p 1 ) x 1(mod p 2 ),x (p 2-1) (mod p 2 ) x 1(mod p 3 ),x 2(mod p 3 ),x 3(mod p 3 ),x (p 3-1) (mod p 3 ) x 1(mod p 4 ),x 2(mod p 4 ),x 3(mod p 4 ),x 4(mod p 4 ),x 5(mod p 4 ),x (p 4-1)(mod p 4 ) x 1(mod p i ),x 2(mod p i ),x 3(mod p i ),,x (p i -1) (mod p i ) x 1(mod p r ),x 2(mod p r ),x 3(mod p r ),,x (p r -1) (mod p r ) Proof The each row of (2), there has (p i -1) congruence For example: The first row has (p 1-1) congruence; the second row has (p 2-1) congruence; ; the last row has (p r -1) congruence The product of (p 1-1) (p 2-1) (p r -1) is number of the system congruence of (2) The result of (2) is defined to be the number of positive integers not exceeding w r that are relatively prime to w r The number of solution of (2) is φ(w r )=(p 1-1)(p 2-1) (p r -1) Theorem 3 is proved When 1<x<N, the x is a prime By Theorem 3 and Lemma 1, we can calculate the primes But the efficiency is not high 4 Can use Chinese Remainder Theorem to calculate N=p+(N-p)in the "1 +1" for each answer 2

3 In the formula (2), if i = 1,2,, r p i =p 1,p 2,,p i,,p r and 1 when N(p i )=0, b i =a i =1, 2,,(p i -1); 2 when N(p i ) 0, b i =a i N(p i ) We can obtain (3) Theorem 4 If the x is a result of (3), and (p r +1)<x<(N- p r -1), then the x is a result of "1 +1" (3) x b 1 (mod p 1 ) x b 2 (mod p 2 ) x b i (mod p i ) x b r (mod p r ) (4) v= Π (p-2) Π (p-1)= Π (p-2) p-1 (Has been omitted p p-2 1-1=1 ) (p,n)=1 (p,n)=p p N 3 p N 2 p N 3 p N 3 p N Proof 1 When the (p i,n)=p i, N(p i )=0,b i =a i =1,2,,(p i -1) This row has (p i -1) congruence; 2 When the (p i,n)=1, N(p i ) 0, b i =a i N(p i ) This row has (p i -2) congruence Some (p i -1) multiplied some (p i -2) is number v of the system congruence of (3) (See (4)) The x of (3)can not be divisible by p 1 ~p r, according to Lemma 1, when x<n, the x is a prime And because i=1~r, b i N(p i ),the (N-x) can not be divisible by p1~pr, according to Lemma 1, when (N-x)<N, the (N-x) is a prime number, it can be sure, the x is a result of "1 +1" Theorem 4 is proved By Theorem 4, we can calculate the result of even Goldbach's conjecture But the efficiency is not high 5 Discussion We can use the Chinese Remainder Theorem to calculate the positive integers of the Euler phi-function φ(w r ) and the results of even Goldbach's conjecture But the efficiency is not high The v>0, if we can prove that v's part of the result lying in the closed interval [pr +1, N-pr-1], we can prove even Goldbach's conjecture References [1] Chen Jing Run, Elementary number theory Ⅰ, Science Press, 1978, page 6 Thanks Thank Song Kai fu teacher made valuable comments on this paper Thank Zhang Yong teacher produced symbol / 用中国剩余定理计算欧拉函数中的正整数和偶数哥德巴赫猜想的答案童信平 Txp1313abc@hotmailcom 关键词计算欧拉函数正整数偶数哥德巴赫猜想答案 3

4 摘要本文指出, 当偶数 N 和素数 p i p 满足 p 1,p 2,,p i,,p r < N <p r+1 ;(p r +1)<p<N-p r -1 1 若 N p(mod p i ), 则 p 不是 N 的哥德巴赫猜想的答案 2 若 i=1~r,n / p(mod p i ), 则 p 和 (N-p) 是一组 N 的哥德巴赫猜想的答案 3 对于素数阶乘 w r =p 1 p 2 p r 的欧拉函数 φ(w r ), 可以用中国剩余定理计算出 φ(w r ) 中的与 w r 互素的每一个正整数 ;4 对于 N=p i +(N-p i )=p+(n-p), 可以用中国剩余定理计算出 p 中的每一个偶数哥德巴赫猜想的答案偶数 N 素数 p i p 满足 p 1,p 2,,p i,,p r < N <p r+1 ;(p r +1)<p<N-p r -1,N=p i +(N-p i )=p+(n-p) 本文指出 :1 若 N p(mod p i ), 则 p 不是 N 的哥德巴赫猜想 ( 简称 1+1 ) 的答案 ;2 若 i=1~r 时,N / p(mod p i ), 则 p 和 (N-p) 是一组 N 的 1+1 的答案 ;3 对于素数阶乘 w r =p 1 p 2 p r 的欧拉函数 φ(w r ), 可以用中国剩余定理 ( 孙子定理 ) 计算出 φ(w r ) 中的与 w r 互素的每一个正整数 φ (w r ) φ (w r ) 的数量 φ(w r )= (p 1-1)(p 2-1) (p r -1);4 对于 N=p i +(N-p i )=p+(n-p), 可以用中国剩余定理计算出 p 中的每一个偶数哥德巴赫猜想的答案 1 名词术语符号引理 N 偶数 (N 50 或 r 4 ) p i p r p r+1 素数 2 p i p r < N <p r+1 i =1,2,,r r=π( N ) p 闭区间 [p r +1,N- p r -1]( 以下简称闭区间 ) 内的素数因为 (p r +1)<p<N-p r -1, 必有 (N-p)>p r p 的数量是 π(n) r =π(n-p r -1)-r N(p i ) 用 p i 去除 N 所得到的余数 N= N(p i )+ n p i,0 N(p i ) (p i -1) p(p i ) 用 p i 去除 p 所得到的余数 p= p(p i )+ n p i,1 p(p i ) (p i -1) 根据以上规定,N=p i +(N-p i )=p+(n-p) 实验证明, 许多 N 的 (N-p i ) 都是合数例如,N= 等等由此可见, 1+1 就是要证明 (N-p) 中必有素数 w r 素数阶乘,w r =p 1 p 2 p r φ(w r ) 欧拉函数, 不大于 w r 且与 w r 互素的正整数的个数 φ(w r )=(p 1-1)(p 2-1) (p r -1) φ (w r ) φ(w r ) 中那些具体的正整数引理 1 [1] 如果 a 是一个大于 1 的正整数, 而所有 a 的素数都除不尽 a, 则 a 是素数引理 2 ( 中国剩余定理即孙子定理 ) 若 m 1,m 2,,m r 是两两互素的正整数, 则下列同余式组 (1) 中有小于 M=m 1 m 2 m r 的唯一的解 (1) x a 1 (mod m 1 ) x a 2 (mod m 2 ) x a r (mod m r ) 2 判断 p 和 (N-p) 是不是可以组成一组 N 的 1+1 的答案定理 1 若 N p(mod p i ), 则 p 不是 N 的 1+1 的答案证明 N p(mod p i ),p i (N-p),(N-p)=k p i 前面指出,(N-p)>p r, 可知 k>1, 即 (N-p) 是合数 p 不是 N 的 1+1 的答案证毕定理 2 若 i=1~r,n / p(mod p i ), 则 p 和 (N-p) 是一组 N 的 1+1 的答案证明 i=1~r 时,N / p(mod p i ), 即 (N-p) 不能依次被 p 1,p 2,,p i,,p r 整除, 根据引理 1,(N-p) <N 时,(N-p) 是素数,p 和 (N-p) 是一组 N 的 1+1 的答案证毕 4

5 3 可以用中国剩余定理计算得到欧拉函数 φ(wr) 中与 wr 互素的每一个正整数在上面的同余式组 (1) 中, 取 i=1,2,,r m i =p i =p 1,p 2,,p i,,p r a 1 =1; a 2 =1,(p 2-1); a 3 =1, 2,,(p 3-1); ;a i =1,2,,(p i -1); ;a r =1,2,,(p r -1) 则组成同余式组(2), 定理 3 同余式组 (2) 中计算出来的是不大于 w r 且与 w r 互素的正整数 φ (w r ) φ (w r ) 的数量 φ(w r )=(p 1-1)(p 2-1) (p r -1) (2) x 1 (mod p 1 ) x 1(mod p 2 ),x (p 2-1) (mod p 2 ) x 1(mod p 3 ),x 2(mod p 3 ),x 3(mod p 3 ),x (p 3-1) (mod p 3 ) x 1(mod p 4 ),x 2(mod p 4 ),x 3(mod p 4 ),x 4(mod p 4 ),x 5(mod p 4 ),x (p 4-1)(mod p 4 ) x 1(mod p i ),x 2(mod p i ),x 3(mod p i ),,x (p i -1) (mod p i ) x 1(mod p r ),x 2(mod p r ),x 3(mod p r ),,x (p r -1) (mod p r ) 证明根据 a i 的变化, 式 (2) 的每一行中有 (p i -1) 个同余式, 即 : 第一行中有 (p 1-1) 个同余式 ; 第二行中有 (p 2-1) 个同余式 ; ; 第 i 行中有 (p i -1) 个同余式 ; ; 最后一行有 (p r -1) 个同余式 i=1~r 时, 依次在公式 (2) 的每一行中取一个同余式, 组成彼此之间至少有一个同余式不相同的同余式组时, 这些同余式组的数量将是 (p 1-1) (p 2-1) (p r -1) 的乘积根据引理 2, 这里的每一个同余式组都有小于 wr 的唯一的解, 故解的数量就是 φ(wr)=(p 1-1)(p 2-1) (p r -1) 这里的每一个答案皆不能依次被 p 1 p 2 p r 整除故这些解与 w r 互素证毕用同余式组 (2) 计算出来的 φ (w r ) 中的正整数包括 :1 数 1;2 大于 (p r +1) 而小于 N 的素数 ;3 大于 N 而小于 w r 的素数和不包含素因子 p i 的合数 ( 其中, 大于 p 2 r+1 的素数或合数需要用其它方法判别 ) 因为 2 中的正整数可以直接用引理 1 来判断是不是素数, 所以, 从理论上讲, 式 (2) 可以用来计算素数, 但效率不高, 因为 w r 越大, 计算出 2 中的素数的可能性越小 4 可以用中国剩余定理计算出 N=p+(N-p)= 1+1 的 p 的每一个答案在上面的同余式组 (2) 中, 取 i=1,2,,r p i =p 1,p 2,,p i,,p r b i 的取值取决于 :1 当 N(p i )=0 时, 取 b i =a i =1,2,,(p i -1) 2 当 N(p i ) 0 时, 取 b i =a i N(p i ) 则组成同余式组(3), 定理 4 在同余式组 (3) 中,x 的解的数量是 v ( 见公式 (4) ) 当 (p r +1)<x<(N- p r -1) 时,x 是 N 的 1+1 的答案 (3) x b 1 (mod p 1 ) x b 2 (mod p 2 ) x b i (mod p i ) x b r (mod p r ) (4) v = Π (p-2) Π (p-1)= Π (p-2) p-1 ( 已省略 p p-2 1-1=1 ) 5

6 (p,n)=1 (p,n)=p p N 3 p N 2 p N 3 p N 3 p N 证明 1 当 (p i,n)=p i 时,N(p i )=0,b i =a i 中未出现 0, 不必去掉任何数值, 这一行是 (p i -1) 个同余式 ; 2 当 (p i,n)=1 时,N(p i ) 0,b i =a i 中去掉一个 N(p i ) 之值后, 这一行还有 (p i -2) 个同余式 i=1~r 时, 任取 b i 的一个数值, 组成彼此之间至少有一个元素不相同的同余式组时, 这些同余式组的数量 v 将是若干个 (p i -2) 与若干个 (p i -1) 相乘如公式 (4) 这些 x 不能被 p 1 ~p r 整除, 根据引理 1,x<N 时,x 是素数又因为 i=1~r 时,b i N(p i ),(N-x) 不能被 p 1 ~p r 整除, 根据引理 1,(N-x)<N 时,(N-x) 是素数, 故可以肯定,x 是 N 的 1+1 的答案证毕定理 4 实际上是对 φ (w r ) 中的正整数进行筛选, 筛去的是 φ (w r ) N(mod p i ) 的正整数 ( 简称同余的 φ (w r ) ) 留下的是 φ (w r ) / N(mod p i ) 的正整数 ( 简称不同余的 φ (w r ) ) 不同余的 φ (w r ) 中的正整数包括 :1 数 1 或没有数 1;2 闭区间内的 N 的 1+1 的答案 ;3 大于 (N-p r -1) 而小于 w r 的素数及不包含素因子 p i 的合数 ( 这些素数或合数需要用其它方法判别 ) 因为 2 可以直接用 (N-p r -1) 判断计算的结果是不是 N 的 1+1 的答案, 所以, 从理论上讲, 定理 4 可以用来计算闭区间内 N 的 1+1 的每一个答案同前面一样, 用这种方法求解 1+1 答案的效率不高 5 讨论偶数哥德巴赫猜想的内容叙述起来非常简单, 学过素数的小学生也可以理解本文介绍了中小学生可以进一步理解乃至掌握的偶数哥德巴赫猜想的答案的判断方法和计算方法 v>0, 如果能证明 v 中的部分答案必定分布于闭区间 [p r +1,N- p r -1] 之内, 就可以证明偶数哥德巴赫猜想成立参考文献 [1] 陈景润, 初等数论, 科学出版社,1978 年,6 页致谢感谢湖北宋开福老师对本文提出了宝贵意见感谢浙江张勇老师制作了不同余的符号 /

Stochastic Processes (XI) Hanjun Zhang School of Mathematics and Computational Science, Xiangtan University 508 YiFu Lou talk 06/

Stochastic Processes (XI) Hanjun Zhang School of Mathematics and Computational Science, Xiangtan University hjzhang001@gmail.com 508 YiFu Lou talk 06/04/2010 - Page 1 Outline 508 YiFu Lou talk 06/04/2010