Kruhový polynom

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 6. února 2021; kontroly vyžadují 3 úpravy .

Kruhový polynom nebo polynom dělení kruhu je polynom tvaru

\Phi _{n}(x)=\prod _{k}(x-\xi _{n}^{k})

kde

\xi _{n}^{k}=\cos {\frac {2\pi k}n}+i\sin {\frac {2\pi k}n}

je kořenem jednoty $n$ a součin je převzat všechna přirozená čísla menší než a coprime to . $k$ $n$ $n$

Vlastnosti

Koeficienty kruhového polynomu jsou celá čísla.
Stupeň kruhového polynomu , kde je Eulerova funkce . ${\mathop {{\mathrm {deg}}}}\,\Phi _{n}=\varphi (n)$ $\varphi$
Kruhový polynom splňuje vztah

\prod _{{d|n}}\Phi _{{d}}(x)=x^{n}-1

kde součin převezme všechny kladné dělitele , včetně 1 a samotného . Tuto rovnost lze přepsat takto:

d

n

n

\Phi _{n}(x)={\frac {x^{n}-1}{\prod _{{d|n,\,d<n}}\Phi _{d}(x))) .

Pro polynom můžete zadat explicitní výraz pomocí Möbiovy funkce : $\Phi _{n} (x)$

\Phi _{n}(x)=\prod _{{d|n}}(x^{d}-1)^{{\mu (n/d)))

Speciální případ předchozího vzorce: if je prvočíslo , pak $n=p$

\Phi _{n}(x)={\frac {x^{p}-1}{x-1}}=x^{p-1}+x^{p-2}+\cdots +1

Jestliže , kde je liché číslo větší než jedna, pak: $n=2m$ $m$

\Phi _{2m}(x)=\Phi _{m}(-x)

If je maximální přirozené číslo dělení , a bez druhých mocnin (radikální ) a , pak $m$ $n$ $n$ $d=n/m$

\Phi _{n}(x)=\Phi _{m}(x^{d})

Jestliže je prvočíslo, které nedělí , pak $p$ $n$

\Phi _{pn}(x)={\frac {\Phi _{n}(x^{p})}{\Phi _{n}(x)))

V poli racionálních čísel jsou všechny polynomy neredukovatelné , ale v konečných jednoduchých tělesech mohou být tyto polynomy redukovatelné. Takže, je- li prvočíslo, pak modulo se polynom rozloží na lineární faktory a polynom se rozloží na součin ( různé) polynomy stupně 2 (neredukovatelné přes kruh ), s volnými členy rovnými 1. $\Phi _{n} (x)$ $p$ $p$ $\Phi _{p-1}(x)$ $\Phi _{p+1}(x)$ $\mathbb {Z} _{p}$
- Například:

\Phi _{8}(x)=x^{4}+1=(x^{2}+4x+1)(x^{2}-4x+1){\pmod {7}}

\Phi _{12}(x)=x^{4}-x^{2}+1=(x^{2}+5x+1)(x^{2}-5x+1){ \pmod {11}}

\Phi _{14}(x)=(x^{2}-6x+1)(x^{2}-5x+1)(x^{2}-3x+1){\pmod { 13}}

Obecnější je následující fakt: Je-li p prvočíslo, n přirozené číslo, pak polynom modulo p expanduje na součin polynomů stupně n. Jestliže n je také jednoduché, pak polynomy stupně n zapojené do rozkladu jsou ireducibilní v kruhu . $\Phi _{\Phi _{n}(p)}(x)$ $\mathbb {Z} _{p}$

Příklady

Zde je souhrn prvních 30 kruhových polynomů [1] .

\Phi _{1}(x)=x-1

\Phi _{2}(x)=x+1

\Phi _{3}(x)=x^{2}+x+1

\Phi _{4}(x)=x^{2}+1

\Phi _{5}(x)=x^{4}+x^{3}+x^{2}+x+1

\Phi _{6}(x)=x^{2}-x+1

\Phi _{7}(x)=x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1

\Phi _{8}(x)=x^{4}+1

\Phi _{9}(x)=x^{6}+x^{3}+1

\Phi _{10}(x)=x^{4}-x^{3}+x^{2}-x+1

\Phi _{11}(x)=x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x ^{4}+x^{3}+x^{2}+x+1

\Phi _{12}(x)=x^{4}-x^{2}+1

\Phi _{13}(x)=x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x ^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1

\Phi _{14}(x)=x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1

\Phi _{15}(x)=x^{8}-x^{7}+x^{5}-x^{4}+x^{3}-x+1

