Wielomiany podziału koła – część 2

Przed przystąpieniem do lektury polecam zapoznać się z poprzednim kącikiem (${\mathrm{\Delta }}_{24}^1$). Udowodniliśmy w nim istnienie ciągu wielomianów ${\mathrm{\Phi }}_1(x),$ ${\mathrm{\Phi }}_2(x),$ …, które dla każdej liczby naturalnej $n$ spełniają $$\prod _{d\mid n}{\mathrm{\Phi }}_d(x)=x^n-1.$$ W tym kąciku przyjrzymy się rozkładowi na czynniki pierwsze liczby ${\mathrm{\Phi }}_n(a)$ dla $a\ge 2.$ Niech $p$ będzie liczbą pierwszą, która dzieli ${\mathrm{\Phi }}_n(a).$ Ponieważ ${\mathrm{\Phi }}_n(a)\mid a^n-1,$ więc $p\mid a^n-1.$ Istnieje zatem najmniejsza taka liczba całkowita dodatnia $r,$ że $p\mid a^r-1.$ Nazywamy ją rzędem $a$ modulo $p.$ Rząd jest dzielnikiem każdej liczby naturalnej $w$ spełniającej $p\mid a^w-1,$ w szczególności $r\mid n.$ Zapiszmy $n=rm{p}^k,$ przy czym $p\nmid m.$ Niech ${\nu }_p(N)$ oznacza wykładnik największej potęgi $p$ dzielącej $N.$ Dla $p>2$ otrzymujemy $${\nu }_p(a^r-1)+k\stackrel{\text{(i)}}{=}{\nu }_p(a^n-1)\stackrel{\text{(ii)}}{=}\sum _{D\mid n}{\nu }_p({\mathrm{\Phi }}_D(a))\stackrel{\text{(iii)}}{=}\sum _{d\mid m}\sum _{j=0}^k{\nu }_p({\mathrm{\Phi }}_{rd{p}^j}(a)),$$ przy czym (i) wynika z lematu o zwiększaniu wykładnika $p$-adycznego (zob. kącik nr 24 w ${\mathrm{\Delta }}_{20}^{12}$), a (ii) wynika z (1). Równość (iii) wynika z obserwacji, że jeśli ${\nu }_p({\mathrm{\Phi }}_d(a))$ jest niezerowe, czyli $p\mid {\mathrm{\Phi }}_D(a),$ to $p\mid a^D-1,$ a więc $r\mid$D; natomiast każdy podzielny przez $r$ dzielnik $n$ jest postaci $rd{p}^j,$ w której $d\mid m$ i $j\le k.$

Z równości (2) wnioskujemy kolejno, że:

1. jeśli $n=r$ ($k=0$ i $m=1$), to ${\nu }_p(a^r-1)={\nu }_p({\mathrm{\Phi }}_n(a))$;

2. jeśli $n=r{p}^k$ ($k>0$ i $m=1$), to ${\nu }_p({\mathrm{\Phi }}_n(a))=1,$ co uzasadniamy indukcją po $k$;

3. jeśli $n=rm{p}^k$ ($k>0$ i $m>1$), to ${\nu }_p({\mathrm{\Phi }}_n(a))=0$

Uzasadnienia powyższych implikacji można powtórzyć dla $p=2$ i $n\ge 3,$ wykorzystując część 2(c) lematu o zwiększaniu wykładnika, sformułowanego w kąciku nr 24. Dzielniki pierwsze liczby ${\mathrm{\Phi }}_n(a)$ dla $n\ge 3$ można zatem podzielić na trywialne (spełniające $n=r{p}^k$ dla $k>0$) i nietrywialne (spełniające $n=r$). Te pierwsze jest łatwo znaleźć, bo są dzielnikami $n.$ Jest nawet prościej: zgodnie z Małym Twierdzeniem Fermata $a^{p-1}\equiv 1(\mathrm{mod}p),$ czyli $r\mid p-1$ i $r<p,$ a zatem z równości $n=r{p}^k$ wynika, że $p$ jest największą liczbą pierwszą dzielącą $n.$ Dlatego ${\mathrm{\Phi }}_n(a)$ ma co najwyżej jeden dzielnik trywialny.

Trudniej znaleźć dzielniki nietrywialne. Wykażemy tu, że niemal zawsze jest co najmniej jeden taki dzielnik. Niech $p$ będzie największym dzielnikiem pierwszym liczby $n.$ Wystarczy wykazać, że ${\mathrm{\Phi }}_n(a)>p$ – w takiej sytuacji nawet gdyby $p$ okazał się dzielnikiem trywialnym, to równość ${\nu }_p({\mathrm{\Phi }}_n(a))=1$ implikuje istnienie dzielnika ${\mathrm{\Phi }}_n(a)$ różnego od $p,$ a zatem nietrywialnego. Zapiszmy $n=mp.$ Nietrudno udowodnić, że dla $p\mid m$ zachodzi ${\mathrm{\Phi }}_n(x)={\mathrm{\Phi }}_m(x^p),$ a w przeciwnym przypadku ${\mathrm{\Phi }}_n(x){\mathrm{\Phi }}_m(x)={\mathrm{\Phi }}_m(x^p)$ – wystarczy porównać pierwiastki wielomianów po obu stronach (por. ${\mathrm{\Delta }}_{24}^1$). Ta pierwsza równość pozwala też wywnioskować, że jeśli każdy dzielnik pierwszy liczby $t$ jest dzielnikiem pierwszym liczby $m,$ to ${\mathrm{\Phi }}_{mt}(x)={\mathrm{\Phi }}_m(x^t).$

Ponieważ $(a-1{)}^{\phi (n)}\le {\mathrm{\Phi }}_n(a)\le (a+1{)}^{\phi (n)}$ dla $a\ge 2$ (znów ${\mathrm{\Delta }}_{24}^1$), otrzymujemy $${\mathrm{\Phi }}_n(a)\ge \frac{{\mathrm{\Phi }}_m(a^p)}{max\{1,{\mathrm{\Phi }}_m(a)\}}\ge \frac{(a^p-1{)}^{\phi (m)}}{(a+1{)}^{\phi (m)}}\ge \frac{a^p-1}{a+1}\ge \frac{2^p-1}{3}.$$ Jest jasne, że $\frac{2^p-1}{3}>p$ dla $p>3.$ Jeżeli $p=2,$ to $n=2^k=2t$ oraz ${\mathrm{\Phi }}_n(a)=a^t+1>2.$ Dla $p=3$ możliwe są dwie sytuacje. Dla $n=3^k=3t$ mamy ${\mathrm{\Phi }}_n(a)=a^{2t}+a^t+1>3.$ Jeśli $n=2^{k_1}{3}^{k_2}=6t,$ to mamy ${\mathrm{\Phi }}_n(a)=a^{2t}-a^t+1,$ co jest większe od $3,$ gdy $a>2$ lub $t>1.$ W przypadku $a=2$ i $t=1$ mamy ${\mathrm{\Phi }}_6(2)=3,$ i nie ma tu dzielnika nietrywialnego. Wykazaliśmy zatem:

Twierdzenie. Jeśli $n\ge 3,$ $a\ge 2$ oraz $(n,a)\ne (3,2),$ to liczba ${\mathrm{\Phi }}_n(a)$ ma nietrywialny dzielnik pierwszy $p,$ tzn. rząd $a$ modulo $p$ wynosi $n.$

Zadania