WikiSysop: Zamjena teksta - ''' u ''

2025-05-29T11:09:08Z

Zamjena teksta - ''' u ''

←Starija inačica		Inačica od 29. svibanj 2025. u 11:09
Redak 1:		Redak 1:
	~~<!--'''Gaussova lema'''-->'~~''Gaussova lema''' je [[teorem]] u [[Teorija brojeva\|elementarnoj teoriji brojeva]] koji daje uvjet za provjeru je li neki [[Prirodni broj\|prirodni]] broj [[potpuni kvadrat]] ili nije.		''Gaussova lema''' je [[teorem]] u [[Teorija brojeva\|elementarnoj teoriji brojeva]] koji daje uvjet za provjeru je li neki [[Prirodni broj\|prirodni]] broj [[potpuni kvadrat]] ili nije.

	Prvi se puta spominje u radovima velikog [[Njemačka\|njemačkog]] [[Matematika\|matematičara]] [[Carl Friedrich Gauss\|Carla Friedricha Gaussa]] još [[1808.]] godine kao treći [[Matematički dokaz\|dokaz]] ''Kvadratnog zakona reciprociteta''.		Prvi se puta spominje u radovima velikog [[Njemačka\|njemačkog]] [[Matematika\|matematičara]] [[Carl Friedrich Gauss\|Carla Friedricha Gaussa]] još [[1808.]] godine kao treći [[Matematički dokaz\|dokaz]] ''Kvadratnog zakona reciprociteta''.

WikiSysop: Bot: Automatski unos stranica

2021-12-11T17:00:07Z

Bot: Automatski unos stranica

Nova stranica

'''Gaussova lema''' je [[teorem]] u [[Teorija brojeva|elementarnoj teoriji brojeva]] koji daje uvjet za provjeru je li neki [[Prirodni broj|prirodni]] broj [[potpuni kvadrat]] ili nije.

Prvi se puta spominje u radovima velikog [[Njemačka|njemačkog]] [[Matematika|matematičara]] [[Carl Friedrich Gauss|Carla Friedricha Gaussa]] još [[1808.]] godine kao treći [[Matematički dokaz|dokaz]] ''Kvadratnog zakona reciprociteta''.

== Iskaz leme ==
Za proizvoljni neparni [[prosti broj]] <math>p</math> neka je <math>a</math> prirodni broj relativno prost s <math>p.</math>

Promotrimo [[skup]] <math>S = \{a, 2a, 3a, ..., \frac{p - 1}{2}a\}.</math> Isto tako, promotrimo skup <math>S'</math> najmanjih pozitivnih ostataka modulo <math> p </math> koji daju elementi prvobitnog skupa <math>S.</math>

Neka je <math>n</math> broj elemenata skupa <math>S'</math> koji su veći od <math>\frac{p}{2}.</math>

Tada je <math>\left(\frac{a}{p}\right) = (-1)^n,</math>
gdje je <math>\left(\frac{a}{p}\right)</math> [[Legendreov simbol]].<ref>Andrej Dujella, Teorija brojeva, Školska knjiga, Zagreb, 2019.</ref>

== Dokaz ==
Označimo s <math>r_1, r_2, ..., r_n</math> elemente skupa <math>S = \{a, 2a, ..., \frac{p - 1}{2}a\}</math> koji su veći od
<math>\frac{p}{2}</math> te sa <math>s_1, s_2, ..., s_k</math> elemente skupa
<math>S</math> koji su manji od
<math>\frac{p}{2}</math>. Očito je
<math>n + k = \frac{p - 1}{2}.</math>

Kako su <math>r_i</math> međusobno različiti<ref>Obrazloženje ove tvrdnje ekvivalentno je dokazu leme u članku o [[Eulerov teorem|Eulerovom teoremu]]</ref>, slijedi da su i brojevi <math>p - r_i</math> međusobno različiti. Uz to, vrijedi <math>0 < p - r_i < \frac{p}{2}</math> za <math>i = 1, 2, ..., n</math>.

Također, nijedan
<math>p - r_i</math> nije jednak nekom <math>s_j</math>. Naime, ako ako je <math>p - r_i = s_j</math>,
iz <math>r_i \equiv \alpha a \pmod p, s_j \equiv \beta a \pmod p</math> bi
slijedilo <math>a(\alpha + \beta) \equiv 0 \pmod p </math>, što nije moguće.

Prema tome, brojevi <math>p - r_1, p - r_2, ..., p - r_n</math> te
<math>s_1, s_2, ..., s_k</math> su svi međusobno različiti, ima ih <math>\frac{p - 1}{2}</math> i elementi su skupa <math>S = \{1, 2, ..., \frac{p - 1}{2}.</math> Zato su to upravo brojevi <math>1, 2, ..., \frac{p - 1}{2}</math> u nekom poretku.

Množeći ih, dobivamo da je
<math>(\frac{p - 1}{2})! \equiv (p - r_1)...(p - r_n)s_1...s_k \pmod p,</math> odnosno <math>(\frac{p - 1}{2})! \equiv (- 1)^na^{\frac{p - 1}{2}}(\frac{p - 1}{2})! \pmod p</math> iz čega kraćenjem i korištenjem [[Kvadratni ostatak|Eulerovog kriterija]] slijedi traženi rezultat.<ref>https://crypto.stanford.edu/pbc/notes/numbertheory/gausslemma.html</ref>

== Veza s MFT ==
=== Intuicija i glavne ideje ===
Laički rečeno, Gaussova lema na dva načina računa umnožak <math>a \cdot 2a \cdot ... \cdot \frac{(p - 1)}{2}a</math>. Ovaj umnožak nas podsjeća na nadaleko poznati [[Eulerov teorem|Mali Fermatov teorem]] (MFT). I ova lema je u mnogočemu slična s njime, samo se u njoj dakle bavimo dvama načinima gledanja na jedan te isti skup <math>S = \{a, 2a, ..., (p - 1)a\}</math>, odnosno na umnožak prve polovice njegovih elemenata, tj. elemente <math>a, 2a, ..., \frac{p - 1}{2}a</math>. Razlog tomu je što ćemo drugu polovicu (odnosno elemente <math>\frac{p + 1}{2}a, ..., (p - 1)a</math>) koristiti kao negacije elemenata iz prve polovice jer vrijedi <math>k \equiv p - k \pmod p</math> za svaki <math>k \in \mathbb{Z}</math>. (1)

Pri tome ćemo također, na prirodan način, elemente razvrstati po tome jesu li njihovi ostatci pri dijeljenju s <math>p</math> veći ili manji od
<math>\frac{p}{2}</math>.

Dakle, jednostavno svojstvo (1) će nam omogućiti računanje na način drugačiji od načina korištenog u MFT iz čega ćemo komputacijom i Eulerovim kriterijom dobiti traženi rezultat.

===Primjer===
Uzmimo <math>p = 7, a = 4</math>.

Dakle, imamo skup <math>S = \{1, 2, 3, 4, 5, 6\} </math> te novonastali skup <math>S' = \{4, 8, 12, 16, 20, 24\}</math>. Elementi od <math>S'</math> redom daju ostatke <math>4, 1, 5, 2, 6, 3</math> pri dijeljenju sa 7. Ovo nam je dobro poznato iz leme korištene u dokazu [[Eulerov teorem|Eulerovog teorema]].

Pri tome je, kako je već rečeno, <math>3 \equiv 7 - 4, 1 \equiv 7 - 6, 5 \equiv 7 - 2 \pmod 7.</math> Zato ćemo promatrati samo prvu polovicu skupa <math>S'</math>, tj. skup <math>\{4, 8, 12\}</math> jer je druga samo negacija prve modulo 7.
Vidimo da ostatci koji daju ovi brojevi nisu posebno omeđeni, tj. neki su veći od <math>\frac{7}{2}</math>, a neki su manji od tog broja.

Ako promotrimo neki ostatak <math>r > \frac{7}{2}</math> (npr. <math>4</math>) očito će njegova negacija, <math>7 - r </math> (dakle <math>3</math>) biti manja od <math>\frac{p}{2}</math> i pripadat će drugoj polovici skupa
<math>S</math>.

No, evidentno taj <math> 7 - r </math> neće biti jednak nijednom elementu manjem od <math>\frac{7}{2}</math> u prvoj polovici skupa <math>S</math>. (Posve analogno ako promatramo brojeve manje od <math>\frac{7}{2}</math>.)

Sada imamo <math>r_1 = 4, r_2 = 5, s_1 = 1 </math>.

Dakle, brojeva <math>7 - r_1 = 3, 7 - r_2 = 2, s_1 = 1</math> ima <math>\frac{7 - 1}{2} = 3</math>, međusobno su nekongruenti modulo 7 i daju iste ostatke kao <math>4, 8, 12 </math> u nekom poretku.

(U formalnom dokazu je rečeno da brojevi <math>p - r_1, p - r_2,..., p - r_n, s_1, s_2, ..., s_k</math> daju iste ostatke kao <math>a, 2a, ..., \frac{p - 1}{2}a</math>.)

Zato su dva umnoška iz formalnog dokaza jednaka iz čega se lako dobiva tvrdnja leme.

==Izvori==
{{izvori}}

[[Kategorija:Matematika]]

Gaussova lema - Povijest promjena

WikiSysop: Zamjena teksta - ''' u ''

WikiSysop: Bot: Automatski unos stranica