Suma pierwiastków pierwotnych (ciekawe)
-
- Użytkownik
- Posty: 158
- Rejestracja: 10 gru 2008, o 23:20
- Płeć: Mężczyzna
- Lokalizacja: Wawa
- Podziękował: 7 razy
- Pomógł: 10 razy
Suma pierwiastków pierwotnych (ciekawe)
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
- Użytkownik
- Posty: 3306
- Rejestracja: 10 gru 2005, o 17:48
- Płeć: Mężczyzna
- Lokalizacja: Lebendigentanz
- Podziękował: 37 razy
- Pomógł: 778 razy
Suma pierwiastków pierwotnych (ciekawe)
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.
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.