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

ܼ

Ϥ

x2a (mod p)Ȥ2Ʊˤϡ򤬤ȤȤʤȤ롣

λ¤ǹͻ뤿ˡp=7ʴǿˤΤȤͤƤߤ롣

ޤˡɽ񤯡ˡɽʤΤ0Ͻ졢ʳ16γݤɽˤʤ롣 mod 7ǹͤΤǡ7dzä;꤬񤫤Ƥ롣

123456
1123456
2246135
3362514
4415263
5531642
6654321

ɽ狼뤳ȤȤơ٤ƤιԤ16ͤ1ФƤ롣p=7ǿ򤷤Ǥ롣⤷pʤ顢Ϥʤ0о줷ꡢƱͤо줷ꤹΤǤ롣

ǽפʤΤϡгʬǤ롣1ܤʬгʬФƤ

xx2
11
24
32
42
54
61

ɽܤȡx2ʬ岼оݤˤʤäƤ뤳Ȥ狼롣
ľŪ򤹤뤿ˤϡxΤȤ񤭴Ф褤mod7Ǥϡ4-35-26-1ʤΤǡΤ褦˽񤭴롣

xx2
11
24
32
-32
-24
-11

񤭴ƤߤмǤxˤϡ1,2,3˥ޥʥĤƵսˤ3,2,1о줷Ƥ롣
\mathbb{Z}_p^*Ǥդ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ɽ롣

ȼΤ褦ˤʤ롣

  • QR_p~=~\{~a~|~a~\in~\mathbb{Z}_N^*~\wedge~~(\exists~x~\in~\mathbb{Z}_p^*~\,~s.t.~\,~a~\equiv~x^2~\pmod{p})~\}
  • QNR_p~=~\{~a~|~a~\in~\mathbb{Z}_N^*~\wedge~~(\exists~x~\in~\mathbb{Z}_p^*~\,~s.t.~\,~a~\not{\equiv}~x^2~\pmod{p})~\}

[]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ȤȤˡm^2~\equiv~n^2~\,~\pmod{p}Ȳꤷ̷Ƴ

m^2~\equiv~n^2~\,~\pmod{p}
n^2~-~m^2~\equiv~0~\,~\pmod{p}
(n~+~m)(n~-~m)~\equiv~0~\,~\pmod{p}

äơ(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)եޡξa~\cdot~a^{p-2}~=~a^{p-1}~\equiv~1~\,~\pmod{p}

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ȤȡιƱΩġ
x^s~-~1~\equiv~(x-a_1)(x-a_2)\cdots(x-a_s)~\,~\pmod{p}

ιƱΰ̣ϡդȱդ¿༰ηߤ˹ƱȤȤǤ롣

[]̾¿༰ΰʬƱͤˤƾ롣

f(x)=x^s~-~1֤

aipˡȤơʿ;ʤΤǡa_i~\equiv~{\alpha_i}^2Ƚ񤱤롣

f(a_i)
=~{a_i}^s~-~1
\equiv~({\alpha_i}^2)^s~-~1~\,~\pmod{p}ʢa_i~\equiv~{\alpha_i}^2
=~\alpha^{2s}~-~1
=~\alpha^{p-1}~-~1ʢp=2s+1ꡢ2s=p-1Ǥ뤫
\equiv~1~-~1~\,~\pmod{p}ʢեޡξ
=0

äơf(x)x-a1dzäơΤ褦˽񤯡

f(x)=f_1(x)(x-a_1)~+~c_1

ǡf1(x)ϼs-1¿༰ǡǤx-a1ˤxη1a1ǤȤȤȤäˡ

x=a1֤ȡf(a_1)=c_1Ȥʤ뤬f(a_1)~\equiv~0~\,~\pmod{p}c_1~\equiv~0~\,~\pmod{p}Ǥ롣

äơΤ褦˽ľ롣

f(x)~\equiv~f_1(x)(x-a_1)~\,~\pmod{p}(*)

ˡx=a2֤ƤߤȡΩġ

f(a_2)~\equiv~f_1(a_2)(a_2~-~a_1)~\,~\pmod{p}
f_1(a_2)(a_2~-~a_1)~\equiv~0~\,~\pmod{p}ʢf(a_2)~\equiv~0~\,~\pmod{p}

