szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Kobieta
PostNapisane: 7 gru 2008, o 05:01 
Użytkownik

Posty: 1874
Lokalizacja: Lost Hope
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.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Element odwrotny w ciele - zadanie 6  MowMiGrzesiek  4
 Element wyróżniony  bankierka  1
 Skończony zbiór częściowo uporządkowany - element maksymalny  WeronikaWeronika  7
 Czy element dzieli inny element  blade  3
 element neutralny, pochłaniający  mitsumi140  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl