Element pierwotny

Zbiór wzorów, definicji i najczęściej poruszanych problemów z Algebry.
xiikzodz
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 4 paź 2008, o 02:13
Płeć: Kobieta
Lokalizacja: Lost Hope

Element pierwotny

Post autor: xiikzodz » 7 gru 2008, o 04:01

Mowa o pewnym elementarnym, lecz pomocnym uogolnieniu malego twierdzenia Fermata. Ustalmy liczbe pierwsza \(p\). Symbolem \(\mathbb{Z}_p^*\) oznaczmy zbior \(\{1,...,p-1\}\). Rzedem liczby \(a\in\mathbb{Z}_p^*\) nazwiemy najmniejsza liczbe naturalna \(m\) taka, ze: \(a^m\equiv 1\mbox{ mod }p\). Na mocy malego twierdzenia Fermata rzad isnieje i jest niewiekszy od \(p-1\). Zachodzi: \(\boxed{\mbox{ Twierdzenie: W zbiorze }\mathbb{Z}_p^* \mbox{ istnieje liczba rz\c edu } p-1.}\) Liczbe, ktorej istnienie wynika z powyzszego twierdzenia, nazywamy elementem pierwotnym modulo \(p\). Zeby dowod przeprowadzic calkiem elementarnie, potrzebne sa pewne przygotowania: Niech \(w(x)\) bedzie wielomianem o wspolczynnikach calkowitych. Liczbe \(t\) ze zbioru \(\{0,1,...,p-1\}\) taka, ze: \(w(r)\equiv 0\mbox{ mod }p\) nazwiemy pierwiastkiem wielomianu \(w(x)\) modulo \(p\). Zachodzi: Twierdzenie ("Bezout"): Jesli \(w(x)\) jest wielomianem o wspolczynnikach calkowitych, zas \(t\) jego pierwiastkiem modulo \(p\), wowczas istnieje dokladnie jeden wielomian o wspolczynnikach calkowitych \(v(x)\) taki, ze \(w(x)=(x-t)v(x)\).
    Dowod (w skrocie): Reszta z dzielenia wielomianu \(w(x)\) przez jednomian \(x-t\) jest wielomianem stopnia \(0\), czyli liczba calkowita, ktora oznczymy \(r\). Mamy wiec: \(w(x)=(x-t)v(x)+r\) dla pewnego wielomianu \(v(x)\) o wspolczynnikach calkowitych. Skad: \(0=w(t)=(t-t)v(x)+r=0+r\), czyli \(r=0\) co konczy dowod.
Wniosek: Wielomian (o wspolczynnikach calkowitych) stopnia \(m\) ma co najwyzej \(m\) pierwiastkow modulo \(p\).
    Dowod: Natychmiastowy przez indukcje ze wzgledu na stopien wielomianu.
Mozemy teraz przystapic do pokazania glownego twierdzenia: Niech \(a_m\) oznacza liczbe elementow rzedu \(m\) w zbiorze \(\mathbb{Z}_p^*\). Zatem \(a_m=0\), gdy \(m\) nie jest dzielnikiem liczby \(p-1\) (MFT). Jesli pewien element \(x\) ma rzad \(m\), czyli \(x^m\equiv 0\mbox{ mod }p\), to elementy \(x^0,x^1,x^2,...,x^{m-1}\) sa wszystkimi, na mocy wniosku powyzej, pierwiastkami modulo \(p\) wielomianu \(x^m-1\). Co wiecej, dla kazdej liczby \(k\) wzglednie pierwszej z \(m\) liczba \(x^k\) ma rzad \(m\). Elementow rzedu \(m\) zbiorze \(\mathbb{Z}_p^*\) jest zatem dokladnie \(\varphi(m)\). Stad: \(\sum_{m}\varphi(m)=p-1\) gdzie suma przebiega wszystkie mozliwe rzedy elementow \(\mathbb{Z}_p^*\). Wiemy jednak, ze \(p-1=\sum_{d|p-1}\varphi(d)\) zatem te dwie sumy moga byc rowne wtedy i tylko wtedy, gdy \(m=p-1\) jest rzedem pewnego elementu. Tym samym dowod zostal zakonczony. Uwaga: Z rozumowania powyzej wynika, ze elementow pierwotnych modulo \(p\) jest dokladnie \(\varphi(p-1)\).
    Przyklad zastosowania. Pokazemy, ze dla kazdej liczby pierwszej \(p\) wiekszej od \(3\) i dla kazdej liczby \(b\) wzglednie pierwszej z \(p\) istnieje permutacja \(\sigma:\{1,2,...,p-1\}\to\{1,2,...,p-1\}\) taka, ze: \(\sum_{i=1}^{p-1}b^{i-1}\sigma(i)\equiv 0\mbox{ mod }p\) Dowod: Niech \(\xi\) bedzie elementem pierwotnym modulo \(p\). Polozmy: \(\sigma(i)=\xi^{i-1}\mbox{ mod }p\) Jest to dobrze okreslona permutacja, bo potegi elementu pierwotnego przebiegaja wszystkie liczby zbioru \(\{1,2,...,p-1\}\). Mamy wowczas: \(\sum_{i=1}^{p-1}\xi^{i-1}\sigma(i) \equiv \sum_{i=1}^{p-1}\sigma(i)\sigma(i) \equiv\sum_{i=1}^{p-1}i^2\equiv\frac{p(p-1)(2p-1)}{6}\equiv 0\mbox{ mod }p\) o ile \(p>3\). Przez indukcje po \(m\), korzystajac ze wzoru: \(\frac{\xi^{m(i-1)}-\xi^{i-1}}{\xi^{i-1}-1}=\xi^{i-1}+\xi^{2(i-1)}+...+\xi^{(m-1)(i-1)}\) otrzymujemy: \(\sum_{i=1}^{p-1}\xi^{m(i-1)}\sigma(i)\equiv \sum_{i=1}^{p-1}\xi^{i-1}\sigma(i)\mbox{ mod }p\) Jesli wiec dobierzemy \(m\) takie, ze \(\xi^m=b\), to otrzymujemy: \(\sum_{i=1}^{p-1}b^{i-1}\sigma(i)\equiv\sum_{i=1}^{p-1}\xi^{m(i-1)}\sigma(i)\equiv 0\mbox{ mod }p\), Co nalezalo pokazac.

ODPOWIEDZ