ΥڡϤƤʥ֥åޡɲΥڡޤϤƤʥ֥åޡ Υڡlivedoor åפɲΥڡޤlivedoor å

ܼ

Ʊ

[]8150137233 (mod 4)ΩĤȤΤ롣

815013723
=815013700100+23
8150137000+23 (mod 4)ʢ1000 (mod 4))
23 (mod 4)
20+3 (mod 4)
3 (mod 4)(200 (mod 4))

[]271-176833 (mod 5)ΩĤȤΤ롣

22-1 (mod 5)Ѥȡ

2712235+1(-1)352-2 (mod 5)(*)

ˤʤ롣

ޤ61 (mod 5)Ǥ뤳Ȥ顢

683318331 (mod 5)

Ȥʤ롣

Ʊαդϡ

  • 176833-171-2 (mod 5)(**)

Ȥʤ롣

äơ(*)(**)ϰפ롣

[]11|(213317+519724)򼨤

Ʊx2-1 (mod p)

ɤǿpˤĤơιƱϲĤΤĤޤꡢιƱx¸ߤ뤿pξϲĴ٤롣

x2-1 (mod p)(*)

ιƱβȤƤ΢(-1)ϡñ̤i(=(-1))ȤϤޤäʪǤ롣

[]p=7ξˡ(*)ͻ롣

7ˡȤʿ׻ȡɽ롣

x0123456
x201492162254361
  • 16 (mod 7)Ǥꡢɽx2ιˤ6ʤΤǡx2-1 (mod 7)˲򤬤ʤȤ狼롣

[]p=13ξˡ(*)ͻ롣

x0123456789101112
x201493121010123941
  • 112 (mod 13)Ǥꡢɽx2ιˤx58ΤȤ12Τǡx58ΤȤx2-1 (mod 13)ϲġ

嵭ˤꡢp=7ΤȤˤ(*)ϲp=13ΤȤˤ(*)ϲġΤ褦pͤˤäơ(*)Ĥɤޤ롣

¤ϡ(*)ľϡp=2ޤp1 (mod 4)Ǥ뤳Ȥ狼äƤ롣¨pξͣζǿǤ2Ǥ뤫1ǿǤ뤳ȤǤ롣
p=131ǿǤ뤿ᡢ(*)ľ

[]pǿΤȤƱx21 (mod p)βϡx1 (mod p)Ǥ롣

[]xx21 (mod p)Ȥ롣

ȡp|(x2-1)Ǥ롣

p|(x-1)(x+1)ʢx2-1=(x-1)(x+1)

ΤȤpǿǤ뤫顢p|(x-1) or p|(x+1)Ωġϡx1 (mod p) or x-1 (mod p)ΩĤȤȤʤΤǡ꤬줿

[]Ʊx2-1 (mod p)Ĥɬ׾ʸϡp=2 or p1 (mod 4)Ǥ롣

[][1]p=2ΤȤx2-11 (mod 2)Ȥʤꡢx=1Ȥʤ롣äơp=2ΤȤˡ(*)ϲ򤬤롣

[2]pǿΤȤ

(i)p3 (mod 4)ξ硢¨3ǿξˡ(*)ʤȤ򼨤

ˡѤ롣(*)βȤʤx¸ߤȲꤹ롣

ΤȤx4(-1)^21 (mod p)ΩĤΤǡxpˡȤ̿ordp(x)4Ǥ롣

(*)ˤꡢx21 (mod p)ǤpʤΤǡ-11 (mod p)Ǥˡ
ȡ4|(p)Ǥ롣ʤʤ[̿](a,m)=1Ȥd=ordm(a)֤kˤĤơak1 (mod m)Ȥʤ뤿ɬ׽ʬϡd|kǤפΩĤǤ롣

4|(p)
4|p-1ʢ(p)=p-1

p3 (mod 4)Ȥ̷⤷Ƥ롣

äơp3ǿΤȤˤϡ(*)ˤϲ򤬤ʤ

(ii)p1 (mod 4)ξ硢¨1ǿξˡ(*)ĤȤ򼨤

ˤȤƤϡѤơ(*)β롣

1p-1ޤǤp-1Ĥο򡢡Ⱦס1(p-1)/2ޤǡˤȡָȾס(p+1)/2p-1ޤǡˤʬơȾο٤ƤѤxȤ

x=1~\times~2~\times~\cdots~\times~(\frac{p-1}{2})(1)

ȾοˤĤƤϡʲθ롣

(p-1)-1,(p-2)-2,,(p+1)/2-(p-1)/2 (mod p)

򤹤٤Ƴݤ碌ȼ롣

(\frac{p+1}{2}~\times~\cdots~\times~(p-2)~\times~(p-1)~\equiv~(-1)^{\frac{p-1}{2}}x~\,~(mod~\,~p))
(\frac{p+1}{2}~\times~\cdots~\times~(p-2)~\times~(p-1)~\equiv~x~\,~(mod~\,~p))(2)ʢp1 (mod 4)Ǥ뤳Ȥ顢(p-1)/2϶Ǥ롣äơ(-1)^{\frac{p-1}{2}}~=~1

(1)(2)ˤäơ롣

(p-1)!
=1~\times~2~\times~\cdots~\times~(\frac{p-1}{2})~\times~\frac{p+1}{2}~\times~\cdots~\times~(p-2)~\times~(p-1)
\equiv~x^2~\,~(mod~\,~p))

륽ꡢ(p-1)!-1 (mod p)ʤΤǡʲΩġ

x^2~\equiv~-1~\,~(mod~\,~p))

äơx(*)βǤ롣

ʸ

  • ػϤ褦