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
Podziękował: 28 razy
Pomógł: 502 razy

Element pierwotny

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

Mowa o pewnym elementarnym, lecz pomocnym uogolnieniu malego twierdzenia Fermata.

Ustalmy liczbe pierwsza \(\displaystyle{ p}\).

Symbolem \(\displaystyle{ \mathbb{Z}_p^*}\) oznaczmy zbior \(\displaystyle{ \{1,...,p-1\}}\).

Rzedem liczby \(\displaystyle{ a\in\mathbb{Z}_p^*}\) nazwiemy najmniejsza liczbe naturalna \(\displaystyle{ m}\) taka, ze:

\(\displaystyle{ a^m\equiv 1\mbox{ mod }p}\).

Na mocy malego twierdzenia Fermata rzad isnieje i jest niewiekszy od \(\displaystyle{ p-1}\).

Zachodzi:

\(\displaystyle{ \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 \(\displaystyle{ p}\).

Zeby dowod przeprowadzic calkiem elementarnie, potrzebne sa pewne przygotowania:

Niech \(\displaystyle{ w(x)}\) bedzie wielomianem o wspolczynnikach calkowitych. Liczbe \(\displaystyle{ t}\) ze zbioru \(\displaystyle{ \{0,1,...,p-1\}}\) taka, ze:

\(\displaystyle{ w(r)\equiv 0\mbox{ mod }p}\)

nazwiemy pierwiastkiem wielomianu \(\displaystyle{ w(x)}\) modulo \(\displaystyle{ p}\).

Zachodzi:

Twierdzenie ("Bezout"): Jesli \(\displaystyle{ w(x)}\) jest wielomianem o wspolczynnikach calkowitych, zas \(\displaystyle{ t}\) jego pierwiastkiem modulo \(\displaystyle{ p}\), wowczas istnieje dokladnie jeden wielomian o wspolczynnikach calkowitych \(\displaystyle{ v(x)}\) taki, ze \(\displaystyle{ w(x)=(x-t)v(x)}\).
  • Dowod (w skrocie): Reszta z dzielenia wielomianu \(\displaystyle{ w(x)}\) przez jednomian \(\displaystyle{ x-t}\) jest wielomianem stopnia \(\displaystyle{ 0}\), czyli liczba calkowita, ktora oznczymy \(\displaystyle{ r}\). Mamy wiec:

    \(\displaystyle{ w(x)=(x-t)v(x)+r}\)

    dla pewnego wielomianu \(\displaystyle{ v(x)}\) o wspolczynnikach calkowitych. Skad:

    \(\displaystyle{ 0=w(t)=(t-t)v(x)+r=0+r}\),

    czyli \(\displaystyle{ r=0}\) co konczy dowod.
Wniosek: Wielomian (o wspolczynnikach calkowitych) stopnia \(\displaystyle{ m}\) ma co najwyzej \(\displaystyle{ m}\) pierwiastkow modulo \(\displaystyle{ p}\).
  • Dowod: Natychmiastowy przez indukcje ze wzgledu na stopien wielomianu.

Mozemy teraz przystapic do pokazania glownego twierdzenia:

Niech \(\displaystyle{ a_m}\) oznacza liczbe elementow rzedu \(\displaystyle{ m}\) w zbiorze \(\displaystyle{ \mathbb{Z}_p^*}\).

Zatem \(\displaystyle{ a_m=0}\), gdy \(\displaystyle{ m}\) nie jest dzielnikiem liczby \(\displaystyle{ p-1}\) (MFT).

Jesli pewien element \(\displaystyle{ x}\) ma rzad \(\displaystyle{ m}\), czyli

\(\displaystyle{ x^m\equiv 0\mbox{ mod }p}\),

to elementy \(\displaystyle{ x^0,x^1,x^2,...,x^{m-1}}\) sa wszystkimi, na mocy wniosku powyzej, pierwiastkami modulo \(\displaystyle{ p}\) wielomianu \(\displaystyle{ x^m-1}\).

Co wiecej, dla kazdej liczby \(\displaystyle{ k}\) wzglednie pierwszej z \(\displaystyle{ m}\) liczba \(\displaystyle{ x^k}\) ma rzad \(\displaystyle{ m}\).

Elementow rzedu \(\displaystyle{ m}\) zbiorze \(\displaystyle{ \mathbb{Z}_p^*}\) jest zatem dokladnie \(\displaystyle{ \varphi(m)}\).

Stad:

\(\displaystyle{ \sum_{m}\varphi(m)=p-1}\)

gdzie suma przebiega wszystkie mozliwe rzedy elementow \(\displaystyle{ \mathbb{Z}_p^*}\).

Wiemy jednak, ze

\(\displaystyle{ p-1=\sum_{d|p-1}\varphi(d)}\)

zatem te dwie sumy moga byc rowne wtedy i tylko wtedy, gdy \(\displaystyle{ m=p-1}\) jest rzedem pewnego elementu. Tym samym dowod zostal zakonczony.

Uwaga: Z rozumowania powyzej wynika, ze elementow pierwotnych modulo \(\displaystyle{ p}\) jest dokladnie \(\displaystyle{ \varphi(p-1)}\).
  • Przyklad zastosowania. Pokazemy, ze dla kazdej liczby pierwszej \(\displaystyle{ p}\) wiekszej od \(\displaystyle{ 3}\) i dla kazdej liczby \(\displaystyle{ b}\) wzglednie pierwszej z \(\displaystyle{ p}\) istnieje permutacja \(\displaystyle{ \sigma:\{1,2,...,p-1\}\to\{1,2,...,p-1\}}\) taka, ze:

    \(\displaystyle{ \sum_{i=1}^{p-1}b^{i-1}\sigma(i)\equiv 0\mbox{ mod }p}\)


    Dowod: Niech \(\displaystyle{ \xi}\) bedzie elementem pierwotnym modulo \(\displaystyle{ p}\). Polozmy:

    \(\displaystyle{ \sigma(i)=\xi^{i-1}\mbox{ mod }p}\)

    Jest to dobrze okreslona permutacja, bo potegi elementu pierwotnego przebiegaja wszystkie liczby zbioru \(\displaystyle{ \{1,2,...,p-1\}}\).

    Mamy wowczas:

    \(\displaystyle{ \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 \(\displaystyle{ p>3}\).

    Przez indukcje po \(\displaystyle{ m}\), korzystajac ze wzoru:

    \(\displaystyle{ \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:

    \(\displaystyle{ \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 \(\displaystyle{ m}\) takie, ze \(\displaystyle{ \xi^m=b}\), to otrzymujemy:

    \(\displaystyle{ \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.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

ODPOWIEDZ