Wielomiany podziału koła - część 1

Poniższe twierdzenia są podstawą tego kącika. Dla kompletności podaję ich dowody, w których wykorzystuje się liczby zespolone. Czytelnik nieznający liczb zespolonych może je bez obaw pominąć i przejść od razu do zadań.

Twierdzenie 1. Istnieją (i są określone jednoznacznie) takie wielomiany unormowane (tzn. mające współczynnik $1$ przy najwyższej potędze zmiennej) ${\mathrm{\Phi }}_1,{\mathrm{\Phi }}_2,{\mathrm{\Phi }}_3,\dots$ o współczynnikach całkowitych, że dla każdego całkowitego dodatniego $n$ zachodzi równość: $$\begin{array}{}\text{(1)}& x^n-1=\prod _{d\mid n}{\mathrm{\Phi }}_d(x).\end{array}$$ Wielomiany ${\mathrm{\Phi }}_d(x)$ nazywamy wielomianami podziału koła (lub cyklotomicznymi).

Twierdzenie 2. Niech $\phi$ oznacza funkcję Eulera (zobacz kącik nr 45 w ${\mathrm{\Delta }}_{22}^9$). Dla $x\ge 1$ zachodzą nierówności: $$\begin{array}{}\text{(2)}& (x-1{)}^{\phi (n)}\le {\mathrm{\Phi }}_n(x)\le (x+1{)}^{\phi (n)},\end{array}$$ przy czym pierwsza z nich jest ostra dla $n\ge 2,$ a druga dla $n\ge 3.$ W szczególności dla $n\ge 2$ i $x\ge 2$ mamy ${\mathrm{\Phi }}_n(x)>1.$

Liczbę zespoloną $\zeta$ nazywamy pierwiastkiem $n$-tego stopnia z $1,$ jeśli ${\zeta }^n=1.$ Jeżeli ponadto ${\zeta }^m\ne 1$ dla $1\le m<n,$ to liczbę $\zeta$ nazywamy pierwotnym pierwiastkiem stopnia $n$ z $1.$ Niech ${\zeta }_n=e^{2\pi i/n}=\cos \frac{2\pi }{n}+i\sin \frac{2\pi }{n}.$ Wówczas zbiór ${\mu }_n=\{{\zeta }_n,{\zeta }_n^2,{\zeta }_n^3,\dots ,{\zeta }_n^n\}$ stanowią wszystkie pierwiastki stopnia $n$ z jedności, a zbiór ${\mu }_n^{\star }=\{{\zeta }_n^k:1\le k\le n,$ $\mathtt{\text{NWD}}(k,n)=1\}$ stanowią wszystkie pierwiastki pierwotne.

Lemat. Wielomiany ${\mathrm{\Phi }}_n(x)=\prod _{\zeta \in {\mu }_n^{\star }}(x-\zeta )$ spełniają równość $\text{(1)}$.

Dowód. Wykażemy najpierw równość ${\mu }_n=\bigcup _{d\mid n}{\mu }_d^{\star }.$ Ułamek $a/n$ dla $a=1,2,\dots ,n$ możemy w sposób jednoznaczny przedstawić w postaci $k/d,$ w której $d\mid n,$ $1\le k\le d$ oraz $\mathtt{\text{NWD}}(k,d)=1.$ Na odwrót, każdy taki ułamek $k/d$ możemy jednoznacznie rozszerzyć do ułamka $a/n.$ Na tej podstawie tworzymy bijekcję zbiorów ${\mu }_n$ i $\bigcup _{d\mid n}{\mu }_d^{\star }$ określoną przez ${\zeta }_n^a\mapsto {\zeta }_d^k$ ($k/d$ jest postacią nieskracalną ułamka $a/n$). Pozostaje jeszcze zauważyć, że wówczas ${\zeta }_n^a=e^{2a\pi /n}=e^{2k\pi /d}={\zeta }_d^k,$ więc ta bijekcja jest identycznością.
Z udowodnionej równości wynika, że $$x^n-1=\prod _{\zeta \in {\mu }_n}(x-\zeta )=\prod _{d\mid n}\prod _{\zeta \in {\mu }_d^{\star }}(x-\zeta ),$$ co kończy dowód lematu.

Dowód twierdzenia 1. Oczywiście wielomiany ${\mathrm{\Phi }}_m(x)$ z lematu są unormowane. Wybierzmy dowolne $n>1$ i załóżmy indukcyjnie, że wielomiany ${\mathrm{\Phi }}_m$ mają wszystkie współczynniki całkowite dla każdego $m<n.$ Niech ${\mathrm{\Psi }}_n(x)=\prod _{d\mid n,d<n}{\mathrm{\Phi }}_d(x).$ Z lematu wynika, że ${\mathrm{\Phi }}_n(x){\mathrm{\Psi }}_n(x)=(x^n-1).$ Na mocy założenia indukcyjnego ${\mathrm{\Psi }}_n(x)$ to unormowany wielomian o współczynnikach całkowitych, skąd (i z poprzedniej równości) ${\mathrm{\Phi }}_n(x)$ też ma współczynniki całkowite, co kończy dowód indukcyjny i uzasadnienie istnienia postulowanych w twierdzeniu 1 wielomianów. Analogiczną indukcją dowodzimy jednoznaczności (wielomiany ${\mathrm{\Phi }}_d$ opisane w twierdzeniu dla $d<n,$ $d\mid n$ oraz równość $\text{(1)}$ jednoznacznie wyznaczają wartości wielomianu ${\mathrm{\Phi }}_n$).

Dowód twierdzenia 2. Ponieważ ${\mathrm{\Phi }}_1(x)=x-1$ i ${\mathrm{\Phi }}_2(x)=x+1,$ teza jest oczywista dla $n\le 2.$ Dalej niech $n\ge 3.$ Jeśli $\zeta \in {\mu }_n^{\star },$ to $|\zeta |=1$ i $\zeta \ne \pm 1.$ Wobec tego $x-1<|x-\zeta |<x+1.$ Stopień wielomianu ${\mathrm{\Phi }}_n(x)$ jest równy $|{\mu }_n^{\star }|=\phi (n).$ Wynika z tego, że $(x-1{)}^{\phi (n)}<|{\mathrm{\Phi }}_n(x)|<(x+1{)}^{\phi (n)}.$ Pozostaje zauważyć, że dla $n\ge 3$ wielomian ${\mathrm{\Phi }}_n(x)$ jest unormowany i nie ma pierwiastków rzeczywistych, więc ${\mathrm{\Phi }}_n(x)>0$ dla wszystkich rzeczywistych $x,$ czyli $|{\mathrm{\Phi }}_n(x)|={\mathrm{\Phi }}_n(x).$

Zadania