¨f1(a2)(a2-a1)Ѥpdzڤ롣
a_2~-~a_1~\not{\equiv}~0~\,~\pmod{p}f_1(a_2)~\equiv~0~\,~\pmod{p}ǤʤФʤʤ

٤f1(x)x-a2dzäơΤ褦˽񤱤롣

f_1(x)=f_2(x)(x-a_2)~+~c_2

ȤޤäƱͤˤơc_2~\equiv~0~\,~\pmod{p}ȤʤꡢΤ褦˽ľ롣

f(x)~\equiv~f_2(x)(x-a_2)(x-a_1)~\,~\pmod{p}

Ʊͤε򷫤֤ȤǡդΩġ

[]aǿp=2s+1ߤǤȤ롣
ΤȤapˡȤʿ;Ǥ뤫ʤϡˤäޤ롣
(1)a^s~\equiv~1~\,~\pmod{p}a(pˡȤʿ;
(2)a^s~\equiv~-1~\,~\pmod{p}a(pˡȤʿ;

[][]p=2s+1ǿpˡȤʿ;a1,,asȤȡιƱΩġ
x^s~-~1~\equiv~(x-a_1)(x-a_2)\cdots(x-a_s)~\,~\pmod{p}פˤСƱx^s~-1~\equiv~0~\,~\pmod{p}βϤ礦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ʿ;Ǥ롣

ϵդΩġ

ʾޤȤơȤƤ

  • amod pλؿעΡamod pʿ;
  • amod pλؿעΡamod pʿ;

[]㤨Сp=7ΤȤˤǾθϺg=3Ǥ롣ΤȤλؿt׻ơؿɽʻؿɽ긵ˤз׻μ֤Ͼʤˡ

  1. a=1ΤȤt=Indg(a)=Ind3(1)=0Ȥʤ롣
    • ʤʤСg=3t=0褹Сmod 7a=1ˤʤ뤫Ǥ롣
  2. a=2ΤȤt=Indg(a)=Ind3(2)=2Ȥʤ롣
    • ʤʤСg=3t=2褹Сmod 7a=2ˤʤ뤫Ǥ롣
  3. a=3ΤȤt=Indg(a)=Ind3(3)=1Ȥʤ롣
    • ʤʤСg=3t=1褹Сmod 7a=3ˤʤ뤫Ǥ롣
  4. a=4ΤȤt=Indg(a)=Ind3(4)=4Ȥʤ롣
    • ʤʤСg=3t=4褹Сmod 7a=4ˤʤ뤫Ǥ롣
  5. a=5ΤȤt=Indg(a)=Ind3(5)=5Ȥʤ롣
    • ʤʤСg=3t=5褹Сmod 7a=5ˤʤ뤫Ǥ롣
  6. a=6ΤȤt=Indg(a)=Ind3(6)=3Ȥʤ롣
    • ʤʤСg=3t=3褹Сmod 7a=6ˤʤ뤫Ǥ롣

p=7g=3λؿɽ񤯽Ǥ

at
10
22
31
44
55
66

ؿ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ξˡɽѤ뤳ȤˤΤǡƤӰѤ롣

123456
1123456
2246135
3362514
4415263
5531642
6654321

黻оݤʬ1ܡ1ܡˤʬʿ;ʿ;ʬˤޤȤ᤿˽ľ
Ĥޤꡢ1,2,3,4,5,6Ȥʬ1,4,2,3,5,6Ⱦ3Ĥʿ;QR7θȾ3Ĥʿ;QNR7θˤȤΤǤ롣

142356
1142356
4421563
2214635
3356214
5563142
6635421

ɽϼΤ褦ɽ˵夷Ƥ뤳Ȥ狼롣

ʿ;ʿ;
ʿ;ʿ;ʿ;
ʿ;ʿ;ʿ;

ˡQR7={1,2,4}ϾˡȤ狼롣
ʤʤСǤդθФƵո¸ߤñ̸¸ߤƤ뤫Ǥ롣

142
1142
4421
2214

ʾδѻˤꡢδطľŪ롣

  • ʿ;ˡߡʿ;ˡʿ;
  • ʿ;ˡߡʿ;ˡʿ;
  • ʿ;ˡߡʿ;ˡʿ;

[]ǿp=2s+1ˡȤơΩġ
(1)a,bʿ; or ʿ;ʤСabʿ;Ǥ롣 (2)a,bΰʿ;¾ʿ;ʤСabʿ;Ǥ롣

[](ab)s=asbsꡢ[]aǿp=2s+1ߤǤȤ롣
ΤȤapˡȤʿ;Ǥ뤫ʤϡˤäޤ롣
(1)a^s~\equiv~1~\,~\pmod{p}a(pˡȤʿ;
(2)a^s~\equiv~-1~\,~\pmod{p}a(pˡȤʿ;פ顢դΩġ

Ϻʿ;

[]pϴǿgpˡȤ븶ϺȤ롣
[1]g^{\frac{p-1}{2}~\equiv~-1~\,~(mod~\,~p)}
[2]p1ǿǤȤx=g^{\frac{p-1}{4}}ȤСx2-1 (mod p)Ωġ

[]ɤǿpˤĤƤ⡢pˡȤ븶Ϻ¸ߤ롣

른ɥ뵭

p=2ʿ;1ʤΤǡʲpǿȤ롣

pȤ1(p-1)/2ޤǽĴ٤ʿ;Ǥ뤫ʿ;Ǥ뤫狼롣ˡͿx¨mod pˤĤƤʿ狼롣

ǤǤ른ɥ뵭(/)Ȥɽˤ롣

[]p=2s+1ǿȤ롣
aФơ(\frac{a}{p})򼡤Τ褦롣

  • apˡȤʿ;ξ硢(\frac{a}{p})~=~1
  • apܿξ硢(\frac{a}{p})~=~0
  • apˡȤʿ;ξ硢(\frac{a}{p})~=~-1 ε른ɥεȸƤ֡

ʿ;ʿ;ȸƤ֤ȤϡapܿǤϤʤȤꤹ롣

[]㤨Сp=7ΤȤQR7={1,2,4}ǤäΤǡ른ɥ뵭ȤмΤ褦ˤʤ롣

  • (1/7)=(2/7)=(4/7)=1
  • (3/7)=(5/7)=(6/7)=-1

ۤɸʿ;ʿ;δطȤפƤ롣㤨С(2/7)(3/7)=1(-1)=-1ޤ(6/7)=-1ǰפ롣

른ɥεȤȡʿ;ʷ˽Ҥ٤뤳ȤǤ롣

[]p=2s+1ǿa,bȤ롣
(1)a~\equiv~b~\pmod{p}(\frac{a}{p})~=~(\frac{b}{p})
(2)(\frac{ab}{p})~=~(\frac{a}{p})(\frac{b}{p})
(3)(\frac{a^2}{p})=1
äˡ(\frac{1}{p})=1
(4)(\frac{a}{p})~\equiv~a^s~\pmod{p}
äˡ(\frac{-1}{p})~=~(-1)^s

[]

(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^s~\equiv~1~\,~\pmod{p}a(pˡȤʿ;
(2)a^s~\equiv~-1~\,~\pmod{p}a(pˡȤʿ;פ른ɥεǽľǤ롣

äˡa=-1ΤȤƱε椬ˤʤΤϡդˡ1Ǥꡢ줬(-1)s˹ƱȤȤȤƱǤ뤫Ǥ롣

[̾](3)򼨤

(2)η̤a=bФ褤

[](1)η̤ˤꡢ른ɥ뵭ʬҤʬdzä;֤ƤʤȤݾ㤵줿

㤨С(72/7)=(2/7)=(-5/7)ȷ׻Ǥ롣

[]

  • amod pλؿעΡamod pʿ;
  • amod pλؿעΡamod pʿ;

[]Ǥ˾ѤߤǤ롣

[](\frac{a}{p})~=~(-1)^{Ind(a)}

[]a\mathbb{Z}_p^*~=~\{~1,~\cdots,~p-1~\}ȡؿInd(a){0,,p-2}Τ줫1Ĥ˽ʣ˳롣
pϴʤǿˤʤΤǡ{0,,p-2}˴ޤޤ븵϶Ĥ롣

ĤޤꡢΤȾʬ϶ǤꡢĤȾʬϴǤ롣

äơʿ;θĿΤȾʬǤ롣

|QR_p|~=~|QNR_p|~=~\frac{|\mathbb{Z}_p^*|}{2}~=~\frac{p-1}{2}Ωġ

[̾](2)򼨤

ʬ롣

[1]a~|~pޤb~|~pΤȤ

른ɥ뵭ˤξդȤ0Ǥ롣

[2]a~\not{|}~pb~\not{|}~pΤȤ

ʺա
=(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ǰʬǤʤΤᡢ른ɥ뵭ǤϺΤǡĥǤΥ䥳ӵȤΤ¸ߤ롣

䥳ӵ

[]顼
(\frac{a}{p})~\equiv~a^{\frac{p-1}{2}}~\pmod{p}

[]դ(a/p)0,1,-1Ǥ뤫ˤꡢʬ롣

[1]ʺաˡ(a/p)=0ΤȤ

른ɥ뵭p|aǤ롣

ʱա
a^{\frac{p-1}{2}}~\pmod{p}
0^{\frac{p-1}{2}}~\pmod{p}ʢapdzڤΤǡmod paϤ0ˤʤ
0

äơդȱդפ롣

[2]ʺաˡ(a/p)=1ΤȤ

xZ;ax2 (mod p)

ʱա
a^{\frac{p-1}{2}}~\pmod{p}
x^{p-1}~\pmod{p}ʢax2
1 (mod p)ʢեޡξ

äơդȱդפ롣

[3]ʺաˡ(1/p)=-1ΤȤ

pθϸgȤȡIndg(a)=2m+1Ωġ

ʱա
a^{\frac{p-1}{2}}~\pmod{p}
\equiv~(~a^{2m+1}~)^{\frac{p-1}{2}}~\pmod{p}ʢIndg(a)=2m+1ꡢa=g2m+1
\equiv~(~g^{p-1}~)^m~\cdot~g^{\frac{p-1}{2}})
\equiv~g^{\frac{p-1}{2}}ʢ踶ϸꡢgp-11
-1ʢlogg(-1)=(p-1)/2)

äơդȱդפ롣

äơ[1][3]ꡢΩġ

[](a,p)=1ǤäƤ⡢(a,p)1ǤΩġ

[]p=7,a=4ΤȤǴѻƤߤ롣

(\frac{a}{p})
\equiv~a^{\frac{p-1}{2}}~\pmod{p}ʢ襪顼
\equiv~4^{\frac{7-1}{2}}~\pmod{7}
\equiv~4^3~\pmod{7}
\equiv~64~\pmod{7}
\equiv~1~\pmod{7}

Ǥ˸褦4QR7(\frac{4}{7})=1Ǥꡢߤפ롣

ʤ򵭽ҤΤǤϤʤǴѻƤߤ롣

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, 21,2,3,4,51̤긽Ƥ롣

ΤȤ른ɥ뵭(\frac{a}{p})׻롣

(\frac{a}{p})
=(\frac{7}{11})
\equiv~7^{\frac{11-1}{2}}~\pmod{11}
=7^5
\equiv~-1~\pmod{11}

(-1)^(ͺǾ;οθĿ)׻롣οθĿ3ĤʤΤǡ(-1)3=-1ˤʤ롣-1(\frac{a}{p})ͤȰפƤ롣

ʾ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(***)(****)ϹƱʤΤǡΩġʱդܤˡ

(-1)^t~\cdot~r!~\equiv~a^r~\cdot~r!~\pmod{p}
(-1)^t~\equiv~a^rʢ(r!,p)=1ꡢξդr!ä
(-1)^t~\equiv~a^{\frac{p-1}{2}}ʢr=(p-1)/2
(-1)^t~\equiv~(\frac{a}{p})ʢ襪顼ˡ

佼ˡ§

nФ(n/p)Ȥϡ른ɥ뵭ϾˡĤΤǡnǰʬ򤹤Ф褤С(n/p)(-1/p) or (2/p) or (ǿ/p)Ѥ˵夵롣Ĥޤꡢ(-1/p) or (2/p) or (ǿ/p)1-1ȽꤹƻˤɬפǤ롣

[]1佼ˡ§
pǿȤ롣
(\frac{-1}{p})~=~(-1)^{\frac{p-1}{2}}

[]顼Ǥ(a/p)=a^{(p-1)/2}ˡa=-1

[̾]a=-1Ȥơaܿ¤٤롣

  • 1,-2,,-r

Ϥ٤ͺǾ;ˤʤäƤΤǡΩġ

(-1/p)=(-1)tʡt=(p-1)/2

[]

  • p1 (mod 4)ΤȤ(-1/p)=1
  • p3 (mod 4)ΤȤ(-1/p)=-1

[]mΤȤ4ˡȤm=4n12ѥˤʤ롣

  • m=4n+1עΡ(m-1)/2=2nעΡ(m-1)/2
  • m=4n-1עΡ(m-1)/2=2n-1עΡ(m-1)/2

p1 (mod 4)ΤȤ(p-1)/2=ꡢ(-1)^{(p-1)/2}ϤĤ1ˤʤ롣

p3 (mod 4)ΤȤ(p-1)/2=ꡢ(-1)^{(p-1)/2}ϤĤ-1ˤʤ롣

[]2佼ˡ§
pǿȤ롣
(\frac{2}{p})~=~(-1)^{\frac{p^2~-~1}{8}}

[ľŪʡ˾]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, a66Ĥοǹ롣
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, a88Ĥοǹ롣
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, a77Ĥοǹ롣
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, a99Ĥοǹ롣
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ˤǤ롣

ʾεϰ̤Ω뤫顢Ωġ

  • [1](p-1)/2ע͡(p+1)/2פΤȤt1=(p-1)/4
  • [2](p-1)/2פΤȤt2=(p+1)/4

ΤȤΤ褦ʼͤ롣

  • [1]\frac{p+1}{2}~t_1~=~\frac{p^2~-~1}{8}
  • [2]\frac{p-1}{2}~t_2~=~\frac{p^2~-~1}{8}
    • \frac{p-1}{2}ϴǤ롣

2Ĥμζt1 or t2ζ˰¸롣
ʤʤС߶ߴǤ뤫顣

椨ˡ\frac{p^2~-~1}{8}ϼĥμˤ뱦դ(-1)߾б롣

[]2佼ˡ§ˤꡢ㤨(2/13)ưפ˲򤯤ȤǤ롣

p=13ΤȤǤꡢ(p^2-1)/8=(169-1)/8=168/8=21=

äơ(2/13)=(-1)^()=-1ˤʤ롣

[]

  • p1 or 7 (mod 8)ΤȤ(2/p)=1
  • p3 or 5 (mod 8)ΤȤ(2/p)=-1

[]8ˡȤȡm=8n1 or 8n5nZˤ4ѥˤʤ롣

  • m=8n1ΤȤ(m2-1)/8=8n22n
  • m=8n5ΤȤ(m2-1)/8=8n210n+3

Ȥǡ2佼ˡ§(\frac{2}{p})~=~(-1)^{\frac{p^2~-~1}{8}}1-1ϡ\frac{p^2~-~1}{8}ζ˰¸롣

pϴǿmʤΤǡ\frac{p^2~-~1}{8}ζ\frac{m^2~-~1}{8}ζȰפ롣

[]ηϤ´Ƥߤ롣2佼ˡ§(2/13)׻Ȥϡ132η׻ɬפǤäȤηϤȤp=135 (mod 8)ꡢ(2/13)=-1Ȥ狼롣

ʿ;ˡ§

Ĥ(ǿ/p)Ĵ٤ѤΤߤǤ롣ϡʿ;Ρˡ§ȸƤФѤ뤳ȤǼ¸Ǥ롣ˡ§ΤҤȤĤλȸƤꡢˡ§ȯȤƶŸ줿

ˡ§ϥ顼ˤ굢ǼŪ˼졢ʾϥˤäͿ줿ˡ§ξϤ¸ߤ1ˤʤäƤۤɤǤ롣

ǤϤޤˡ§μĥҲ𤹤롣

[]ʿ;ˡ§
p,qۤʤ
(\frac{p}{q})(\frac{q}{p})~=~(-1)^{{\frac{p-1}{2}}{\frac{q-1}{2}}}
ϼΤ褦ˤ롣

  • p1 q1 (mod 4)ΤȤ(p/q)(q/p)=1
  • p3 q3 (mod 4)ΤȤ(p/q)(q/p)=-1

[](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'϶Ǥ

äơΤ褦˼ĥΩġ

(\frac{q}{p})~(\frac{p}{q})
=(-1)^{t_1~+~t_2}
=(-1)^{\frac{p-1}{2}~\frac{q-1}{2}~-~\triangle~2EFF'}
=(-1)^{\frac{p-1}{2}~\frac{q-1}{2}}

Ⱦ줿

ϸȾ򼨤ϻѷ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

ʸ

  • ؤʤäȤ륪顼ȥեޡ