Suma pierwiastków pierwotnych (ciekawe)

[Parton]

Obliczyć sumę pierwiastków pierwotnych stopnia n z 1. Zadanko jest bardzo fajne no i trickowe, na pałę się go nie zrobi. A no i wynik jest bardzo ciekawy.

[max]

Oznaczmy tę sumę w zależności od \(\displaystyle{ n}\) przez \(\displaystyle{ s(n)}\).

Zauważmy, że jeśli \(\displaystyle{ d|n}\), to wśród pierwiastków n-tego stopnia z \(\displaystyle{ 1}\) są wszystkie pierwiastki pierwotne stopnia \(\displaystyle{ d}\) z \(\displaystyle{ 1}\) oraz, że dla każdego pierwiastka \(\displaystyle{ \xi}\) n-tego stopnia z \(\displaystyle{ 1}\) znajdziemy takie \(\displaystyle{ d|n}\), że \(\displaystyle{ \xi}\) jest pierwiastkiem pierwotnym d-tego stopnia z \(\displaystyle{ 1}\) (za \(\displaystyle{ d}\) wystarczy przyjąć najmniejszą liczbę naturalną taką, że \(\displaystyle{ \xi^{d} - 1 = 0}\)).

Stąd i z wzorów Viete'a z których wynika, że suma wszystkich pierwiastków n-tego stopnia z \(\displaystyle{ 1}\) jako suma pierwiastków wielomianu \(\displaystyle{ x^{n} - 1}\) wynosi \(\displaystyle{ 0}\) otrzymujemy, że

\(\displaystyle{ s(n) = -\sum_{\substack{d|n \\ d}\)


Dalej pokażemy, że \(\displaystyle{ s}\) jest funkcją multiplikatywną:

Oczywiście \(\displaystyle{ s(1) = 1}\)
Zauważmy, że pierwiastki pierwotne z n-tego stopnia z \(\displaystyle{ 1}\) mają jednoznaczne przedstawienie \(\displaystyle{ \mbox{exp}\,\left(\frac{2ki\pi}{n}\right)}\) z dokładnością do reszty \(\displaystyle{ k}\) modulo \(\displaystyle{ n}\), gdzie \(\displaystyle{ k}\) jest względnie pierwsze z \(\displaystyle{ n}\).
Stąd

\(\displaystyle{ s(n) = \sum_{\substack{k\in \{0,\ldots, n - 1\}\\ (k,n) = 1}}\mbox{exp}\,\left(\frac{2ki\pi}{n}\right)}\)

więc jeśli \(\displaystyle{ n, m}\) są względnie pierwsze, to:

\(\displaystyle{ s(n)s(m) = \sum_{\substack{k\in \{0,\ldots, n - 1\},\, l \in \{0, \ldots, m-1\}\\ (k,n) = 1,\, (l,m) = 1}}\mbox{exp}\left(\frac{2(km + ln)i\pi}{nm}\right) = s(nm)}\)

gdyż dla względnie pierwszych \(\displaystyle{ n,m}\) każda liczba względnie pierwsza z \(\displaystyle{ nm}\) ma jednoznaczne przedstawienie modulo \(\displaystyle{ nm}\) postaci \(\displaystyle{ km + ln}\), gdzie \(\displaystyle{ k\in \{0,\ldots, n-1\}, \ l \in \{0,\ldots, m-1\}, \ (k,n) = 1,\ (l, m) = 1}\).

Ponieważ \(\displaystyle{ s}\) jest multiplikatywna to jest wyznaczona jednoznacznie przez wartości na argumentach postaci \(\displaystyle{ p^{\alpha}}\).
Mamy:
\(\displaystyle{ s(p^{0}) = 1}\), z pierwszego z otrzymanych wzorów na \(\displaystyle{ s(n)}\) dostajemy \(\displaystyle{ s(p) = -1}\) i dalej przez indukcję z tegoż wzoru \(\displaystyle{ s(p^{\alpha}) = 0}\) dla \(\displaystyle{ \alpha > 1}\).

Pozostaje zauważyć, że dokładnie tak samo na argumentach \(\displaystyle{ p^{\alpha}}\) zachowuje się multiplikatywna funkcja \(\displaystyle{ \mu}\) Möbiusa, lub też przez indukcję ze względu na liczbę dzielników pierwszych \(\displaystyle{ n}\) pokazać, że dla \(\displaystyle{ n > 1}\) jest:

\(\displaystyle{ s(n) = \begin{cases}1,\ n = p_{1}\cdot\ldots\cdot p_{2k}\\ 0, \ \exists p : \, p^{2}|n\\ -1,\ n = p_{1}\cdot\ldots\cdot p_{2k+1} \end{cases} = \mu(n)}\)

gdzie \(\displaystyle{ p, p_{i}}\) są pierwsze i \(\displaystyle{ p_{i}}\) są parami różne.