根据k与3的同余得到二次剩余值与3的同余 本次文介绍n=4k-1，费马分解的两个值与后序序列的连续两个整数枳的关系，以及在k≡0(mod 3)、k≢0(mod 3)时，a^2≡b(mod n)，√n<a<√(2n)，b与3的整除关系。
一、后序序列连续两个整数积与费马分解值的关系设n=4k-1，n=ab，1<a<b，根据费马分解有:t^2≡s^2(mod n)，其中: t=(a+b)/2，s=(b-a)/2 因n=4k-1，则a=4ka+1，b=4kb-1，或者a=4ka-1，b=4kb+1 n=ab=(4ka+1)(4kb-1)=16ka*kb-4ka+4kb-1=4(4ka*kb-ka+kb)-1，即 k=4ka*kb-ka+kb，上式必为4k-1型 又因为根据后序序列有: c^2-k=i(i-1) ⅰ≥1 ① =﹥ (2c)^2≡(2ⅰ-1)^2(mod n) 此时2c、2ⅰ-1与t、s的关系为 2c=t，2ⅰ-1=s 以下来证明 ∵ k=4ka*kb-ka+kb，要想①式的右边为连续整数积，则: c=ka+kb，代入上式左边有: (ka+kb)^2-(4ka*kb-ka+kb) = (ka)^2+2ka*kb+(kb)^2-4ka*kb+ka-kb = (ka-kb)^2-(kb-kba ) = (kb-ka)(kb-ka-1)为连继两个整数积 ∴ (2(ka+kb))^2≡2(kb-ka)-1)^2(mod n) ∵t=(a+b)/2=(4ka+1+4kb-1)/2=2(ka+kb) s=(b-a)/2=(4kb-1-4ka-1)/2=2(kb-ka)-1 也即2c=t ， 2i-1=s
二、k≡0(mod 3)及k≢0(mod 3)时，t与s和3的整除关系㈠ 、从后序序列证明t、s与3的同余关系 设n=4k-1，n=ab，1<a<b，根据费马分解有: t^2≡s^2(mod n)，其中: t=(a+b)/2 s=(b-a)/2 再设定(n，3)=1，(t，s)=1，有 如果k≡0(mod 3)，则t≡0(mod 3) 如果k≢0(mod 3)，则s≡0(mod 3) 证明如下: 1、当k≡0(mod 3)，可表示为k=3d 则c可表示为3g、3g±1，分别代入①式中有: ⑴、c≡0(mod 3)，即c=3g有 (3g)^2-3d，可知①式右边必为3的倍数3f，即: (3g)^2-3d=3f(3f±1)，等式两边都存在3的倍数，上式成立 根据笫一段可得: (6g)^2≡(6f±1)^2(mod n)，也即: t=6g => t≡0(mod 3) ⑵、c≢0(mod 3)，可令c=3g±1，代入①式可表示为: (3g±1)^2-3d=(9g^2±6g-3d)+1，该式不为3的倍数，而ⅰ不为3的倍数连续两个整数积的表达为: (3f+1)(3f+2)=9f^2+9f+2 => (9g^2±6g-3d)+1≠9f^2+9f+2 => 9g^2±6g-3d≠9f^2+9f+1 左边为3的倍数，右边不是3的倍数，该等式不成立 ∴ 根据上述情况可知: 当k≡0(mod 3)，则t≡0(mod 3) 2、当k≢0(mod 3)时，s≡0(mod 3) 此时k分别表示为3d+1，3d-1， ⑴、当 k=3d+1，代入n得: 4(3d+1)-1=12d+3，n必为3的倍数，与题设(n，3)=1不符，舍去。 ⑵、当k=3d-1时，根据c与3是否能整除，可分为以下情况: Ⅰ、当c≡0(mod 3)时，可令c=3g，代入①式得: (3g)^2-(3d-1)，结果不是3的倍数，等式右边必为(3f+1)(3f+2)，可得: 9g^2-3d=9f^2+9f+3，该式可以成立。根据第一段可得 (6g)^2≡(6f+3)^2(mod n) 此时(t，s)=3，与题设不符，舍去。 Ⅱ、当c≢0(mod 3)时，可令c=3g±1，代入①式 (3g±1)^2-(3d-1)=9g^2±6g-3d+2 结果不为3的倍数，等式右边只能为(3f+1)(3f+2)=9f^2+9f+2，即: 9g^2±6g-3d+2=9f^2+9f+2，该结果成立 根据笫一段可得: (6g±2)^2≡(6f+3)″2 (mod n) 此时:s=6f+3 => s≡0(mod 3) ∴∴综上述可知: 当k≢0(mod 3)，则s≡0(mod 3)
㈡、从前序序列证明c^2≡d(mod n)中d与3的同余关系 设n=4k-1，n=ab，1<a<b，(n，3)=1，c^2≡d(mod n)，√n<c<√(2n)以下分别讨论当d≥0和d<0这两种情况下，d与3的整除结果。 ⑴ 、当d≥0时 Ⅰ、如果 k≡0(mod 3)， 则有d≢0(mod 3) Ⅱ、如果k≢0(mod 3)，根据c与3的整关系，有以下两种结果: 当c≡0(mod 3)，有d≢0(mod 3) 当c≢0(mod 3)，有d≡0(mod 3) 下面来分别证明。 二次剩余值: d=c^2-n=c^2-(4k-1) ② 1、当k≡0(mod 3)，可设k=3f Ⅰ、当c≡0(mod 3)，令c=3g，代入②式得: (3g)^2-(12f-1)=3(3g^2-4f)+1，即 c^2-(4k-1)≡1(mod 3) => d≡1(mod 3) 即: d≢0(mod 3) Ⅱ、当c≢0(mod 3)时，令c=3g±1，代入②式得 (3g±1)^2-(12f-1)=3(3g^2±2g-4f)+2，即 c^2-(4k-1)≡2(mod 3) => d≡2(mod 3)， 即: d≢0(mod 3) 综合上述两种情况，得: 当k≡0(mod 3)时， 有d≢0(mod 3)
当k≢0(mod 3) 时， k可分别表示为:3f-1和3f+1，以下分别证明 2、当k=3f-1时，即k≡-1(mod 3) Ⅰ、当c≡0(mod 3时，令c=3g，代入②式得: (3g)^2-(12f-5)=3(3g^2-4f)+5，即 c^2-(4k-1)≡2(mod 3) 即 d≢0(mod 3) Ⅱ、当c≢0(mod 3)时， c=3g±1，代入②式得 (3g±1)^2-(12f-5)≢=3(3g^2±2g-4f+2) 即 c^2-(4k-1)≡0(mod 3) 即 d≡0(mod 3) 3、当k=3f+1，即k≡1(mod 3)，4(3f+1)-1=12f-3，此时(n，3)=3，与题设不符，舍去。 根据上述可知: 当k≢0(mod 3) 时，分为以下两种情况: 当c≡0(mod 3)时，有d≢0(mod 3) 当c≢0(mod 3)时，有d≡0(mod 3)⑵、当d<0时，则有: Ⅰ、如果k≡0(mod 3)，有以下两种结果: 当c≢0(mod 3)，有d≡0(mod 3)
...(已截断)
---
来源: 看雪论坛
原文链接: https://bbs.kanxue.com/thread-290177.htm
[原创]整数分解随笔(k与3的同余关系得到二次剩余值与3的同余)
81 浏览
0 回复
暂无回复，快来抢沙发吧！