Lemat Gaussa (teoria liczb)

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Lemat Gaussa w teorii liczb zadaje warunki, które musi spełniać liczba całkowita, aby była resztą kwadratową. Pierwszy raz użył go Carl Friedrich Gauss w dowodzie prawa wzajemności reszt kwadratowych.

Treść lematu[edytuj | edytuj kod]

Dla dowolnej nieparzystej liczby pierwszej p niech a będzie względnie pierwsze z p.

Rozważmy liczby:

a, 2a, 3a, \dots, \frac{p-1}{2}a

i ich reszty modulo p. (wszystkie reszty są różne, więc jest ich \frac{p-1}{2})

Niech n będzie liczbą tych reszt które są większe niż \frac{p}{2}. Wtedy

\left(\frac{a}{p}\right) = (-1)^n

gdzie \left(\frac{a}{p}\right) jest symbolem Legendre'a.

Dowód[edytuj | edytuj kod]

Dowód[1] można przeprowadzić elementarnymi metodami porównując wartość wyrażenia

Z=a \cdot 2a \cdot 3a \cdot \cdots \cdot \frac{p-1}{2}a

modulo p liczoną dwoma sposobami. Z jednej strony mamy

Z=a^{(p-1)/2} \left(1 \cdot 2 \cdot 3 \cdot \cdots \cdot \frac{p-1}2 \right)

Do policzenia wartości Z innym sposobem na potrzeby dowodu definiujemy wartość |x| jako

|x| = \begin{cases} x & \mbox{gdy } 1 \leqslant x \leqslant \frac{p-1}2, \\ -x & \mbox{gdy } \frac{p+1}2 \leqslant x \leqslant p-1. \end{cases}

Skoro n zlicza wielokrotności ka dla k=1,2,3,\cdots,\frac{p-1}{2} których reszty modulo p należą do drugiego warunku definicji, zaś wtedy reszty modulo p z wielokrotności -ka są pod pierwszym warunkiem, mamy

Z = (-1)^n \left(|a| \cdot |2a| \cdot |3a| \cdot \cdots \cdots \left|\frac{p-1}2 a\right|\right).

Zauważmy teraz że wartości reszt ka modulo p są parami różne dla k=1,2,3,\cdots,\frac{p-1}{2}.

Istotnie, jeśli |pa|=|qa|, dla p\neq q, wtedy pa=\pm qa, czyli p=\pm q, więc

p=q, bo p,q większe od 1 i mniejsze od \frac{p-1}{2}, ale reszt jest

dokładnie \frac{p-1}{2}, więc muszą one być permutacją zbioru 1,2,\cdots,\frac{p-1}{2}. Zatem

Z = (-1)^n \left(1 \cdot 2 \cdot 3 \cdot \cdots \cdot \frac{p-1}2\right).

Porównując to z pierwszym rezultatem i skracając przez 1 \cdot 2 \cdot 3 \cdot \cdots \cdot \frac{p-1}{2} otrzymując

a^{\frac{p-1}{2}} = (-1)^n.

Co kończy dowód na podstawie kryterium Eulera, gdyż lewa strona jest alternatywnym sposobem na wyrażenia symbolu Legendre'a.

Przykład[edytuj | edytuj kod]

Dobierając p=11 and a=7, ciąg liczb to:

7, 14, 21, 28, 35.

Po przeprowadzeniu dzielenia modulo 11 otrzymujemy reszty:

7, 3, 10, 6, 2.

Trzy z nich są większe od \frac{11}{2}, więc n=3. Z lematu otrzymujemy, że

\left(\frac{7}{11}\right)=(-1)^3=-1.

Co istotnie jest prawdą, ponieważ 7 nie jest resztą kwadratową modulo 11.

Przypisy

  1. Any textbook on elementary number theory will have a proof. The one here is basically Gauss's from "Neuer Beweis eines arithnetischen Satzes"; pp 458-462 of Untersuchungen uber hohere Arithmetik