Dlaczego funkcja Eulera ϕ(n) jest tak fundamentalna i jednocześnie tajemnicza?

Funkcja Eulera ϕ(n), określająca liczbę dodatnich liczb całkowitych nieprzekraczających n i względnie pierwszych z n, może wydawać się z pozoru nieskomplikowana. Jednak jej natura jest dalece bardziej złożona, niż sugeruje to jej definicja. W rzeczywistości, struktura jej wartości bywa bardziej zawiła niż faktoryzacja samego n, a to czyni ją jednym z kluczowych, a zarazem trudniejszych obiektów w teorii liczb.

Centralna tożsamość ϕ = μ ∗ I, gdzie I(k) = k i μ to funkcja Möbiusa, prowadzi do natychmiastowego wniosku, że splot ı ∗ ϕ = I, czyli suma ϕ(d) po dzielnikach d liczby n jest równa n. Tożsamość ta nie tylko charakteryzuje funkcję Eulera, ale również pozwala rekonstruować ϕ za pomocą inwersji Möbiusa. Co więcej, funkcja ta jest multiplikatywna, co oznacza, że jeśli m i n są względnie pierwsze, to zachodzi ϕ(mn) = ϕ(m)ϕ(n).

Jednakże to właśnie formuła jawna:

Wzory z funkcją Ramanujana cq(n), zdefiniowaną jako suma e(nh/q) po wszystkich h ≤ q, dla których h i q są względnie pierwsze, ujawniają kolejne właściwości multiplikatywne: cq1q2(n) = cq1(n)cq2(n), jeśli q1 i q2 są względnie pierwsze. Dodatkowo, cq(n) zależy wyłącznie od największego wspólnego dzielnika ⟨q,n⟩, czyli cq(n) = cq(⟨q,n⟩). Funkcja ta przyjmuje formę wyrażoną wzorem:
cq(n) = μ(q/⟨q,n⟩) * ϕ(q) / ϕ(q/⟨q,n⟩),
co jest natychmiastowym następstwem tożsamości Möbiusa oraz splotów liczbowych.

W szczególności, podstawiając n = 1, otrzymujemy zaskakującą postać funkcji Möbiusa jako szeregu Fouriera:
μ(q) = ∑ e(h/q),
gdzie suma biegnie po wszystkich h względnie pierwszych z q. Ten rezultat łączy teorię liczb z analizą harmoniczną i funkcjami trygonometrycznymi, wskazując na ich wspólną strukturę algebraiczną.

Ciekawostką jest również prawdopodobieństwo, że dwie losowe liczby a i b są względnie pierwsze. Wynosi ono dokładnie 6/π² – wartość pojawiająca się w kontekście funkcji dzeta Riemanna: ζ(2) = π²/6. Dowód wykorzystuje własności funkcji Möbiusa i sprowadza się do obliczenia podwójnej sumy po liczbach ≤ N, które są względnie pierwsze, a następnie jej granicy przy N → ∞.

Chociaż funkcja ϕ(n) ma czysto arytmetyczne korzenie, jej złożoność wewnętrzna powoduje, że wiele pytań z nią związanych pozostaje otwartych. Przykładem jest hipoteza Carmichaela, która głosi, że dla każdego m ≥ 1 istnieje co najmniej jedna liczba n ≠ m, taka że ϕ(n) = ϕ(m). Równie nieuchwytne jest pytanie Lehmera, czy istnieje liczba złożona n taka, że ϕ(n) dzieli n − 1. Brak odpowiedzi na te pytania pokazuje, że mimo upływu wieków funkcja Eulera nadal skrywa nieodkryte tajemnice.

Ważne jest zrozumienie, że choć wzór (18.4) umożliwia wyznaczenie wartości ϕ(n), to jego praktyczne zastosowanie wymaga pełnej faktoryzacji n – co jest problematyczne dla dużych liczb. W konsekwencji funkcja ϕ odgrywa kluczową rolę w kryptografii asymetrycznej, w tym w algorytmie RSA, gdzie bezpieczeństwo opiera się właśnie na trudności faktoryzacji. Ponadto, choć funkcja Eulera wydaje się posiadać prostą strukturę, to jej odwrotność względem splotu Dirichleta, jej związki z funkcją Möbiusa, a także liczne zależności z teorią dzielników, dowodzą jej głębokiego zakorzenienia w strukturze liczbowej liczb naturalnych.

Jak rozwiązywać zagadnienia związane z pierwiastkami wielomianów w ciałach skończonych?

Aby to potwierdzić, zauważmy, że dla $t(\rho^p) = 0$, mamy do czynienia z różnymi pierwiastkami, które spełniają $t(x) = 0$. Gdyby na przykład $\rho^{p^u} = \rho^{p^v}$, to przyjmując $\xi = \rho^{p^u}$, możemy uzyskać, że $t(\xi) = 0$ oraz $\xi^{p^{v-u}} = \xi$. Stąd można wykazać, że $t(x)$ dzieli wyrażenie $(x^{p^{v-u}} - x)$ w $\mathbb{F}_p[x]$, co prowadzi do wniosku, że stopień wielomianu dzieli różnicę $v - u$, co kończy dowód.

Zastosowanie tej struktury jest kluczowe dla dalszej analizy sum Gaussa w ciałach skończonych. Definiujemy sumę Gaussa $\gamma(a) = \sum_{h \mod q} \lambda^{ah}$, która jest istotna w kontekście wyznaczania wartości charakterystyk Gaussa oraz wykorzystywania jej w dowodach reciprocity. Na przykład, w przypadku gdy $p \mod q$ jest kwadratowym resztą mod $q$, suma $\gamma(1)$ ma wartość różną od zera, co wprost wiąże się z rezultatem twierdzenia Gaussa o reciprocity kwadratowym.

Z kolei, gdy przechodzimy do dalszego rozważania Gaussa w kontekście innych dowodów reciprocity, dostrzegamy, że takie podejście jest korzystne z punktu widzenia strukturalnej elegancji dowodów Gaussa, których celem jest ukazanie głębokiej więzi między teorią liczb a teorią pól. Chociaż dowody na podstawie sum Gaussa, takie jak w przypadku Gaussa i jego ósmego dowodu, mogą wydawać się zwięzłe i proste, zawierają one ogromną ilość informacji matematycznej i strukturalnej, co czyni je niezwykle istotnymi w historii matematyki.

Warto także dodać, że struktury pól skończonych i ich rozszerzeń są nie tylko narzędziem do rozwiązania problemów algebraicznych, ale także mają zastosowanie w bardziej zaawansowanych teoriach, takich jak teoria kodowania czy kryptografia. Analiza tych ciał pozwala na lepsze zrozumienie fundamentów nowoczesnej matematyki, w tym algorytmów stosowanych w cyfrowych technologiach.