Gaussova lema

Gaussova lema je teorem u elementarnoj teoriji brojeva koji daje uvjet za provjeru je li neki prirodni broj potpuni kvadrat ili nije.

Prvi se puta spominje u radovima velikog njemačkog matematičara Carla Friedricha Gaussa još 1808. godine kao treći dokaz Kvadratnog zakona reciprociteta.

Iskaz leme

Za proizvoljni neparni prosti broj [math]\displaystyle{ p }[/math] neka je [math]\displaystyle{ a }[/math] prirodni broj relativno prost s [math]\displaystyle{ p. }[/math]

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

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

Tada je [math]\displaystyle{ \left(\frac{a}{p}\right) = (-1)^n, }[/math] gdje je [math]\displaystyle{ \left(\frac{a}{p}\right) }[/math] Legendreov simbol.

Dokaz

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

Kako su [math]\displaystyle{ r_i }[/math] međusobno različiti, slijedi da su i brojevi [math]\displaystyle{ p - r_i }[/math] međusobno različiti. Uz to, vrijedi [math]\displaystyle{ 0 \lt p - r_i \lt \frac{p}{2} }[/math] za [math]\displaystyle{ i = 1, 2, ..., n }[/math].

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

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

Množeći ih, dobivamo da je [math]\displaystyle{ (\frac{p - 1}{2})! \equiv (p - r_1)...(p - r_n)s_1...s_k \pmod p, }[/math] odnosno [math]\displaystyle{ (\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 Eulerovog kriterija slijedi traženi rezultat.

Veza s MFT

Intuicija i glavne ideje

Laički rečeno, Gaussova lema na dva načina računa umnožak [math]\displaystyle{ a \cdot 2a \cdot ... \cdot \frac{(p - 1)}{2}a }[/math]. Ovaj umnožak nas podsjeća na nadaleko poznati 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]\displaystyle{ S = \{a, 2a, ..., (p - 1)a\} }[/math], odnosno na umnožak prve polovice njegovih elemenata, tj. elemente [math]\displaystyle{ a, 2a, ..., \frac{p - 1}{2}a }[/math]. Razlog tomu je što ćemo drugu polovicu (odnosno elemente [math]\displaystyle{ \frac{p + 1}{2}a, ..., (p - 1)a }[/math]) koristiti kao negacije elemenata iz prve polovice jer vrijedi [math]\displaystyle{ k \equiv p - k \pmod p }[/math] za svaki [math]\displaystyle{ 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]\displaystyle{ p }[/math] veći ili manji od [math]\displaystyle{ \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]\displaystyle{ p = 7, a = 4 }[/math].

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

Pri tome je, kako je već rečeno, [math]\displaystyle{ 3 \equiv 7 - 4, 1 \equiv 7 - 6, 5 \equiv 7 - 2 \pmod 7. }[/math] Zato ćemo promatrati samo prvu polovicu skupa [math]\displaystyle{ S' }[/math], tj. skup [math]\displaystyle{ \{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]\displaystyle{ \frac{7}{2} }[/math], a neki su manji od tog broja.

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

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

Sada imamo [math]\displaystyle{ r_1 = 4, r_2 = 5, s_1 = 1 }[/math].

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

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

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