精华内容
下载资源
问答
  • 数学家们把问题复杂化了(用连续的思想去解决离散的问题难度更大),用解析数论、代数数论、实分析和复分析不能解决这些问题时,用初等方法能解决吗? 受欧几里得用反证法简单而优美地证明素数无限性的启发,考虑 ...

    哥德巴赫猜想的初等证明

    凡事应尽可能简单,但不能过于简单——A.爱因斯坦
    我们的祖先在地球上生活了几百万年后才知道地球的存在;然而真相是简单的。数学家们把问题复杂化了(用连续的思想去解决离散的问题难度更大),用解析数论、代数数论、实分析和复分析不能解决这些问题时,用初等方法能解决吗?
    受欧几里得用反证法简单而优美地证明素数无限性的启发,考虑 2n=p+(2np)2n=p+(2n-p) ,若设定 ppnn 前奇素数,那么只需证明 2np2n-p 中一定有素数即可证明哥德巴赫猜想。
    2n2425262728292102112np333,53,53,5,73,5,73,5,73,5,73,5,7,...p<n2np579,711,913,11,915,13,1117,15,1319,17,152np\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline 2n&2\cdot 4 & 2\cdot 5& 2\cdot 6&2\cdot 7&2\cdot 8& 2\cdot 9&2\cdot 10&2\cdot11&2n \\ \hline p &3& 3&{\color{red}{} 3},5&3, {\color{red}{} 5}&3,5, {\color{red}{} 7}&{\color{red}{} 3},5,7&3,{\color{red}{} 5},7&3,5,{\color{red}{} 7}&3,5,7,...p<n\\ \hline2n-p&5&7&{\color{red}{} 9},7&11,{\color{red}{} 9}&13,11,{\color{red}{} 9}&{\color{red}{} 15},13,11&17,{\color{red}{} 15},13&19,17,{\color{red}{} 15}&2n-p中必有素数\\ \hline \end{array}

    定理1:设ppnn 前奇素数的集合,则 2np,2n+p2n-p,2n+p 中皆有素数

    引理:(中国剩余定理)设m1,m2,m3,...mrm_{1},m_{2},m_{3},...m_{r}是两两互素的,则同余方程组
    xa1(modm1),x\equiv a_{1}(modm_{1}),
    xa2(modm2),x\equiv a_{2}(modm_{2}),
    xa3(modm3),x\equiv a_{3}(modm_{3}),
    ............
    xar(modmr).x\equiv a_{r}(modm_{r}).
    有模M=m1m2m3mrM=m_{1}m_{2}m_{3} \cdot\cdot\cdot m_{r} 的唯一解.
    这里不是要证明它,而是要引入两种特殊情况的解:
    (1)ai=mi(1)a_{i}=m_{i} 时,有唯一解x0(modM): x\equiv0(modM) ,最小正解 x=M(0)x=M ;(非0)
    (2)ai=mk,ik(2)a_{i}=m_{k},i\ne k时,包括部分ai=mia_{i}=m_{i}也有唯一解:xb(modM),0<b<M,: x\equiv b(modM),0<b<M ,最小正解 x=b+M.x=b+M .

    下面回到命题的证明:
    ppnn 前奇素数的集合, p={3,5,7,...,pi},p<n,i1p=\left\{ 3,5,7,...,p_{i} \right\},p<n,i\geq1
    n=4n=4 时,p=3;2np=5p=3; 2n-p=5 是素数;
    n=5n=5 时, p=3;2np=7p=3; 2n-p=7 是素数;
    n=6n=6 时, p={3,5};2np={9,7};7p=\left\{ 3,5\right\}; 2n-p=\left\{ 9,7 \right\}; 7 是素数;
    n=7n=7 时, p={3,5};2np={11,9};11p=\left\{ 3,5\right\}; 2n-p=\left\{ 11,9 \right\}; 11是素数;
    n=8n=8 时, p={3,5,7};2np={13,11,9};13,11p=\left\{ 3,5,7 \right\}; 2n-p=\left\{ 13,11,9 \right\}; 13,11是素数;
    后面是不是都成立呢?下面用反证法来证明:
    因为, n2>1n^{2}>1是一个合数, nn 的全部素因子皆不超过 n;n;n<2np<n2n<2n-p<n^{2}, 所以,若 2np2n-p 是一个合数,则 2np2n-p 必有一个素因子小于 nn, 即若 2np2n-p 是合数,必能被某个 pp 整除.设为 q,qp.q, q∈p.

    反证法:
    ppnn 前奇素数的集合,假设 2np={2n3,2n5,,2npi}2n-p=\left\{ 2n-3,2n-5,\cdots,2n-p_{i} \right\}全部是合数,必有 2np0(modq),qp,2n-p\equiv0(modq),q\in p, 2np0(modq)2n-p\equiv0(modq) 全部是合数,不外两种情况: p=qp=qpqp\ne q(包括部分 p=qp=q )与引理的两种特殊情况对应(若有 iip,p ,有解的方程组有 i!i! 个,即,有解的方程组把 qqpp 不动,把 iippqq 全排列):

    • p=qp=q 时:只有一组这种情况

    2n30(mod3),2n-3\equiv0\pmod 3,
    2n50(mod5),2n-5\equiv0\pmod 5,
    2n70(mod7)2n-7\equiv0\pmod 7,
    \cdots\cdots
    2npi0(modpi)2n-p_{i}\equiv0\pmod {p_{i}}
    方程组的解是 n0(mod357pi)n\equiv0(mod3\cdot5\cdot7\cdots p_{i}) ,满足 2np2n-p 全部是合数的 nn 最小正值是n=357pi,i=1n=3\cdot5\cdot7\cdots p_{i} , i=1 时就错了,因 n=3n=3 这与设定 ppnn 前奇素数 3<n3<n 矛盾.

    35=153*5=1515357111315前面不是只有3和5两个素数,还有7,11,13没有被考虑;

    所以, n=357pin=3\cdot5\cdot7\cdots p_{i} 是错误的, nn 前还有大于 pip_{i} 的素数;

    • pqp\ne q 时(包括部分 p=qp=q ):其它情况,有 i!1i!-1组(并不是 ii1i^{i}-1 组)

    用中国剩余定理解其它方程组都能得到: nb(modM),b>0,M=357pin\equiv b(modM) , b>0,M=3\cdot5\cdot7\cdots p_{i} 满足 2np2n-p 全部是合数的 nn 最小值是 n,=b+357pi,b>0,n^{,}=b+3\cdot5\cdot7\cdots p_{i} , b>0 ,(部分 q=pq=pb>0,b>0 ,因只要有 一个pqp\ne q 就有 b>0b>0 );
    n=357pi<n,=b+357pin=3\cdot5\cdot7\cdots p_{i}<n^{,}=b+3\cdot5\cdot7\cdots p_{i}
    n=357pin=3\cdot5\cdot7\cdots p_{i} 是错误的, nn 前还有大于 pip_{i} 的素数; nn 并非全部 pp 的积;
    n,=b+357pin^{,}=b+3\cdot5\cdot7\cdots p_{i} 更是错误的, n,n^{,} 前还有更多大于 pip_{i} 的素数;

    举例:
    n=6n=6时,有 2n32n-32n52n-5

    p=q:2n30(mod3),2n50(mod5),p=q:2n-3\equiv0(mod3),2n-5\equiv0(mod5), 解得n0(mod35)n\equiv0(mod3\cdot5)
    pq:2n30(mod5),2n50(mod3),p\ne q:2n-3\equiv0(mod5),2n-5\equiv0(mod3), 解得n4(mod35)n\equiv4(mod3\cdot5)

    若这两数都是合数解得 n0,4(mod15)n\equiv0,4(mod15) (最小解)不等于6.6.

    (2n30(mod3),2n50(mod3)2n-3\equiv0(mod3),2n-5\equiv0(mod3)无解; 2n30(mod5),2n50(mod5)2n-3\equiv0(mod5),2n-5\equiv0(mod5)也无解,即同模无解或是同一个方程,因为矛盾 )

    n=15n=15 是满足 2n3=272n5=252n-3=27 和 2n-5=25 都是合数的最小解,但 1515 前面还有大于 55 的素数 711137、11、13 没有被考虑;n=6n=6 时,有 2n32n52n-3 与 2n-5 ,但这两数都是合数时 n=15,30,45,...n=15,30,45,...
    n=4+15=19n=4+15=19 也满足 2n3=352n5=332n-3=35 和 2n-5=33 都是合数,但 1919 前面还有大于 55 的素数 71113177、11、13、17 没有被考虑;这两数都是合数时 n=19,34,49,...n=19,34,49,...

    综上所述:假设 2np={2n3,2n5,,2npi}2n-p=\left\{ 2n-3,2n-5,\cdot\cdot\cdot,2n-p_{i} \right\} 全部是合数, n=Mn=M 是最小解,其它解 也与事实不符:n0,b(modM),n\ne0,b(modM),n=Mn=M 是错误的,n=b+Mn=b+M 更是错误的,这个假设是错误的,它们不能全是合数。所以, ppnn 前奇素数的集合, 2np2n-p 中必有素数.
    同理ppnn 前奇素数的集合, 2n+p2n+p 中必有素数,因 n<2n+p<3n<n2.n<2n+p<3n<n^{2} .

    定理2:大于2的偶数必能表为两个素数之和

    证明
    ppnn 前奇素数的集合,对于 2n2n ,当
    n=2n=2 时, 4=2+24=2+2 ,成立;
    n=3n=3 时, 6=3+36=3+3 ,成立;
    n>pn>p 时, nn 前总有奇素数 p,np , n2n2n 前,总有 2np2n-p 是素数;(证明同定理1)
    2n=p+(2np)2n=p+(2n-p) ,所以大于2的偶数必能表为两个素数的和。

    定理3:偶数必能表为两个素数之差

    证明
    ppnn 前奇素数的集合,对于 2n2n ,当
    n=1n=1 时, 2=532=5-3 ;
    n=2n=2 时, 4=734=7-3 ;
    n=3n=3 时, 6=1156=11-5 ;都成立;
    n>pn>p 时, 2n+p2n+p 中必有素数; 证明同定理1;
    2n=(2n+p)p2n=(2n+p)-p ,所以:偶数必能表为两个素数之差。

    定理4:(伯特兰猜想) 任意正整数 n>1,nn>1 , n2n2n 之间必有一素数

    1845 年,法国数学家伯特兰猜想对于任意给定的正整数 n>1n>1 ,存在一个素数 dd ,使得 n<d<2nn<d<2n .这个猜想的第一个证明是由切比雪夫在 1852 年给出的(证明的过程较复杂).因为已经 被证明了,所以它通常被称为伯特兰公设.
    证明
    ppnn 前奇素数的集合, p={3,5,7,...,pi},p<n,i1p=\left\{ 3,5,7,...,p_{i} \right\},p<n,i\geq1
    n=2n=2 时, 2<3<42 < 3 < 4 ,命题成立;
    n=3n=3 时, 3<5<63 < 5 < 6 ,命题成立;
    n>pn>p 时,nn2n2n(n<2np<2n)(n<2n-p<2n)总有 2np2n-p 是素数;证明同定理 1;1;
    所以,当 n>1 时, n 与 2n 之间必有一素数。 伯特兰猜想得证。

    定理5:大于2的偶数两边总有一对对称素数(素数偶对称性)

    证明:

    所谓奇数哥德巴赫猜想不需证明,偶数+3+3即是奇数,自然成立。
    即:大于55的奇数都能写成三个素数之和。

    致谢:
    XXX指出原文中最小解的“错误”,后来我发现原来的论述是对的,最小解就是 n=Mn=M ,不是 n=0,b,n=0,b ,因为 n0,b(modM)n\equiv0,b(modM) 它等价于 n=(0,b)+Mk,n=(0,b)+M*k ,其中 k0k\ne0 为正整数(00不能作除数)。

    补充:
    不得不作如下说明

    nn 前若有iipp,使得(若) 2np2n-p 全部是合数的有解的方程组有i!i!个,并不是 iii^{i} 个。同模都要剔除。举例: n=12n=12的情况
    1212小的奇素数有44个,不考虑有没有解的话应当有 44=2564^{4}=256 个同余式组,以下是其中一个
    {2n3(mod7),2n5(mod3),2n7(mod11),2n11(mod3).\begin{cases} 2n\equiv3(mod7) ,\\ 2n\equiv5(mod3),\bullet\\ 2n\equiv7(mod11), \\2n\equiv11(mod3).\bullet\end{cases}
    解为 n227(mod231)n\equiv227\left( mod231 \right) ,虽然有解,其中 5112(mod3)5\equiv11\equiv2(mod3) 是同一个方程,就少了一个,不能保证四个 (2n3,2n5,2n7,2n11)(2n-3,2n-5,2n-7,2n-11) 全部是合数;将最小的 n=227+231=458n=227+231=458 代入得:
    {2n3=913=11×83,2n5=911,prime2n7=909=9×101,2n11=905=5×181.\begin{cases} 2n-3=913=11\times83 ,\\ 2n-5=911,prime\\ 2n-7=909=9\times101, \\2n-11=905=5\times181.\end{cases}
    其中 911911 是素数。
    只有两两互素才能保证全部是合数, (3,3)=31(3,3)=3\ne1
    同模要么无解,要么是同一个方程。所以都要剔除。所以(符合全部是合数的)有解的方程组只有i!个。
    n=12n=12 时,符合 2np2n-p 全部是合数的 nn 最小值 n=3×5×7×11=1155n=3\times5\times7\times11=1155 ,其它解都大于 11551155.
    :方程组 {xa1(mod  m1)xa2(mod  m2)\begin{cases}x\equiv a_{1}(\mod m_{1})\\x\equiv a_{2}(\mod m_{2})\end{cases} 有解当且仅当 (m1,m2)(a1a2),(m_{1},m_{2})|(a_{1}-a_{2}),若有解,则解模 [m1,m2][m_{1},m_{2}] 唯一。


    附:

    1. nn 是素数时, 2n2n 表为两个素数之和有奇数种表示;
      比如:
      4=22={2}14=2\cdot2=\left\{ 2 \right\}_{1}
      6=23={3}16=2\cdot3=\left\{ 3 \right\}_{1}
      10=25={3,5,7}310=2\cdot5=\left\{ 3,5,7 \right\}_{3}
      14=27={3,7,11}314=2\cdot7=\left\{ 3,7,11 \right\}_{3}
      22=211={3,5,11,17,19}522=2\cdot11=\left\{ 3,5,11,17,19 \right\}_{5}
      ={3+195+1711+1117+519+3=\begin{cases} 3+19\\5+17\\11+11\\17+5\\19+3\end{cases}
      26=213={3,7,13,19,23}526=2\cdot13=\left\{ 3,7,13,19,23 \right\}_{5}
      34=217={3,5,11,17,23,29,31}734=2\cdot17=\left\{ 3,5,11,17,23,29,31 \right\}_{7}
      38=219={7,19,31}338=2\cdot19=\left\{ 7,19,31 \right\}_{3}
      ={7+3119+1931+7=\begin{cases}7+31\\19+19\\31+7\end{cases}
      46=223={3,5,17,23,29,41,43}746=2\cdot23=\left\{ 3,5,17,23,29,41,43 \right\}_{7}
      58=229={5,11,17,29,41,47,53}758=2\cdot29=\left\{ 5,11,17,29,41,47,53 \right\}_{7}
      62=231={3,19,31,43,59}562=2\cdot31=\left\{ 3,19,31,43,59 \right\}_{5}
      74=237={3,7,13,31,37,43,61,67,71}974=2\cdot37=\left\{ 3,7,13,31,37,43,61,67,71 \right\}_{9}
      82=241={3,11,23,29,41,53,59,71,79}982=2\cdot41=\left\{ 3,11,23,29,41,53,59,71,79 \right\}_{9}
      86=243={3,7,13,19,43,67,73,79,83}986=2\cdot43=\left\{ 3,7,13,19,43,67,73,79,83 \right\}_{9}
      \cdot\cdot\cdot\cdot\cdot\cdot\cdot
    1. nn 是合数时, 2n2n 表为两个素数之和有偶数种表示;
      12=26={5,7}2={5+77+512=2\cdot6=\left\{ 5,7 \right\}_{2}=\begin{cases} 5+7\\7+5\end{cases}
      16=28={3,5,11,13}4={3+135+1111+513+316=2\cdot8=\left\{ 3,5,11,13 \right\}_{4}=\begin{cases} 3+13\\5+11\\11+5\\13+3\end{cases}
      70=235={3,11,17,19,23,41,47,53,59,67}10={3+6711+5917+5323+4729+4141+2947+2353+1759+1167+370=2\cdot35=\left\{ 3,11,17,19,23,41,47,53,59,67 \right\}_{10} =\begin{cases} 3+67\\11+59\\17+53\\23+47\\29+41\\41+29\\47+23\\53+17\\59+11\\67+3\end{cases}
      100=250={3,11,17,29,41,47,53,59,71,83,89,97}12100=2\cdot50=\left\{ 3,11,17,29,41,47,53,59,71,83,89,97 \right\}_{12}
      104=252={3,7,31,37,43,61,67,73,97,101}10104=2\cdot52=\left\{ 3,7,31,37,43,61,67,73,97,101 \right\}_{10}
      \cdot\cdot\cdot\cdot\cdot\cdot\cdot
      对任意的 n>1n>1 都有:
      nn 是合数, 2n2n 表示为两个素数之和的方法有偶数种;
      nn 是素数, 2n2n 表示为两个素数之和的方法有奇数种.

    2. 大于6的偶数,都能表为两个不同奇素数的和
      这是因为: p<n,p2npp<n, p\ne2n-p

    3. 大于1010的偶数,都能表为1+2“1+2”,即一个素数与两个素数乘积之和
      12=3+3312=3+3\cdot3
      14=5+3314=5+3\cdot3
      16=2+27=7+3316=2+2\cdot7=7+3\cdot3
      这是因为:当 2np2n-p 为合数时,它的全部素因子皆小于 nn ,因为 2np<n22n-p<n^{2}
      一定存在2np=pjapib2n-p=p_j^{a}\cdots p_i^b,那么,一定存在这样的合数,2np=pjpi2n-p=p_j\cdot p_i

    4. 小于146146的偶数有些不都能表为1+3“1+3”,即一个素数与三个素数乘积之和
      10=2+22210=2+2\cdot2\cdot2
      1212 不能表为1+31+3
      14=2+22314=2+2\cdot2\cdot3
      1616 不能表为1+31+3
      1818 不能表为1+31+3
      20=2+23320=2+2\cdot3\cdot3
      22=2+22522=2+2\cdot2\cdot5
      2424 不能表为1+31+3
      2626 不能表为1+31+3
      2828 不能表为1+31+3
      30=3+33330=3+3\cdot3\cdot3
      32=5+33332=5+3\cdot3\cdot3
      34=7+33334=7+3\cdot3\cdot3
      3636 不能表为1+31+3
      38=11+33338=11+3\cdot3\cdot3
      40=13+33340=13+3\cdot3\cdot3
      4242不能表为1+31+3
      44=17+33344=17+3\cdot3\cdot3
      46=19+33346=19+3\cdot3\cdot3
      48=3+33548=3+3\cdot3\cdot5
      50=5+335=23+33350=5+3\cdot3\cdot5=23+3\cdot3\cdot3
      52=7+33552=7+3\cdot3\cdot5
      54=2+221354=2+2\cdot2\cdot13
      56=11+33556=11+3\cdot3\cdot5
      58=31+27=13+33558=31+27=13+3\cdot3\cdot5
      6060不能表为1+31+3
      62=17+33562=17+3\cdot3\cdot5
      64=37+333=19+33564=37+3\cdot3\cdot3=19+3\cdot3\cdot5
      78=3+35578=3+3\cdot5\cdot5
      8484 不能表为1+31+3
      9090 不能表为1+31+3
      9696 不能表为1+31+3
      108=3+357108=3+3\cdot5\cdot7
      114114 不能表为1+31+3
      114={2+2473+33719+51923+71329+51737+71159+51179+5789+55114=\begin{cases}2+2^{4}\cdot7\\3+3\cdot37\\19+5\cdot19\\23+7\cdot13\\29+5\cdot17\\37+7\cdot11\\59+5\cdot11\\79+5\cdot7\\89+5\cdot5\end{cases}
      114={5,7,11,13,17,31,41,43,47,53,61,67,71,73,83,97,101,103,107,109}20114=\left\{ 5,7,11,13,17,31,41,43,47,53,61,67,71,73,83,97,101,103,107,109 \right\}_{20}
      138138不能表为1+31+3
      144144 不能表为1+31+3

    大于2828的不能表为1+31+3的偶数都能被33整除!
    146146开始,我算到266266都能够表为1+31+3
    11461146 不能表为1+41+4
    待续中

    展开全文
  • 初等数论》(第四版)(闵嗣鹤,严士健编)第五章:二次同余式与平方剩余的8个小节的习题答案:①一般二次同余式,②奇素数的平方剩余与平方非剩余,③勒让德符号,④前节定理的证明,⑤雅克比符号,⑥合数模的...
  • 目录1题目:证明2题目证明3题目证明4题目证明5题目 1 题目: 证明:任意奇数的平方减1是8的倍数 证明 设这个奇数为a+1a+1a+1,aaa为偶数 它的平方-1为a2+2a=a(a+2)a^2+2a=a(a+2)a2+2a=a(a+2) ∵\because∵aaa为偶数 ...

    1

    题目:

    证明:任意奇数的平方减1是8的倍数

    证明

    设这个奇数为a+1a+1,aa为偶数

    它的平方-1为a2+2a=a(a+2)a^2+2a=a(a+2)

    \becauseaa为偶数

    \thereforeaaa+2a+2中肯定有一个数可以被4整除

    \thereforea(a+2)a(a+2)88的倍数

    得证

    2

    题目

    nn是偶数时,23n+12|3^n+1;当nn是奇数时,223n+12^2|3^n+1;
    证明:
    但无论nn是偶数还是奇数,对任意整数α>2\alpha>2,都有2α3n+12^\alpha \nmid 3^n+1

    证明

    证:

    31=33^1=3,3%8=33\%8=3
    32=93^2=9,3%8=13\%8=1
    那么3n%8=3n1%8×33^n\%8=3^{n-1}\%8\times3
    \therefore由数学归纳法
    33%8=33^3\%8=3
    34%8=13^4\%8=1
    \dots

    即3的幂modmod 88的余数都是1,3,1,31,3,1,3的循环

    那么3的幂+1modmod 88的余数都是2,4,2,42,4,2,4的循环,不可能被8整除

    因为α>2\alpha>2,所以2α82^\alpha \geqslant 8

    所以2α3n+12^\alpha \nmid 3^n+1

    得证

    3

    题目

    a,bZ,b0a,b \in \mathbb{Z},且b\neq 0,证明: 存在唯一的q,rZq,r \in \mathbb{Z},使得a=qb+ra=qb+r,其中b2r<b2- \frac{\left | b\right |}{2} \leqslant r< \frac{b}{2}

    证明

    证:
    由带余除法:
    存在唯一的q,rZq,r \in \mathbb{Z},使得a=qb+ra=qb+r,其中0r<b0 \leqslant r< b

    b2r\frac{b}{2} \leqslant r

    式子可化为a=(q+1)b+(rb)a=(q+1)b+(r-b)

    所以r的范围为:b2r<b2- \frac{\left | b\right |}{2} \leqslant r< \frac{b}{2}

    4

    题目

    证明:如果2a+3b2a+3b,9a+5b9a+5b中有一个能被1717整除,那么另外一个也能被1717
    整除.

    证明

    2a+3b2a+3b能被1717整除

    2a+3b0(mod17)2a+3b \equiv 0 (mod 17)

    13(2a+3b)0(mod17)\therefore 13(2a+3b) \equiv 0 (mod 17)

    26a+39b0(mod17)\therefore 26a+39b \equiv 0 (mod 17)

    9a+5b0(mod17)\therefore 9a+5b \equiv 0 (mod 17)

    得证

    9a+5b9a+5b能被1717整除

    9a+5b0(mod17)9a+5b \equiv 0 (mod 17)

    4(9a+5b)0(mod17)\therefore 4(9a+5b) \equiv 0 (mod 17)

    36a+20b0(mod17)\therefore 36a+20b \equiv 0 (mod 17)

    2a+3b0(mod17)\therefore 2a+3b \equiv 0 (mod 17)

    得证

    综上,得证

    5

    题目

    假定d1,d2,...,dkd_1,d_2,...,d_k是n的全部正因数,试证: (d1d2...dx)2=nk(d_1d_2...d_x)^2 = n^k

    不妨设

    展开全文
  • 证明:如果Ck=pkqkC_k = \frac{p_k}{q_k}Ck​=qk​pk​​是d\sqrt{d}d​的简单连分数展开式的收敛子,那么∣pk2−dqk2∣<1+2d|p_k^2 - dq_k^2| < 1 + 2\sqrt{d}∣pk2​−dqk2​∣<1+2d​. 思路:已知pk2−...

    证明:如果Ck=pkqkC_k = \frac{p_k}{q_k}d\sqrt{d}的简单连分数展开式的收敛子,那么pk2dqk2<1+2d|p_k^2 - dq_k^2| < 1 + 2\sqrt{d}.

    思路:已知pk2dqk2=(1)k1Qk+1p_k^2 - dq_k^2 = (-1)^{k-1}Q_{k+1},那么可以是否可以求得Qk+1Q_{k+1}的取值范围,然而可知的是αk=Pk+dQk>0,αk=PkdQk(1,0)\alpha_k = \frac{P_k + \sqrt{d}}{Q_k} > 0, \alpha_k' = \frac{P_k - \sqrt{d}}{Q_k} \in (-1, 0),因为αk,kZ+\alpha_k, k \in Z_+是纯循环的,从而可得αkαk=2dQk>0Qk>0\alpha_k - \alpha_k' = \frac{2\sqrt{d}}{Q_k} > 0 \Rightarrow Q_k > 0,又

    Qk+1=dPk+12QkPk+1=dQkQk+1<dQ_{k+1} = \frac{d - P_{k+1}^2}{Q_k} \Rightarrow P_{k+1} = \sqrt{d - Q_kQ_{k+1}} < \sqrt{d}
    Qk+1QkQk+1=dPk+12<dQ_{k+1} \le Q_kQ_{k+1} = d - P_{k+1}^2 < d

    没有得出一个更好的上界,故而尝试采用逆推,遇到什么就证明什么

    证:

    pk2dqk2=pkqkdpk+qkd|p_k^2 - dq_k^2| = |p_k - q_k\sqrt{d}||p_k + q_k\sqrt{d}|

    =qk2CkdCk+d<1+2d= q_k^2|C_k - \sqrt{d}||C_k + \sqrt{d}| < 1 + 2\sqrt{d}

    CkdCk+d<(1+2d)qk2\Leftrightarrow |C_k - \sqrt{d}||C_k + \sqrt{d}| < (1 + 2\sqrt{d})q_k^2

    Ck2<(1+2d)qk2+d\Leftrightarrow C_k^2 < (1 + 2\sqrt{d})q_k^2 + d

    kZ+,jZ+C2k1>C2k+1,C2(j+1)<C2j,C2k1>C2j\because \forall_{k \in Z_+, j \in Z_+}C_{2k - 1} > C_{2k+1}, C_{2(j+1)} < C_{2j}, C_{2k - 1} > C_{2j}

    max(C0,C1,...)=C1\therefore \max(C_0, C_1, ...) = C_1

    Ck2<C12=(a0+1a1)2<(d+1)2=1+2d+d=(1+2d)+d(1+2d)qk2+d\therefore \Leftrightarrow C_k^2 < C_1^2 = (a_0 + \frac{1}{a_1})^2 < (\sqrt{d} + 1)^2 = 1 + 2\sqrt{d} + d = (1 + 2\sqrt{d}) + d \le (1 + 2\sqrt{d})q_k^2 + d

    \therefore得证

    经过反思后,发现上面证明有个致命的错误:

    CkdCk+d<(1+2d)qk2|C_k - \sqrt{d}||C_k + \sqrt{d}| < (1 + 2\sqrt{d})q_k^2

    下面给出严格证明:

    pk2dqk2=qk2CkdCk+d|p_k^2 - dq_k^2| = q_k^2|C_k - \sqrt{d}||C_k + \sqrt{d}|

    <qk2×1qkqk+1×Ck+d< q_k^2 \times \frac{1}{q_kq_{k+1}} \times |C_k + \sqrt{d}|

    <qk2×1qk2×Ck+d< q_k^2 \times \frac{1}{q_k^2} \times |C_k + \sqrt{d}|

    <Ck+d< C_k + \sqrt{d}

    C1+d\le C_1 + \sqrt{d}

    =a0+1a1+d<d+1+d=1+2d= a_0 + \frac{1}{a_1} + \sqrt{d} < \sqrt{d} + 1 + \sqrt{d} = 1 + 2\sqrt{d}

    kZ+{0}Qk<1+2d\therefore \forall_{k \in Z_+ \cup \{ 0 \}} |Q_k| < 1 + 2\sqrt{d}

    展开全文
  • 呵呵,我又来了,好久没写日志了,啦啦啦…… 以前说过的,这次带来……好吧,如。先从自认为简单些的开始吧。 ①威尔逊定理 这个定理是说,对于任意自然数q,当且仅当q是质数时,(q-1)!≡q-1(mod q); ...
     呵呵,我又来了,好久没写日志了,啦啦啦……
        以前说过的,这次带来……好吧,如题。先从自认为简单些的开始吧。

        ①威尔逊定理

            这个定理是说,对于任意自然数q,当且仅当q是质数时,(q-1)!≡q-1(mod q);
            那么,怎么证明咧?
                首先,如果q不是质数,而且q大于4,那一定存在q=0(mod p),q=0(mod q/p) 1<p<q,那么(q-1)!=0(mod q)
                然后,当q是质数时,我们可以构造集合A={1,2,3,4……n-1},对于集合中除1和n-1外的任意数x,集合中必定唯一存在y,使xy=1(mod q)(其实就是y是x的数论倒数),那集合中除1和n-1外的数都可两两配对,使最后的乘积为1(mod q),于是乎,再乘上1和n-1,得到(q-1)!=q-1(mod q);
                还有问题,上面说的对于每个x,存在xy=1(mod q),又怎么证明咧?因为q是质数,x与q互质,构造集合{x,2x,3x……qx},所以该集合一定是对于模q的一个缩系(即任意两个数不对模q同余,从而模q后形成q的剩余系),又因为qx=0(mod q),所以一定唯一存在y(1<y<q),使xy=1(mod q)。
                唔,然后就证完了!

        ②中国剩余定理

            听名字就蛮自豪的,这货是用来解同余方程的说;
                首先,对于同余方程x=ai(mod mi)(1≤i≤n),且各个mi互质,我们定义M=m1Xm2Xm3……Xmn,以及qi=M/mi,设ti为qi对于模mi的数论倒数(前面说过的),那么x=a1*t1*q1+a2*t2*q2+……+an*tn*qn+kM(k为任意整数)。
            然后就是证明了:
                 先把等一下要用的东西写出来:
          因为ti*qi=1(mod mi),所以ai*ti*qi=ai(mod mi);
          因为qi是任意mj(i≠j)的倍数,所以ai*ti*qi=0(mod mj);
                 好了,然后开证了:对于每个mi,x=a1*t1*q1+a2*t2*q2+……+an*tn*qn=ai*ti*qi+a1*t1*q1+a2*t2*q2+……+an*tn*qn;之后
            对于模mi可得x=ai+0+0……+0=ai(mod mi),满足条件,然后再加个kM(这个可以理解吧),得证啦!

        ③费马小定理

            注意,是小定理,不是费马大定理哦!它告诉我们假如p是质数,且gcd(a,p)=1(就是互质),那么a(p-1)≡1(mod p);
            证明来了(略苦逼的说):
                构造集合P={1,2……,p-1},由于p与a互质,那么对于另一个集合A={a,2a……a(p-1)},是p的一个缩系,这个前面说过,这里具体证明一下,如果存在ai=aj(mod p),那么ai-aj=a(i-j)=0(mod p),因为a与p互质,可得i-j=0(mod p)!,与题意不符!
                然后1*2*3……*(p-1)=a*2a*3a……an(mod p),于是(p-1)!=(p-1)!*a(p-1) (mod p),因为(p-1)!与p互质,约去(p-1)!
                得证:a(p-1)≡1(mod p)。

        ④欧拉定理

                费马小定理事实上是欧拉定理的一种特殊情况,欧拉定理是说若p,a为正整数,且p,a互质,则aφ(p)≡1(mod p),证明我就不详述了, 用费马小定理的证明改一下就好了啦,就是这样!又偷懒了……

    转载于:https://www.cnblogs.com/Enceladus/p/4979090.html

    展开全文
  • 20. 证明[b1,…,bn]=[[b1,…bs],[bs+1,…,bn]] 设g=[b1,…,an] h=[[b1,…bs],[bs+1,…,bn]] m=[b1,…bs] n=[bs+1,…,bn] 因为[a,b]=|ab|/(a,b) h=[m,n]=|mn|/(m,n) g=|b1,…,an|/(b1,…,an) 且|b1,…,an|=|mn| 结合...
  • 以前遇到数论题直接懵逼,今天开始好好搞搞基础的数论知识。 一下内容证明我可能会省略,毕竟我太弱了…. . . . . . 1.模运算 几个常用的定律: ( a + b ) mod p = ( a mod p + b mod p ) mod p ( a * b...
  • :使用无穷下降法证明丢番图方程x4−y4=z2x^4 - y^4 = z^2x4−y4=z2无非零整数解.(摘自《初等数论及其应用第六版》13.313.313.3习题444) 前言:近来头脑有些短路,如此清晰的题目竟想了半天不解,坐立不安,困惑于...
  • lucas数论定理学习

    2015-09-14 23:54:02
    2015ICPC长春网络赛1010 考到了lucas+crt(中国...证明来自一本《初等数论》非常赞! hdu3037 模板 #include #include #include #include #include #include #include #include #include //#includ
  • :如果nnn为正整数,那么(∑d∣nτ(d))2=∑d∣nτ(d)3(\sum...(摘自《初等数论及其应用》第六版7.2节习题) 前言:通过观察这两个式子,结合已知的定理 (m,n)=1⇒τ(mn)=τ(m)τ(n)(m,n) = 1 \Rightarrow \tau(mn) ...
  • 知识点:这道用到了初等数论中的知识,即 aX+bY=c有整数解的充要条件是 c能整除a,b的最大公约数,然后将这个推广到n个变量同样成立。 证明:设(a,b)=d 贝祖定理 1)充分性:因为d=(a,b),所以存在x0,y0∈Z
  • 数论问题的解法举例(1)

    千次阅读 2009-12-25 09:39:00
    数论问题叙述简明,“很多数论问题可以从经验中归纳出来,并且仅用三言两语就能向一个行外人解释清楚,但要证明它却远非易事”。因而有人说:“用以发现天才,在初等数学中再也没有比数论更好的课程了。任何学生,如...
  • 首先Lucas定理的定义及简单证明:选自初等数论第37页
  • ·|· 根据《初等数论及其应用》第六版第一章节整理的资料。 ·|· 主要是课件,习题答案只写部分。 【1.1 数和序列】 良性性质:每个非空的正整数集合都有一个最小元。 证明​是无理数代数数:是整系数多项式的根...
  • 证明 1+1/2+......+1/n不是整数

    千次阅读 2015-10-06 16:24:48
    闲来无事翻翻初等数论,顺便编写习题解答,全当是学习数论的同时练习LaTeX了,不想第一节的最后一道习题就难住了,苦思良久无果之后,群里有同行在《初等数论100例》中竟然找到了该,我大体看了下它的证明,可读性...
  • 第1章数学语言与证明方法11.1...12.3习题解答与分析230第13章初等数论和离散概率的应用246 13.1内容提要246 13.2习题247 13.3习题解答与分析249第14章代数系统257 14.1内容提要257 14.2习题266 14.3习题解答与分析270
  • Lucas定理相关证明

    2014-03-31 20:37:35
    的时候遇到了这个东西,感觉网上关于这个的证明很少,于是打算写一篇,由于本人能力有限,证明是看了《命题人讲座初等数论》和http://hi.baidu.com/j_mat/item/8e3a891c258c4fe9dceecaba后根据自己理解写的,有...
  • 1. 问题(来自Rosen的《初等数论及其应用》第6版P99第5) 证明完全平方数的最后两个十进制数字(个位和十位)一定是下列数对之一:{00, e1, e4, 25, o6, e9} 注:e = even number, o = prime number, 0也为偶数 ...
  • 强狄里克雷逼近定理的证明

    千次阅读 2018-10-11 11:26:30
    :如果α是实数,n是正整数,则存在a和b使得1≤a≤n且 |aα - b| ≤ 1/(n + 1).(摘自初等数论及其应用第六版) 证:考虑n + 1个数 S = {0, {α}, {2α}, ..., {jα}, ..., {nα} } 以及n + 1个区间 T = {[0, ...
  • 内容包括密码学研究的基本问题、古典密码学、密码学的信息论基础和计算复杂性理论基础、单向函数和伪随机序列生成器的严格理论、序列密码、分组...公钥密码、字签名、杂凑函数、身份识别、认证码、密钥管理和零知识证明...
  • 本文章部分参考及证明来源潘承洞《初等数论》 对于数论的话,先来一道简简单单的小。 相信这个大家有做过,题解也不差我一个 面:求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。 input 两个正整数...
  • 然后自己yy,实在不懂要看证明就看看二潘的初等数论就好啦。。。#include #include #include #include using namespace std; typedef long long ll; long long prime[1000], times[1000], value[1000]; long long b...
  • 51Nod-1969-Fire!

    2017-08-01 19:18:40
    ACM模版描述解数论题,直接调用结论……要是想知道怎么证明,建议去看看那本叫做《初等数论及其应用》第七章部分讲有详细的推论与证明。至于结论嘛,在题解中说的十分清楚了,贴出来大家看看吧……最讨厌这种了...
  • 清北学堂培训大纲

    2019-04-09 19:31:00
    电脑打不开word和ppt的孩子伤不起啊(我竟然忘了我...Day 2:(钟神的小学初等数论) 1.几个神奇的定理的证明(唯一分解定理,欧拉定理,裴蜀定理) 2.更为高级的miller_rabin筛素数 3.矩阵求逆(附带高斯...
  • 初等数论及其应用》第六版第九章 省略了很多帮助理解的例子和证明。浓缩了一下密集的知识点。 前置 乘性函数 可以见博客的算法讲4、5、7 整数的 ⌈\lceil⌈阶⌋\rfloor⌋ 和 ⌈\lceil⌈原根⌋\rfloor⌋ 整数的...
  • ACM训练日记—1月20日

    2018-01-20 21:33:16
    今天还是在看《初等数论》,今天看的没昨天那么快,确实在一些有意思的题目上停留了许多时间。其实之前数分老师就曾经说过数学课本就如同侦探小说一样精彩。环环相扣的定理引理例题,就连课后小的结论都经常会在...
  • 2018年1月19日训练笔记

    2018-01-19 21:59:43
    从昨天一直再看莫比乌斯反演,大体了解了过程,关于证明还是模模糊糊,也不会用,然后就暂时放弃了证明,接下来要看几道,今天下午就再看《初等数论》,还没看多少,比想象中看的要慢一些。   说一下莫比乌斯...
  • POJ1401解题报告

    2014-01-19 19:09:12
    思路: 这一要求的是N!中末尾0的个数,其实也就是所包含因子10的个数。10=5*2,因子10的个数也就是因子2的个数...,这个算法在集训手册推荐的那本《初等数论》上64页有证明,其中x的值是1--N之中所有p的倍数的个数

空空如也

空空如也

1 2
收藏数 39
精华内容 15
关键字:

初等数论证明题