数论吧 关注:14,132贴子:81,221
  • 13回复贴,共1

一个著名的定理

只看楼主收藏回复

西尔维斯特定理:m≥n,则m+1,m+2,...,m+n中必有一个数有大于n的素因子
求助大佬们,这个怎么证


IP属地:天津来自Android客户端1楼2022-06-25 17:56回复
    没有查到初等证明的过程,我自己也想不出来…,如果根据素数定理,可以这样说明
    根据勒让德公式 νp(n!) = ∑[n/p^i],νp[∏(m+i)]=νp[(m+n)!]-νp[m!] = ∑[(m+n)/p^i] - [m/p^i]
    对任何i,[(m+n)/p^i]- [m/p^i]- [n/p^i]≤1
    而当i≥[lg(m+n)/lgp]时[(m+n)/p^i] = 0
    所以νp(∏(m+i))≤[lg(m+n)/lgp] + νp(n!)
    若∏(m+i)仅含n! 的素因子,则∏(m+i)=∏p(k)^νp≤n! ∏p(k)^[lg(m+n)/lgp(k)]= n! (m+n)^π(n),π(n)为1~n中素数的个数
    则C(m+n, n)= ∏(m+i)/n! ≤ (m+n)^π(n)
    只要证明m≥n时C(m+n, n)>(m+n)^π(n)恒成立,就证明∏(m+i)一定含一个大于n的素因子
    若m=m'时C(m'+n, n)>(m'+n)^π(n)成立,只要证明m≥m'时(m+n+1)/(m+1)>[(m+n+1)/(m+n)]^π(n),就可以对同一个n和任何m≥m'证明命题成立
    取对数即 π(n)×ln(m+n)>[π(n)-1]×ln(m+n+1)+ln(m+1)
    由于lnx上凸且递增,只要
    π(n)×(m+n)>[π(n)-1]×(m+n+1)+(m+1)
    成立,前一个式子就成立,化简即n>π(n),n为正整数时恒成立
    所以只要证明,C(2n, n)>(2n)^π(n)对任何正整数n成立,或者找到某个N,证明n≥N时这个式子恒成立,对每一个n<N,再分别找到对应最小的m=M(n)使C(M(n)+n, n)>(M(n)+n)^π(n)成立,最后对每一对(m, n)其中m<M(n), n<N验证原定理内容成立,就可以
    m=M(n)是总能找到的,因为C(x+n, n)是关于x的n次正系数多项式,(x+n)^π(n)是关于x的π(n)次正系数多项式,π(n)<n,则x→∞时前者远大于后者的


    IP属地:北京来自Android客户端2楼2023-12-21 13:40
    收起回复
      则只要找到N使n≥N时,C(2n, n)>(2n)^π(n)恒成立,到这里,就只想到素数定理来说明了
      对C(2n, n)>(2n)^π(n)取对数即
      π(n)< (∑lni - 2∑lnj)/(ln n + ln2)
      其中i=1~2n,j=1~n
      由定积分∫lnxdx和∑lni的关系可以得到
      k*lnk-k+1<∑lni<(k+1)*lnk-k
      则∑lni > (2n)*ln(2n)-2n +1
      ∑lnj < (n+1)*ln n -n
      所以只要
      π(n)< (2n ln2- 2ln n+ 1)/(ln n+ln 2)
      存在某个N使n>N成立
      右边的式子和素数定理π(n)~n/ln n右边是同阶无穷大,只多了大于1的系数2ln2,总存在N使n≥N时π(n)小于右边的式子,相当于说明西尔维斯特定理的反例(m, n)只有有限个,再用具体步骤确定N,依次检验说明定理对任何正整数m, n成立


      IP属地:北京来自Android客户端3楼2023-12-21 13:49
      收起回复
        这个是猜想吧


        IP属地:上海4楼2024-01-03 18:48
        回复
          2L链接里面的证明过程改动了一点,是这样子的:
          先证明引理
          引理1: 设p为素数,用 ν_p(m)表示m的分解中含素因子p的次数
          则ν_p(C(n, k))≤[ln n / ln k]
          引理2: 用f(n)表示1, 2, …, n的最小公倍数,则f(n)< 4ⁿ
          ----------------
          引理1用勒让德公式ν_p(n!)=∑[n/p^i], i=1~+∞就可以证明
          引理2是证明中的关键,证明过程在这里~求助一个数论问题
          它是这个帖子里引理的加强 一个小题,谢谢大佬帮忙
          -------------------
          再证明2个推论
          推论1: 若n≥2k, C(n, k)没有大于k的素因子, 则C(n, k)≤n^π(k), π(k)表示不超过k的素数个数
          证明: 对C(n, k)的某个素因子p, 设ν_p(C(n, k))=α , 则 α≤[lnn/lnp], p^α≤n
          因为p≤k, 不同的素因子最多有π(k)个, 所以C(n, k)=∏p^α ≤n^π(k)
          ----------------
          推论2: 如果n≥6, n≥2k, C(n, k)没有大于k的素因子,那么
          若n^(2/3)<k<n/3, 则C(n, k)< 4^(k+[[n^(1/2)]])
          若n^(2/3)< n/3≤k≤n/2, 则C(n, k)< 4^([[n/3]]+[[n^(1/2)]])
          用[[x]]表示向上取整(打不出那个符号), 也就是不小于x的最小正整数
          证明: 先证明若C(n, k)的素因子p≤k, 则p≤n/3
          n≥6时若p=2是素因子, 则p≤n/3
          对C(n, k)的奇素因子p
          因为p≤k, n! /k! (n-k)! 中分母含p 的次数至少为2, 所以分子含p的次数至少为3, 则n≥3p
          再分类讨论证明,对任意实数x≥3/2, 都有
          [x]≤[2/3 x]+[1/2 x]
          再证明对任何正整数, ν_p(f(m))= [ln m/ln p]
          最后,当n^(2/3)<k<n/3时
          若ln n/ln p≥3/2, 则ν_p(C(n, k))≤[ln n/ln p]≤[2/3 ln n/ln p]+[1/2 ln n/ln p]≤[ln k/ln p]+[1/2 ln n/ln p]
          若ln n/ln p< 3/2 且p≤k, 由于[ln n/ln p]≤1, [ln k/ln p]≥1, 所以也有 ν_p(C(n, k))≤[ln k/ln p]+[1/2 ln n/ln p]
          所以C(n, k) | f(k) * f( [[n^(1/2)]] )
          由引理2, C(n, k)≤f(k)*f([[n^(1/2)]])< 4^(k+[[n^(1/2)]])
          同理,当n^(2/3)< n/3≤k≤n/2 时,
          对C(n, k)的素因子p按ln n/ln p≥3/2 和ln n/ln p<3/2 且 p≤n/3 分类, 可以证明
          C(n, k) | f( [[n/3]] )* f( [[n^(1/2)]] )
          由引理2, C(n, k)< 4^( [[n/3]]+ [[n^(1/2)]] )


          IP属地:北京来自Android客户端5楼2024-01-19 12:55
          回复
            还要用到对C(n, k)的放缩,会标注
            若k>1, n>k, 则
            ①C(n, k) > (n/k)^k
            ②C(2k, k) > 4^k / 2k
            ③C([[5k/2]], k) > 5^k / 2k
            ④C(4k, k) > 8^k / 2k
            ---------------
            ①证明:
            C(n, k)= n*(n-1)*…*(n-k+1) / k*(k-1)*…*1
            = ∏(n-i) / ∏(k-i) = ∏(n-i)/(k-i), i=0~k-1
            对任意1≤i≤k-1, k(n-i) > n(k-i)
            所以(n-i)/(k-i) > n/k
            所以C(n, k)= ∏(n-i)/(k-i) > (n/k)^k
            --------------
            ②证明:
            当k=2时, C(4, 2)=6>16/4= 4² / 2*2
            由于C(2k+2, k+1)= 2(2k+1)/(k+1)* C(2k, k)
            > 4k/(k+1) * C(2k, k)
            所以若C(2k, k)>4^k / 2k,
            则C(2k+2, k+1)> 4k/(k+1) *(4^k / 2k) = 4^(k+1)/ 2(k+1)
            由数学归纳法C(2k, k)>4^k / 2k 对任意k≥2都成立
            --------------
            ③证明:
            用a表示[[5k/2]], 则a≥5k/2, a/2k≥5/4
            则C(a, k)=C(2k, k)* [ a*(a-1)*…*(a-k+1) / 2k*(2k-1)*…*(k+1)]
            由于1≤i≤k-1时(a-i)/(2k-i) > a/2k , 所以中括号里> (a/2k)^k ≥ (5/4)^k
            所以C(a, k)> C(2k, k)*(5/4)^k
            > (4^k / 2k)* (5/4)^k = 5^k / 2k
            --------------
            ④证明 :
            C(4k, k)=C(2k, k)*[ (4k)*(4k-1)*…*(3k+1) / (2k)*(2k-1)*…*(k+1) ]
            当1≤i≤k-1时, (4k-i)/(2k-i) > 2
            所以中括号里 > 2^k
            C(4k, k)> C(2k, k)*2^k > (4^k / 2k) * 2^k = 8^k / 2k


            IP属地:北京来自Android客户端6楼2024-01-19 13:34
            回复
              最后当n≥2500时, 分段证明C(n, k)如果没有大于k的素因子,会产生矛盾
              由于8< 37< n^(1/2) < n^(2/3) < n/4 < n/3 < 2n/5 < n/2
              ----------------
              当k=2, 3, 4, 5, 6, 7时,
              由C(n, k)≤n^π(k), 可以依次分析
              若k=2, C(n, 2)≤n
              若k=3, 4, C(n, 3)≤n², C(n, 4)≤n²
              若k=5, 6, C(n, 5)≤n³, C(n, 6)≤n³
              若k=7, C(n, 7)≤n⁴
              n≥2500时以上6个式子都不可能成立, 都会矛盾
              ----------------
              当8≤k≤n^(1/2)时,
              由于1, 9和大于2的偶数都不是素数, π(k)≤k/2, C(n, k)≤n^π(k)≤n^(k/2)
              而C(n, k)>(n/k)^k (①)
              所以n/k < n^(1/2), k > n^(1/2),矛盾
              -------------------
              当37< k≤n^(2/3)时
              由于t≥1时, 3t+1到3t+3最多只有1个素数, 1到3中2, 3是素数, 而25,26,27和34, 35, 36全都是合数, 所以π(k)≤[[(k-3)/3]]+2-2≤k/3
              C(n, k)≤n^π(k)≤n^(k/3)
              又因为C(n, k)>(n/k)^k (①)
              所以n/k < n^(1/3), k>n^(2/3), 矛盾
              -------------
              当n^(2/3)<k≤n/4时
              C(n, k)< 4^(k+[[n^(1/2)]])≤ 4^(k+k^(3/4)+1)
              而C(n, k)≥C(4k, k)> 8^k / 2k (④)
              所以 8^k < 2k * 4^(k+k^(3/4)+1)
              n≥2500时k≥185, k^(3/4)≤k/3.688
              右边≤8k * [4^(1+1/3.688)]^k < 8k * 6^k
              则 (4/3)^k < 8k
              但k≥18时(4/3)^k > 8k, 矛盾
              -------------
              当n/4< k≤2/5n时
              C(n, k)< 4^(k+[[n^(1/2)]])≤ 4^(k+2k^(1/2)+1)
              而C(n, k)≥C([[5k/2]], k)> 5^k / 2k (③)
              所以 5^k < 2k * 4^(k+2k^(1/2)+1)
              n≥2500时k≥625, 2k^(1/2)≤2k/25
              右边≤8k * [4^(1+2/25)]^k < 8k * (9/2)^k
              则 (10/9)^k < 8k
              但k≥59时(10/9)^k > 8k,矛盾
              -------------
              当2/5n< k≤n/2时
              C(n, k)< 4^([[n/3]]+[[n^(1/2)]])≤4^( 5k/6+(5k/2)^(1/2)+2 )
              而C(n, k)≥C(2k, k)> 4^k / 2k (②)
              所以 4^k < 2k * 4^(5k/6+(5k/2)^(1/2)+2)
              n≥2500时k>1000, (5k/2)^(1/2)< k/20
              右边≤32k * [4^(5/6+1/20)]^k < 32k * (7/2)^k
              则 (8/7)^k < 32k
              但k≥57时(8/7)^k > 32k, 矛盾


              IP属地:北京来自Android客户端7楼2024-01-19 13:37
              回复
                对n<2500只要一一检验,就可以证明西尔维斯特定理对任意n≥2k都成立
                这里的2500是我自己取的比较大的数字,原证明既没有凑也没有猜,是从所分的每种情况,分别反过来定出某个N,当n大于N时一定会产生矛盾,然后对这些N中最大值以内的数字n 一一检验,是真正的初等证明


                IP属地:北京来自Android客户端8楼2024-01-19 13:42
                回复