x2a (mod p)Ȥ2ƱˤϡȤȤʤȤ롣
λ¤ǹͻ뤿ˡp=7ʴǿˤΤȤͤƤߤ롣
ޤˡɽˡɽʤΤ0Ͻ졢ʳ16γݤɽˤʤ롣 mod 7ǹͤΤǡ7dzä;꤬Ƥ롣
1 | 2 | 3 | 4 | 5 | 6 | |
1 | 1 | 2 | 3 | 4 | 5 | 6 |
2 | 2 | 4 | 6 | 1 | 3 | 5 |
3 | 3 | 6 | 2 | 5 | 1 | 4 |
4 | 4 | 1 | 5 | 2 | 6 | 3 |
5 | 5 | 3 | 1 | 6 | 4 | 2 |
6 | 6 | 5 | 4 | 3 | 2 | 1 |
ɽ狼뤳ȤȤơ٤ƤιԤ16ͤ1ФƤ롣p=7ǿǤ롣⤷pʤ顢Ϥʤ0о줷ꡢƱͤо줷ꤹΤǤ롣
ǽפʤΤϡгʬǤ롣1ܤʬгʬФƤ
x | x2 |
1 | 1 |
2 | 4 |
3 | 2 |
4 | 2 |
5 | 4 |
6 | 1 |
ɽܤȡx2ʬ岼оݤˤʤäƤ뤳Ȥ狼롣
ľŪ뤿ˤϡxΤȤФ褤mod7Ǥϡ4-35-26-1ʤΤǡΤ褦˽롣
x | x2 |
1 | 1 |
2 | 4 |
3 | 2 |
-3 | 2 |
-2 | 4 |
-1 | 1 |
ƤߤмǤxˤϡ1,2,3˥ޥʥĤƵսˤ3,2,1о줷Ƥ롣
Ǥդbˤơb2=(-b)2 (mod p)ΩġĤޤꡢ2Ĥb-b2ǤϰפȤȤǤ롣
ɽ2Ʊx2a (mod 7)β¸ߤȤa¸ߤʤȤaȽ롣x2о줹ϡxʿmod pǹͤͤǤ롣Ĥޤꡢa=1,4,2ΤȤx=1,2,3Ȥ뤳Ȥ狼롣
Ĥa=3,5,6ˤϲʤʤʤСx2ΤȤо줷ʤǤ롣
2Ʊβ̵ͭˤäơaθƤ̾ѤƤ
[]xʿmod pǹƱmod pΡʿ;ȸƤ֡Ǥʤmod pΡʿ;ȸƤ֡
p=7ǤСp=7ʿ;1,4,2Ǥꡢp=7ʿ;3,5,6Ǥ롣
p̤ͤξp=NˤǤʿ;ȤǰΩĤޤpǿȤƥȤ롣
ʿ;ȼΤ褦ˤʤ롣
[]pʡ2ˡǿpaڤʤȤ롣
apˡȤʿ;
defx2a (mod p)ġ
Ρ֢bZ,b2a (mod p)
ˡʿ;ʿ;ν롣
[]mod pʿ;νQRpmod pʿ;νQNRpɽ롣
ȼΤ褦ˤʤ롣
[]p=3ΤȤͻȡQR3={1}QNR3={2}Ǥ롣
[]p=5ΤȤϡQR5={1,4}QNR5={2,3}Ǥ롣
[]p=7ǤСQR7={1,2,4}QNR7={3,5,6}Ǥ롣
[]pξ⡢QRp˴ޤޤͤοˡQNRp˴ޤޤͤοˡ¨|QRp|=|QNRp|Ȥطˤʤ롣
ơ|QRp|=(p-1)/2Ǥ롣
̤ǿpˡȤͤ롣p=2ΤȤϼʤΤǡʹߤp2Ȥ롣ȡpǿʤΤǡp=2s+1Ƚ롣
ΤȤpˡȤʿ;ϡ12,22,,(p-1)2pdzäȤ;Ǥ롣
Ȥp=2s+10ˤꡢs+1-s,s+2-(s-1),s+3-(s-2),,2s-1 (mod p)Ǥ뤿ᡢ12,22,,s2ޤǹͤнʬǤ롣
ȤƤޤȤȡΤ褦ˤʤ롣
[]ǿp=2s+1ˡȤʿ;ϡ12,22,,s2pdzäȤ;Ȥ롣
äˡʿ;sĤ롣
[]12,22,,s2pdzäȤ;꤬٤ۤʤ뤳Ȥɬפ롣
1mnsȤȤˡȲꤷ̷Ƴ
äơ(n+m)(n-m)pdzڤ롣
Ĥޤꡢn+m or n-mξʤȤpdzڤ롣
ǡ1mnsꡢ0n-ms2n+m2sǤ롣
Τᡢn-mn+mp(=2s+1)ܿǤϤʤΤǡ̷⤬
[]pǿp=2s+1)Ȥ롣
(1)1ϾpˡȤʿ;Ǥ롣
(2)abpˡȤʿ;ʤСabʿ;Ǥ롣
abpΤȤϡabpdzä;꤬ʿ;ˤʤȤȤǤ
(3)apˡȤʿ;ʤСab1 (mod p)Ȥʤ褦ʿ;b礦1Ĥ¸ߤ롣
[]
(1)12=1ʤΤǡ餫ʿ;Ǥ롣
(2)abpˡȤʿ;
͡a2,b2 (mod p)Ƚ
͡ab()2 (mod p)Ωġ
͡abpˡȤʿ;
(3)եޡξꡢ
b=ap-2ȤС롣
ab1 (mod p)(*)
ꡢaʿ;Ǥ롣
äơaȤѤͤС(2)ˤꡢap-2ʿ;Ǥ롣
ޤʿ;c¸ߤΤȤ롣
ac1 (mod p)(**)
ǡ(*)(**)Ȥκȡa(b-c)=ab-ac0 (mod p)Ȥʤꡢpa(b-c)ڤ롣
paϸߤǤǤ뤫顢pb-cڤʤФʤʤ
Ĥޤꡢbc (mod p)
p=2s+1ΤȤpˡȤʿ;θĿsĤǤ뤳ȤϤǤ˾ѤߤǤ롣
[]p=2s+1ǿpˡȤʿ;a1,,asȤȡιƱΩġ
ιƱΰ̣ϡդȱդ¿༰ηߤ˹ƱȤȤǤ롣
[]̾¿༰ΰʬƱͤˤƾ롣
֤
aipˡȤơʿ;ʤΤǡȽ롣
ʢ
ʢp=2s+1ꡢ2s=p-1Ǥ뤫
ʢեޡξ
äơf(x)x-a1dzäơΤ褦˽
ǡf1(x)ϼs-1¿༰ǡǤx-a1ˤxη1a1ǤȤȤȤäˡ
x=a1֤ȡȤʤ뤬
顢
Ǥ롣
äơΤ褦˽ľ롣
(*)
ˡx=a2֤ƤߤȡΩġ
ʢ
¨f1(a2)(a2-a1)Ѥpdzڤ롣
顢
ǤʤФʤʤ
٤f1(x)x-a2dzäơΤ褦˽롣
ȤޤäƱͤˤơȤʤꡢΤ褦˽ľ롣
Ʊͤε֤ȤǡդΩġ
[]aǿp=2s+1ߤǤȤ롣
ΤȤapˡȤʿ;Ǥ뤫ʤϡˤäޤ롣
(1)a(pˡȤʿ;
(2)a(pˡȤʿ;
[][]p=2s+1ǿpˡȤʿ;a1,,asȤȡιƱΩġ
פˤСƱ
βϤ礦sĤꡢpˡȤʿ;aSUB{1},,asǤ롣
ǿpФơϸgˤ¸ߤ롣ΤȤ1(p-1)ޤǤgΤ٤ɽȤǤ
aλؿtȤȡؿIndg(a)=t¸ߤ롣Ĥޤꡢagt (mod p)Ωġ ⤷t¨t=2sʤСag2s(gs)2 (mod p)Ǥ롣
(gs)2a (mod p)2x2a (mod p)ӤȡgsxβǤ롣
Ĥޤꡢaʿ;Ǥ롣
ϵդΩġ
ʾޤȤơȤƤ
[]㤨Сp=7ΤȤˤǾθϺg=3Ǥ롣ΤȤλؿtơؿɽʻؿɽ긵ˤзμ֤Ͼʤˡ
p=7g=3λؿɽǤ
a | t |
1 | 0 |
2 | 2 |
3 | 1 |
4 | 4 |
5 | 5 |
6 | 6 |
ؿt=¨t=0,2,4ΤȤaϤ줾1,2,4Ǥ롣p=7ʿ;Ǥä
ޤؿt=¨t=1,3,5ΤȤaϤ줾3,6,5Ǥ롣p=7ʿ;Ǥä
ʾˤꡢΤΩĤȤǧǤ
a,bʿ;Ȥȡx2ay2b (mod p)x,y¸ߤ롣
äơ(xy)2=x2y2=ab (mod p)Ȥʤꡢabʿ;Ǥ뤳Ȥ狼롣
Ĥޤꡢ֡ʿ;ˡߡʿ;ˡʿ;ˡפΩġؿθդȤäƸС֡aλؿˡߡbλؿˢ͡abλؿˡפȤʤ롣
ʤʤСΤ褦˷Ǥ뤫Ǥ롣
Ind(ab)
=Ind(a)+Ind(b)ʢInd
=ܶ
=
ʿ;ʿ;δطϡˡɽľŪǤ롣
äp=7ξͤƤΤǡǤp=7ξˡɽѤ뤳ȤˤΤǡƤӰѤ롣
1 | 2 | 3 | 4 | 5 | 6 | |
1 | 1 | 2 | 3 | 4 | 5 | 6 |
2 | 2 | 4 | 6 | 1 | 3 | 5 |
3 | 3 | 6 | 2 | 5 | 1 | 4 |
4 | 4 | 1 | 5 | 2 | 6 | 3 |
5 | 5 | 3 | 1 | 6 | 4 | 2 |
6 | 6 | 5 | 4 | 3 | 2 | 1 |
黻оݤʬ1ܡ1ܡˤʬʿ;ʿ;ʬˤޤȤ˽ľ
Ĥޤꡢ1,2,3,4,5,6Ȥʬ1,4,2,3,5,6Ⱦ3Ĥʿ;QR7θȾ3Ĥʿ;QNR7θˤȤΤǤ롣
1 | 4 | 2 | 3 | 5 | 6 | |
1 | 1 | 4 | 2 | 3 | 5 | 6 |
4 | 4 | 2 | 1 | 5 | 6 | 3 |
2 | 2 | 1 | 4 | 6 | 3 | 5 |
3 | 3 | 5 | 6 | 2 | 1 | 4 |
5 | 5 | 6 | 3 | 1 | 4 | 2 |
6 | 6 | 3 | 5 | 4 | 2 | 1 |
ɽϼΤ褦ɽ˵夷Ƥ뤳Ȥ狼롣
ʿ; | ʿ; | |
ʿ; | ʿ; | ʿ; |
ʿ; | ʿ; | ʿ; |
ˡQR7={1,2,4}ϾˡȤ狼롣
ʤʤСǤդθФƵո¸ߤñ̸¸ߤƤ뤫Ǥ롣
1 | 4 | 2 | |
1 | 1 | 4 | 2 |
4 | 4 | 2 | 1 |
2 | 2 | 1 | 4 |
ʾδѻˤꡢδطľŪ롣
[]ǿp=2s+1ˡȤơΩġ
(1)a,bʿ; or ʿ;ʤСabʿ;Ǥ롣
(2)a,bΰʿ;¾ʿ;ʤСabʿ;Ǥ롣
[](ab)s=asbsꡢ[]aǿp=2s+1ߤǤȤ롣
ΤȤapˡȤʿ;Ǥ뤫ʤϡˤäޤ롣
(1)a(pˡȤʿ;
(2)a(pˡȤʿ;פ顢դΩġ
[]pϴǿgpˡȤ븶ϺȤ롣
[1]
[2]p1ǿǤȤȤСx2-1 (mod p)Ωġ
[]ɤǿpˤĤƤ⡢pˡȤ븶Ϻ¸ߤ롣
p=2ʿ;1ʤΤǡʲpǿȤ롣
pȤ1(p-1)/2ޤǽĴ٤ʿ;Ǥ뤫ʿ;Ǥ뤫狼롣ˡͿx¨mod pˤĤƤʿ狼롣
ǤǤ른ɥ뵭(/)Ȥɽˤ롣
[]p=2s+1ǿȤ롣
aФơΤ褦롣
ʿ;ʿ;ȸƤ֤ȤϡapܿǤϤʤȤꤹ롣
[]㤨Сp=7ΤȤQR7={1,2,4}ǤäΤǡ른ɥ뵭ȤмΤ褦ˤʤ롣
ۤɸʿ;ʿ;δطȤפƤ롣㤨С(2/7)(3/7)=1(-1)=-1ޤ(6/7)=-1ǰפ롣
른ɥεȤȡʿ;ʷ˽Ҥ٤뤳ȤǤ롣
[]p=2s+1ǿa,bȤ롣
(1)
(2)
(3)
äˡ
(4)
äˡ
[]
(1)ʿ;顢ϤۤȤɼȽȼΤ褦ˤʤ롣
ʺաˡ(a/p)1 or -1ǡɤ餬Ф뤫x2a (mod p)Ĥɤ˰¸롣
ʱաˡ(b/p)1 or -1ǡɤ餬Ф뤫x2b (mod p)Ĥɤ˰¸롣ꡢab (mod p)ʤΤǡդͤx2a (mod p)Ĥɤ˰¸Ȥ롣ϡդäȤޤäƱǤ롣
äơ˰¸̤פΤ餫Ǥ롣
(2)[]ǿp=2s+1ˡȤơΩġ
(1)a,bʿ; or ʿ;ʤСabʿ;Ǥ롣
(2)a,bΰʿ;¾ʿ;ʤСabʿ;Ǥ롣פ른ɥεǽľǤ롣
(3)a2pˡȤʿ;ʤΤǡ른ɥεդΩġ
(4)[]aǿp=2s+1ߤǤȤ롣
ΤȤapˡȤʿ;Ǥ뤫ʤϡˤäޤ롣
(1)a(pˡȤʿ;
(2)a(pˡȤʿ;פ른ɥεǽľǤ롣
äˡa=-1ΤȤƱε椬ˤʤΤϡդˡ1Ǥꡢ줬(-1)s˹ƱȤȤȤƱǤ뤫Ǥ롣
[̾](3)
(2)η̤a=bФ褤
[](1)η̤ˤꡢ른ɥ뵭ʬҤʬdzä;֤ƤʤȤݾ㤵줿
㤨С(72/7)=(2/7)=(-5/7)ȷǤ롣
[]
[]Ǥ˾ѤߤǤ롣
[]
[]aȡؿInd(a){0,,p-2}Τ줫1Ĥ˽ʣ˳롣
pϴʤǿˤʤΤǡ{0,,p-2}˴ޤޤ븵϶Ĥ롣
ĤޤꡢΤȾʬ϶ǤꡢĤȾʬϴǤ롣
äơʿ;θĿΤȾʬǤ롣
Ωġ
[̾](2)
ʬ롣
[1]ޤ
ΤȤ
른ɥ뵭ˤξդȤ0Ǥ롣
[2]ΤȤ
ʺա
=(a/p)(b/p)
=(-1)Ind(a)(-1)Ind(b)
=(-1)SUP{Ind(a)+Ind(b)}:
=(-1)Ind(ab)
=(ab/p)
=ʱաˡ
ξʿ;ξˡξȤۤȤƱǤäñɽ㤦Ǥ롣
ˤꡢnФ(n/p)ȤϡnǰʬФ褤СǽŪ(-1/p) or (2/p) or (ǿˤѤ˵Ǥ롣
n礭ȤϡnǰʬǤʤΤᡢ른ɥ뵭ǤϺΤǡĥǤΥ䥳ӵȤΤ¸ߤ롣
[]顼
[]դ(a/p)0,1,-1Ǥ뤫ˤꡢʬ롣
[1]ʺաˡ(a/p)=0ΤȤ
른ɥ뵭p|aǤ롣
ʱա
ʢapdzڤΤǡmod paϤ0ˤʤ
0
äơդȱդפ롣
[2]ʺաˡ(a/p)=1ΤȤ
xZ;ax2 (mod p)
ʱա
ʢax2
1 (mod p)ʢեޡξ
äơդȱդפ롣
[3]ʺաˡ(1/p)=-1ΤȤ
pθϸgȤȡIndg(a)=2m+1Ωġ
ʱա
ʢIndg(a)=2m+1ꡢa=g2m+1
ʢ踶ϸꡢgp-11
-1ʢlogg(-1)=(p-1)/2)
äơդȱդפ롣
äơ[1][3]ꡢΩġ
[](a,p)=1ǤäƤ⡢(a,p)1ǤΩġ
[]p=7,a=4ΤȤǴѻƤߤ롣
ʢ襪顼
Ǥ˸褦4QR7Ǥꡢߤפ롣
ʤҤΤǤϤʤǴѻƤߤ롣
p=11,a=7Ȥ롣a1ܤ5ܡ=(p-1)/2=10/2)ޤǤο롣
a1, a2, a3, a4, a5 | |
71, 72, 73, 74, 75 | |
7, 14, 21, 28, 35 | |
mod p롣 | |
7, 3, 10, 6, 2 | |
p/2=11/2=5.5礭11¨ޥʥɽ롣 | |
-4, 3, -1, -5, 2 | οͺǾ;ȸƤ֡ |
ޥʥ | |
4, 3, 1, 5, 2 | 1,2,3,4,51̤긽Ƥ롣 |
ΤȤ른ɥ뵭롣
(-1)^(ͺǾ;οθĿ)롣οθĿ3ĤʤΤǡ(-1)3=-1ˤʤ롣-1ͤȰפƤ롣
ʾp=11,a=7ξεǤä̤ξǤΩġȤ
[]
pǿr=(p-1)/2(a,p)=1Ȥ롣
ΤȤarܤޤǤܿ¤٤롣=
1a, 2a, , ra
mod pͺǾ;a1, a2, , a_rȤ롣
οθĿtȤС(a/p)=(-1)^tǤ롣
嵭ɽǤͺǾ;ȤդȤäƤ뤬1a,2a,,rapdzä;p/2礭θĿtȸ뤳ȤǤ롣
ΥˤĤơľǹͤƤߤ롣
x1(p-1)/2ޤǤΤ줫οȤ롣aܤơmod pϰAϰB˴ޤޤ롣ΤϰB˴ޤޤĿtȤȡpˡȤaʿ;¨(a/p)tζ˰¸ȤȤǤ롣
[](a,p)=1ΤȤa(p-1)/2ġ=rȤˤܿ롣
1a, 2a, , ra (*) aźǤϤʤ1a1a
ơкǾ;
a1, a2, , a_r (**)1,2,,rź
Ȥ롣
(**)Ρ͡ɤϤ٤mod pǰۤʤ롣
(i)ai=aj1i,jrijˤȲꤹ롣
aiaj (mod p)
a(i-j)0 (mod p)
ij (mod p)ʢ(a,p)=1aξդä
̷⡣
(ii)ˡai=-aj1i,jrijˤȲꤹ롣
ai-aj (mod p)
a(i+j)0 (mod p)
i+j0 (mod p)ʢ(a,p)=1aξդä
r=(p-1)/2ǤäΤǡi+j=2rǤäȤƤ⤻p-1Ȱס
äơi+jp-1Ǥꡢi+jpˤʤ롣
i+j0 (mod p)i+jp餫̷⡣
ʾ(i)(ii)ꡢ(**)Ρ͡ɤϤ٤mod pǰۤʤ뤳Ȥ狼롣
ˡ(**)οˤ̵뤹ȡ1,2,,r1̤긽롣
(**)θĿtȤȡa1a2ߡġa_r=(-1)^tr!(***)Ωġ
ޤ(*)ꡢ(1a)(2a)(ra)=a^rr!(****)Ωġ
mod p(***)(****)ϹƱʤΤǡΩġʱդܤˡ
ʢ(r!,p)=1ꡢξդr!ä
ʢr=(p-1)/2
ʢ襪顼ˡ
nФ(n/p)Ȥϡ른ɥ뵭ϾˡĤΤǡnǰʬФ褤С(n/p)(-1/p) or (2/p) or (ǿ/p)Ѥ˵夵롣Ĥޤꡢ(-1/p) or (2/p) or (ǿ/p)1-1ȽꤹƻˤɬפǤ롣
[]1佼ˡ§
pǿȤ롣
[]顼Ǥ(a/p)=a^{(p-1)/2}ˡa=-1
[̾]a=-1Ȥơaܿ¤٤롣
Ϥ٤ͺǾ;ˤʤäƤΤǡΩġ
(-1/p)=(-1)tʡt=(p-1)/2
[]
[]mΤȤ4ˡȤm=4n12ѥˤʤ롣
p1 (mod 4)ΤȤ(p-1)/2=ꡢ(-1)^{(p-1)/2}ϤĤ1ˤʤ롣
p3 (mod 4)ΤȤ(p-1)/2=ꡢ(-1)^{(p-1)/2}ϤĤ-1ˤʤ롣
[]2佼ˡ§
pǿȤ롣
[ľŪʡ˾]a=2ȤƥŬѤ롣
p-1϶ʤΤǡp-12dz롣
η̤r=(p-1)/2ζˤäơʬ롣ǤľŪǤ褦pŪͤǴѻƤߤ롣
[1]rΤȤ
㤨Сp=138ˡȤƤȤ5ˤȤȡp/2=6.5r=(p-1)/2=6Ȥʤꡢ16ޤǤοܿο롣
a1, a2, a3, a4, a5, a6 | 6Ĥοǹ롣 |
a=2 | |
21, 22, 23, 24, 25, 26 | |
2, 4, 6, 8, 10, 12 |
οǡp/2=6.5礭ΤθĿt=3ġ=r/2=(p-1)/4ˤǤ롣
㤨Сp=178ˡȤƤȤ1ˤȤȡp/2=8.5r=8Ȥʤꡢ18ޤǤοܿο롣
a1, a2, a3, a4, a5, a6, a7, a8 | 8Ĥοǹ롣 |
a=2 | |
21, 22, 23, 24, 25, 26, 27, 28 | |
2, 4, 6, 8, 10, 12, 14, 16 |
οǡp/2=8.5礭ΤθĿt=4ġ=r/2=(p-1)/4ˤǤ롣
[2]rΤȤ
㤨Сp=158ˡȤƤȤ7ˤȤȡp/2=7.5r=7Ȥʤꡢ17ޤǤοܿο롣
a1, a2, a3, a4, a5, a6, a7 | 7Ĥοǹ롣 |
a=2 | |
21, 22, 23, 24, 25, 26, 27 | |
2, 4, 6, 8, 10, 12, 14 |
οǡp/2=7.5礭ΤθĿt=4ġ=(r+1)/2=(p+1)/4ˤǤ롣
㤨Сp=198ˡȤƤȤ3ˤȤȡp/2=9.5r=(p-1)/2=9Ȥʤꡢ19ޤǤοܿο롣
a1, a2, a3, a4, a5, a6, a7, a8, a9 | 9Ĥοǹ롣 |
a=2 | |
21, 22, 23, 24, 25, 26, 27, 28, 29 | |
2, 4, 6, 8, 10, 12, 14, 16, 18 |
οǡp/2=9.5礭ΤθĿt=5ġ=(r+1)/2=(p+1)/4ˤǤ롣
ʾεϰ̤Ω뤫顢Ωġ
ΤȤΤ褦ʼͤ롣
2Ĥμζt1 or t2ζ˰¸롣
ʤʤС߶ߴǤ뤫顣
椨ˡϼĥμˤ뱦դ(-1)߾б롣
[]2佼ˡ§ˤꡢ㤨(2/13)ưפ˲ȤǤ롣
p=13ΤȤǤꡢ(p^2-1)/8=(169-1)/8=168/8=21=
äơ(2/13)=(-1)^()=-1ˤʤ롣
[]
[]8ˡȤȡm=8n1 or 8n5nZˤ4ѥˤʤ롣
Ȥǡ2佼ˡ§1-1ϡ
ζ˰¸롣
pϴǿmʤΤǡζ
ζȰפ롣
[]ηϤ´Ƥߤ롣2佼ˡ§(2/13)Ȥϡ132ηɬפǤäȤηϤȤp=135 (mod 8)ꡢ(2/13)=-1Ȥ狼롣
Ĥ(ǿ/p)Ĵ٤ѤΤߤǤ롣ϡʿ;Ρˡ§ȸƤФѤ뤳ȤǼ¸Ǥ롣ˡ§ΤҤȤĤλȸƤꡢˡ§ȯȤƶŸ줿
ˡ§ϥ顼ˤ굢ǼŪ˼졢ʾϥˤäͿ줿ˡ§ξϤ¸ߤ1ˤʤäƤۤɤǤ롣
ǤϤޤˡ§μĥҲ𤹤롣
[]ʿ;ˡ§
p,qۤʤ
ϼΤ褦ˤ롣
[](a/p)=(-1)^tˤơa=qȤ롣
{1q, 2q, , {(p-1)/2}q}
x{1,2,,(p-1)/2}Ȥxq mod pp/2xθĿtб롣
äơxζ狼нʬǤ롣
xq (mod p) p/2
Ρ֡(q/p)xʬʬˡ1/2סʢxq mod pp/2עΡxq=ap+r (aZ,0ar) rp/2עΡr/p=(q/p)x-ap r/p1/2פˡ(*)
ǸOD(p/2,q/2)̤ľY=(q/p)Xˤy1/2ʿưľEFȤ롣
XˤľY=(q/p)X˰ֶᤤʻϡYξ夫ˤ롣
⤽γʻɬ(q/p)X-(1/2)(q/p)X+(1/2)δ֤¸ߤ롣
X=x0p/2ޤ餻Ȥˡľξ¸ߤֶᤤʻθĿt1ȤȼΩġ
t1
=(*)xθĿ
=#{x|x{1,2,,(p-1)/2} xq (mod p) p/2}
=OEFDγʻο
Ʊͤˤơľβ¸ߤֶᤤʻθĿt2ȤȼΩġ
t2
=#{y|y{1,2,,(q-1)/2} yp (mod q) q/2}
=ODHGγʻο
t1+t2
=OEFDγʻοܢODHGγʻο
=OEFDγʻοܢODHGγʻοܢDFBHγʻοʢ袢DFBHˤɬʻ¸ߤʤ
=ϻѷOEFBHG
=OADC-EFF'-GHH'
={(p-1)/2}{(q-1)/2}-2EFF'
2EFF'϶Ǥ
äơΤ褦˼ĥΩġ
Ⱦ줿
ϸȾϻѷOEFBHGM((p+1)/4,(q+q)/4)оΤǤ롣
[1](p+1)/4(q+1)/4¨p-13 (mod 4)q3 (mod 4)ΤȤ
濴Mϳʻˤʤ뤿t1+t2ϴˤʤ롣äơ(q/p)(p/q)=-1
[2]MʻǤʤСt1+t2϶ˤʤ롣äơ(q/p)(p/q)=1
[]ˡ§ȤХ른ɥ뵭ηưפˤʤ뤳Ȥǧ롣
(15/71)
=(3/71)(5/71)ʢ15=35ˡ
=-(71/3)(71/5)
ʢˡ§ܡ71,5ۤʤǿǿ713 (mod 4), 33 (4)פ(3/71)=-(71/3)71,5ۤʤǿ713 (mod 4), 51 (mod 4)פ(5/71)=(71/5)
=-(2/3)(1/5)ʢ712 (mod 3)711 (mod 5)
=-(-1)1ʢ2佼ˡ§ηϡ
=1