WikiSysop: bnz

2022-03-23T02:48:49Z

bnz

←Starija inačica		Inačica od 23. ožujak 2022. u 02:48
Redak 1:		Redak 1:
	~~<!--'''Kvadratni ostatak'''-->'''~~Kvadratni ostatak''' po [[Modularna aritmetika\|modulu]] <math>n</math> je neki [[cijeli broj]] <math>a</math> ako vrijedi <math>M(a, n) = 1 </math> i ako [[kongruencija]] <math>x^2 \equiv a \pmod n </math> ima rješenja, tj. ako postoji cijeli broj <math>x</math> čiji je kvadrat kongruentan s <math>a.</math>		Kvadratni ostatak''' po [[Modularna aritmetika\|modulu]] <math>n</math> je neki [[cijeli broj]] <math>a</math> ako vrijedi <math>M(a, n) = 1 </math> i ako [[kongruencija]] <math>x^2 \equiv a \pmod n </math> ima rješenja, tj. ako postoji cijeli broj <math>x</math> čiji je kvadrat kongruentan s <math>a.</math>

	U suprotnom kažemo da je <math>a</math> kvadratni neostatak modulo <math>n.</math> Uočimo da ako imamo neki <math> m \in \mathbb{Z} </math> takav da je <math>M(m, n) > 1 </math> tada <math>m</math> nije niti kvadratni ostatak niti kvadratni neostatak, a takav je primjerice broj [[nula]]. Uočimo zato da broj <math>x</math> također mora biti [[Prosti broj\|relativno prost]] s <math>n.</math><ref>Andrej Dujella, Teorija brojeva, Školska knjiga, Zagreb, 2019.</ref>		U suprotnom kažemo da je <math>a</math> kvadratni neostatak modulo <math>n.</math> Uočimo da ako imamo neki <math> m \in \mathbb{Z} </math> takav da je <math>M(m, n) > 1 </math> tada <math>m</math> nije niti kvadratni ostatak niti kvadratni neostatak, a takav je primjerice broj [[nula]]. Uočimo zato da broj <math>x</math> također mora biti [[Prosti broj\|relativno prost]] s <math>n.</math><ref>Andrej Dujella, Teorija brojeva, Školska knjiga, Zagreb, 2019.</ref>

WikiSysop: Bot: Automatski unos stranica

2021-12-11T09:46:03Z

Bot: Automatski unos stranica

Nova stranica

'''Kvadratni ostatak''' po [[Modularna aritmetika|modulu]] <math>n</math> je neki [[cijeli broj]] <math>a</math> ako vrijedi <math>M(a, n) = 1 </math> i ako [[kongruencija]] <math>x^2 \equiv a \pmod n </math> ima rješenja, tj. ako postoji cijeli broj <math>x</math> čiji je kvadrat kongruentan s <math>a.</math>

U suprotnom kažemo da je <math>a</math> kvadratni neostatak modulo <math>n.</math> Uočimo da ako imamo neki <math> m \in \mathbb{Z} </math> takav da je <math>M(m, n) > 1 </math> tada <math>m</math> nije niti kvadratni ostatak niti kvadratni neostatak, a takav je primjerice broj [[nula]]. Uočimo zato da broj <math>x</math> također mora biti [[Prosti broj|relativno prost]] s <math>n.</math><ref>Andrej Dujella, Teorija brojeva, Školska knjiga, Zagreb, 2019.</ref>

Veliki [[Matematika|matematičari]] poput [[Pierre de Fermat|Fermata]], [[Leonhard Euler|Eulera]], [[Joseph Louis Lagrange|Lagrangea]], [[Adrien-Marie Legendre|Legendrea]] (i mnogih drugih) su u [[17. stoljeće|17.]] i [[18. stoljeće|18. stoljeću]] iznijeli neke [[teorem]]e o kvadratnim ostatcima. Ipak, prvi koji ih je sistematično proučavao bio je [[Carl Friedrich Gauss]] u svojem čuvenom djelu ''Disquisitiones Arithmeticae'' izdanom [[1801.]]

== Pronalazak rješenja u reduciranom sustavu ostataka ==

Jasno je da za provjeriti je li neki broj <math>a</math> kvadratni ostatak modulo <math>n</math> dovoljno je naći njegov ostatak pri [[Množenje|dijeljenju]] s <math>n</math> u ''reduciranom sustavu ostataka'' modulo <math>n</math> i vidjeti je li kvadrat nekog od brojeva u tom skupu kongruentan s <math>a.</math>

Isto tako, kongruencija <math>x^2 \equiv (x + kn)^2 \pmod n</math> je trivijalno zadovoljena pa će biti dovoljno promatrati skup relativno prostih brojeva s <math>n</math> u intervalu <math>[1, n - 1]</math> jer je <math>(1, n) = (n - 1, n) = 1.</math>

== Kvadratni ostatci po prostom modulu ==
Kvadratni ostatci modulo <math>p</math> gdje je <math>p > 2</math> prost broj poštuju određena jednostavna svojstva.

Ako želimo naći sve kvadratne ostatke modulo <math>p</math> dovoljno je izlistati kvadratne ostatke po modulu <math>p</math> iz skupa <math>\{1, 2, ..., p - 1\}.</math>

Dokazat ćemo da u tom skupu ima točno <math>\frac{p - 1}{2}</math> kvadratnih ostataka. Pitamo se koliko kvadratnih ostataka postižu brojevi <math>1^2, 2^2, ..., (p - 1)^2.</math> Uočimo da vrijedi <math>x^2 \equiv (p - x)^2 \pmod p </math> pa se svaki kvadratni ostatak pastiže barem dva puta (jer očito <math>x \neq p - x</math>). Treba dokazati da se postižu točno dva puta.

U tu svrhu, pretpostavimo da je <math>x^2 \equiv y^2 \pmod p.</math> Tada <math>p|(x - y)(x + y)</math> pa prema ''Euklidovoj lemi'' slijedi <math>p|x - y </math> ili <math>p|x + y.</math> No kako su <math>x, y \in \{1, 2, ..., p - 1\}</math> slijedi <math>x = y</math> ili <math> x + y = p</math> pa se kvadratni ostatak postiže točno dva puta.

=== Broj rješenja čiste kvadratne kongruencije ===

Neka je <math>p</math> prost i <math>a</math> neki cijeli broj.

Koristeći sada [[Legendreov simbol]], broj rješenja kongruencije <math>x^2 \equiv a \pmod p </math> jednak je <math>1 + \left(\frac{a}{p}\right)</math>.

Naime, ako je <math>a</math> kvadratni ostatak, tada kongruencija ima 2 rješenja (ako je jedno rješenje <math>x_0</math>, drugo rješenje je <math>-x_0</math>). Ako je pak
<math>a</math> kvadratni neostatak, onda kongruencija nema rješenja, a ako <math>p|a</math> kongruencija ima točno jedno rješenje modulo <math>p</math>, tj. sve brojeve kongruente <math>0</math> modulo <math>p</math>.

=== Eulerov kriterij ===
Ovaj se [[teorem]] prvi puta pojavljuje u [[Leonhard Euler|Eulerovim]] radovima iz [[1748.]]

Teorem tvrdi <math>a^{\frac{p - 1}{2}} \equiv \left(\frac{a}{p}\right) \pmod p.</math>

Naime, ako <math>p</math> dijeli <math>a</math> tvrdnja očigledno vrijedi. Zato prijeđimo na slučaj kada <math>p</math> ne dijeli <math> a. </math>

Ako je <math> a </math> kvadratni ostatak modulo <math> p </math>, po definiciji postoji cijeli broj <math> x </math> takav da je <math> x^2 \equiv a \pmod p </math> pa budući da <math> x </math> nije djeljiv s <math> p </math>, tada niti <math>x^2</math> nije djeljiv s <math>p.</math> Prema [[Eulerov teorem|Malom Fermatovom teoremu]] lagano slijedi <math>a^{\frac{p - 1}{2}} \equiv (x^2)^{\frac{p - 1}{2}} \equiv x^{p - 1} \equiv 1 \pmod p</math> pa tvrdnja u ovom slučaju vrijedi.

Slično se pokazuje ako <math> a </math> nije kvadratni ostatak modulo <math> p. </math> Nije teško dokazati da za svaki <math> x \in S = \{1, 2, ..., p - 1\} </math>
postoji jedinstveni <math> y \in S </math> takav da je <math> xy \equiv a \pmod p </math>.<ref>Za dokaz, preporuča se pogledati dokaz leme u članku o [[Wilsonov teorem|Wilsonovom teoremu]]</ref>
Naime, ova tvrdnja slijedi iz [[Bezoutov identitet|Bézoutovog identiteta]].

Dalje, prema pretpostavci, <math> a </math> nije kvadratni ostatak modulo <math>p</math> pa vrijedi <math> x \neq y. </math> Promotrimo li sve takve parove oblika <math> (x, y) </math> vidimo da smo skup <math>S</math> podijelili na <math> \frac{p - 1}{2}</math> parova ostataka koji u umnošku daju <math> a </math> modulo <math> p. </math> Koristeći još [[Wilsonov teorem]] zaključujemo da vrijedi <math>a^{\frac{p - 1}{2}} \equiv 1 \cdot 2 \cdot ... \cdot (p - 1) \equiv - 1 \pmod p, </math> čime je Eulerov kriterij dokazan.

== Gaussov kvadratni zakon reciprociteta ==
Kvadratni zakon reciprociteta je jedan od najdubljih rezultata [[Teorija brojeva|elementarne teorije brojeva]] i jedan je od teorema s najviše poznatih [[dokaz]]a, a tvrdi da za dva različita [[Parnost broja|neparna]] prosta broja <math>p, q </math> vrijedi
<math> \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}.</math>

Kao korak u nekim dokazima ovog teorema se često koristi poznata [[Gaussova lema]].

==Izvori==
{{izvori}}

[[Kategorija:Teorija brojeva]]

Kvadratni ostatak - Povijest promjena

WikiSysop: bnz

WikiSysop: Bot: Automatski unos stranica