\Phi _{16}(x)=x^{8}+1

\Phi _{17}(x)=x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x ^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{ 2}+x+1

\Phi _{18}(x)=x^{6}-x^{3}+1

\Phi _{19}(x)=x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x ^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{ 4}+x^{3}+x^{2}+x+1

\Phi _{20}(x)=x^{8}-x^{6}+x^{4}-x^{2}+1

\Phi _{21}(x)=x^{12}-x^{11}+x^{9}-x^{8}+x^{6}-x^{4}+x ^{3}-x+1

\Phi _{22}(x)=x^{10}-x^{9}+x^{8}-x^{7}+x^{6}-x^{5}+x ^{4}-x^{3}+x^{2}-x+1

\Phi _{23}(x)=x^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+x ^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{ 8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1

\Phi _{24}(x)=x^{8}-x^{4}+1

\Phi _{25}(x)=x^{20}+x^{15}+x^{10}+x^{5}+1

\Phi _{26}(x)=x^{12}-x^{11}+x^{10}-x^{9}+x^{8}-x^{7}+x ^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1

\Phi _{27}(x)=x^{18}+x^{9}+1

\Phi _{28}(x)=x^{12}-x^{10}+x^{8}-x^{6}+x^{4}-x^{2}+1

\Phi _{29}(x)=x^{28}+x^{27}+x^{26}+x^{25}+x^{24}+x^{23}+x ^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+x^{16}+x^{15}+x^{ 14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6} +x^{5}+x^{4}+x^{3}+x^{2}+x+1

\Phi _{30}(x)=x^{8}+x^{7}-x^{5}-x^{4}-x^{3}+x+1

Z tohoto shrnutí můžeme usoudit, že nenulové koeficienty kruhového polynomu jsou vždy stejné, ale tento předpoklad je nesprávný. První protipříklad dává 105. polynom: $\pm1,$

{\begin{aligned}\Phi _{{105}}(x)=&\;x^{{48}}+x^{{47}}+x^{{46}}-x^{{43 }}-x^{{42}}-2x^{{41}}-x^{{40}}-x^{{39}}+x^{{36}}+x^{{35}} +x^{{34}}\\&{}+x^{{33}}+x^{{32}}+x^{{31}}-x^{{28}}-x^{{ 26}}-x^{{24}}-x^{{22}}-x^{{20}}+x^{{17}}+x^{{16}}+x^{{15} }\\&{}+x^{{14}}+x^{{13}}+x^{{12}}-x^{9}-x^{8}-2x^{7}-x ^{6}-x^{5}+x^{2}+x+1\end{aligned}}

Aplikace

Jednou z nejdůležitějších aplikací kruhových polynomů je věta o multiplikativní grupě konečného pole:

Teorém. Multiplikativní grupa konečného pole je cyklická grupa. $K^{*}$ $K$

Důkaz. Nechť pole sestává z prvku, pak jeho multiplikativní skupina (skupina invertibilních prvků) obsahuje všechny prvky pole kromě nuly, to znamená, že se skládá z prvků. Podle Lagrangeovy věty pořadí prvku grupy rozděluje pořadí této grupy, proto pro jakýkoli prvek , , to znamená, že všechny prvky z jsou kořeny rovnice . Pak $K$ $n+1$ $K^{*}$ $n$ $a\in K^{*}$ $a^{n}=1$ $K^{*}$ $x^{n}-1=0$

\prod \limits _{a\in K^{*}}(xa)=x^{n}-1

protože všechny kořeny levé strany jsou kořeny pravé strany a stupně a vedoucí členy obou polynomů jsou stejné.

Protože

x^{n}-1=\prod \limits _{d|n}\Phi _{d}(x)

a ,

\deg \Phi _{d}(x)=\varphi (d)\geqslant 1

pak má polynom přesně kořeny v (a tedy alespoň jeden). Její kořeny jsou prvky řádové grupy , to znamená, že cyklická grupa tvořená kterýmkoli z nich obsahuje různé prvky a musí se shodovat s celou grupou , z čehož vyplývá cykličnost této grupy. $\Phi _{n} (x)$ $\varphi (n)$ $K$ $K^{*}$ $n$ $n$ $K^{*}$

Viz také

kruhové pole

Literatura

Ireland K., Rosen M. Klasický úvod do moderní teorie čísel . M.: Mir, 1987.
Van der Waerden B. L. Algebra. M.: Mir, 1975.

Poznámky

↑ OEIS A013595 .