Element pierwotny
: 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ędu } 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\bmod 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)}\).
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)}\).
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ędu } 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\bmod 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.
- 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)\bmod 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.