Najlepša hvala, vse jasno, samo težko se je spomnit
Nekaj v zvezi s teorijo.
Naj bo
\(p \in \mathb{P}, p>=3\).
\(p=x^2+y^2, x,y \in \mathb{Z}\). Po modulu p:
\(x^2+y^2=0(mod p)\). x,y tuja proti p, torej obrnljiva v
\(\mathb{Z}_p^*\),
\(\mathb{Z}_p^*\) je reduciran sistem ostankov. Vpr.: zakaj sta obrnljiva?
Dokaz naslednje trditve in posledice mi res ni ravno jasen. Kako smo si pomagali z ekvivalenčnimi razredi?
Trditev: Naj bo
\(p \in \mathb{P}\). Za enačbo
\(x^2=-1(mod p)\) velja:
1. če je p=2 ima eno rešitev
2. če je p=1(mod 4) ima dve rešitvi
3. če je p=3(mod 4) nima rešitve.
Dokaz:(2.,3.)
Na množici
\(\mathb{Z}_p^*\) uvedemo ekvivalenčno relacijo kot najmanjšo tisto, pri kateri so ekvivalentni
\(x, -x,x^{-1}, -x^{-1}\).
Tipičen ekviv. razred ima 4 elemente
\(\{x, -x,x^{-1}, -x^{-1}\}\). Izjemni ekviv. razredi so tisti, ko kakšne točke sovpadajo:
a)
\(x=x^{-1}(mod p)=>\)
\(x^2=1(mod p)=>x^2-1=0(mod p)\)
\(x=1(mod p) in x=-1 (mod p)\). Dobimo en dvoelem. ekviv. razred
\(\{1,p-1\}\). Kako smo ga dobili?
b)
\(x=-x^{-1}(mod p)=> x^2=-1(mod p)\). Ta enačba lahko nima rešitev, ali ima največ 2 rešitvi, ker je st. 2 in je
\(p\in \mathb{P}\)
Če ima eno rešitev m, potem je tudi -m rešitev(zakaj? ali zato ker imamo
\(x^2\)), dobimo še en ekviv. razred
\(\{m,-m\}\). Vsi ekviv. razredi določajo dekompozicijo
\(\mathb{Z}_p^*\) na podmnožico moči 4, eno moči 2 in morda še eno moči 2.
Dokaz za 2.:
če je
\(p=1(mod 4)=> p-1=0(mod 4)\),
\(4|p-1\) zato morata obstajati dva ekviv. razreda moči 2. Torej ima enačba
\(x^2=-1 (mod p)\) dve rešitvi (zakaj?)
Dokaz za 3.:
če je
\(p=3(mod 4)\) =>
\(p-1=2(mod 4)\) in v
\(\mathb{Z}_p^*\) je le en ekviv. razred moči 2(zakaj?), zato
\(x^2=-1(mod p)\) nima rešitve(zakaj?).
Posledica:
Če je
\(n=x^2+y^2, x,y \in \mathb{Z}\) in
\(p=3(mod 4 )\) deli n, potem
\(p^2\) deli n.
Dokaz:
p|n =>
\(x^2+y^2=0(mod p)\). Trdimo, da je p|x in p|y. Recimo, da p ne deli x,potem im x inverz modulo p in sledi, da imamo rešitev za kongruenco
\(z^2=-1(mod p)\)(zakaj?). To vemo, da po zg. trditvi ne velja, torej p|x in
\(p^2|x^2\) ter
\(p^2|y^2\)=>
\(p^2|x^2+y^2\).
Kdo razume?