Polinomio ciclotómico

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Polinomio irreducible cuyas raíces son nth raíces de la unidad

En matemáticas, la npolinomia ciclotómica, para cualquier entero positivo n, es el polinomio irreducible único con coeficientes enteros que es un divisor de $x^{n}-1$ y no es un divisor de $x^{k}-1$ para cualquier k. n. Sus raíces son todas nlas raíces primitivas de la unidad $e^{2ipi {frac {k}{n}}}$ , donde k se ejecuta sobre los enteros positivos no mayor que n y coprime n (y) i es la unidad imaginaria). En otras palabras, npolinomia ciclotómica es igual a

{displaystyle Phi _{n}(x)=prod _{stackrel {1leq kleq n}{gcd(k,n)=1}}left(x-e^{2ipi {frac {k}{n}}}right).}

También puede definirse como el polinomio monico con coeficientes enteros que es el polinomio mínimo sobre el campo de los números racionales de cualquier primitivo nth-root de unidad ( $e^{2ipi /n}$ es un ejemplo de tal raíz).

Una relación importante que vincula los polinomios ciclotómicos y las raíces primitivas de la unidad es

prod _{dmid n}Phi _{d}(x)=x^{n}-1,

mostrando eso $x$ es una raíz de $x^n - 1$ si y sólo si es un dla raíz primitiva de la unidad para algunos d que divide n.

Ejemplos

Si n es un número primo, entonces

{displaystyle Phi _{n}(x)=1+x+x^{2}+cdots +x^{n-1}=sum _{k=0}^{n-1}x^{k}.}

Si n = 2p donde p es un número primo impar, entonces

{displaystyle Phi _{2p}(x)=1-x+x^{2}-cdots +x^{p-1}=sum _{k=0}^{p-1}(-x)^{k}.}

Para n hasta 30, los polinomios ciclotómicos son:

{displaystyle {begin{aligned}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}\&qquad quad +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}\&qquad quad +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.end{aligned}}}

El caso del polinomio ciclotómico 105 es interesante porque 105 es el entero menos positivo que es el producto de tres números primos impares distintos (3*5*7) y este polinomio es el primero que tiene un coeficiente distinto de 1, 0 o −1:

{displaystyle {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}\&qquad quad -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}}}

Propiedades

Herramientas fundamentales

Los polinomios ciclotómicos son polinomios mónicos con coeficientes enteros que son irreducibles sobre el campo de los números racionales. Salvo n igual a 1 ó 2, son palindrómicos de grado par.

El grado de $Phi _{n}$ , o en otras palabras el número de nlas raíces primitivas de la unidad, es $varphi (n)$ , donde $varphi$ es la función totiente de Euler.

El hecho de que $Phi _{n}$ es un polinomio irreducible de grado $varphi (n)$ en el anillo ${displaystyle mathbb {Z} [x]}$ es un resultado no trivial debido a Gauss. Dependiendo de la definición elegida, es el valor del grado o la irreducibilidad que es un resultado no tripartito. El caso de la primera n es más fácil probar que el caso general, gracias al criterio de Eisenstein.

Una relación fundamental que involucra polinomios ciclotómicos es

{displaystyle {begin{aligned}x^{n}-1&=prod _{1leqslant kleqslant n}left(x-e^{2ipi {frac {k}{n}}}right)\&=prod _{dmid n}prod _{1leqslant kleqslant n atop gcd(k,n)=d}left(x-e^{2ipi {frac {k}{n}}}right)\&=prod _{dmid n}Phi _{frac {n}{d}}(x)=prod _{dmid n}Phi _{d}(x).end{aligned}}}

lo que significa que cada raíz n-ésima de la unidad es una raíz primitiva d-ésima de la unidad para una única d que divide a n.

La fórmula de inversión Möbius permite la expresión $Phi _{n}(x)$ como una fracción racional explícita:

{displaystyle Phi _{n}(x)=prod _{dmid n}(x^{d}-1)^{mu left({frac {n}{d}}right)},}

Donde $mu$ es la función Möbius.

El polinomio ciclotómico $Phi _{n}(x)$ puede ser calculado por (exactamente) división $x^{n}-1$ por los polinomios ciclotómicos de los divisores adecuados n anteriormente computado recursivamente por el mismo método:

<math alttext="{displaystyle Phi _{n}(x)={frac {x^{n}-1}{prod _{stackrel {d|n}{{}_{dCCPR CCPR n()x)=xn− − 1∏ ∏ d.ndSilencionCCPR CCPR d()x){displaystyle Phi _{n}(x)={frac {x^{n}-1}{prod _{stackrel - ¿Qué? Phi...<img alt="Phi _{n}(x)={frac {x^{n}-1}{prod _{stackrel {d|n}{{}_{d

(Recuerde eso $Phi _{1}(x)=x-1$ .)

Esta fórmula define un algoritmo para la computación $Phi _{n}(x)$ para cualquier n, proporciona la factorización de entero y la división de polinomios están disponibles. Muchos sistemas de álgebra computarizada, como SageMath, Maple, Mathematica y PARI/GP, tienen una función integrada para calcular los polinomios ciclotómicos.

Casos fáciles de computar

Como se indicó anteriormente, si $n$ es un número primo, entonces

{displaystyle Phi _{n}(x)=1+x+x^{2}+cdots +x^{n-1}=sum _{k=0}^{n-1}x^{k}.}

Si n es un entero impar mayor que uno, entonces

Phi _{2n}(x)=Phi _{n}(-x).

En particular, si $n = 2 p$ es el doble de un primo impar, entonces (como se indicó anteriormente)

{displaystyle Phi _{n}(x)=1-x+x^{2}-cdots +x^{p-1}=sum _{k=0}^{p-1}(-x)^{k}.}

Si $n = p m$ es una potencia principal (donde p es primo), entonces

{displaystyle Phi _{n}(x)=Phi _{p}(x^{p^{m-1}})=sum _{k=0}^{p-1}x^{kp^{m-1}}.}

Más generalmente, si $n = p m r$ con $r$ relativamente primo a $p$ , entonces

Phi _{n}(x)=Phi _{pr}(x^{p^{m-1}}).

Estas fórmulas se pueden aplicar repetidamente para obtener una simple expresión para cualquier polinomio ciclotómico $Phi _{n}(x)$ en término de un polinomio ciclotómico de índice libre cuadrado: Si $q$ es el producto de los divisores principales de $n$ (su radical), entonces

Phi _{n}(x)=Phi _{q}(x^{n/q}).

Esto permite dar fórmulas para el $n$ ésimo polinomio ciclotómico cuando $n$ tiene como máximo un factor primo impar: si $p$ es un número primo impar, y $h$ y $k$ son enteros positivos, entonces:

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

{displaystyle Phi _{p^{k}}(x)=sum _{j=0}^{p-1}x^{jp^{k-1}}}

{displaystyle Phi _{2^{h}p^{k}}(x)=sum _{j=0}^{p-1}(-1)^{j}x^{j2^{h-1}p^{k-1}}}

Para los otros valores $n$ , la computación de la $n$ polinomio ciclotómico se reduce igualmente a la de $Phi _{q}(x),$ Donde $q$ es el producto de los diferentes divisores principales diferentes $n$ . Para tratar este caso, uno tiene eso, para $p$ primo y no dividir $n$ ,

{displaystyle Phi _{np}(x)=Phi _{n}(x^{p})/Phi _{n}(x).}

Enteros que aparecen como coeficientes

El problema de acotar la magnitud de los coeficientes de los polinomios ciclotómicos ha sido objeto de varios trabajos de investigación. Varios documentos de encuestas ofrecen una visión general.

Si n tiene en la mayoría de dos factores principales diferentes, entonces Migotti mostró que los coeficientes de $Phi _{n}$ están todos en el set {1, −1, 0}.

El primer polinomio ciclotómico para un producto de tres factores principales diferentes es $Phi _{105}(x);$ tiene un coeficiente -2 (ver su expresión anterior). El contrario no es cierto: ${displaystyle Phi _{231}(x)=Phi _{3times 7times 11}(x)}$ sólo tiene coeficientes en {1, −1, 0}.

Si n es un producto de factores primas más diferentes, los coeficientes pueden aumentar a valores muy altos. Por ejemplo, ${displaystyle Phi _{15015}(x)=Phi _{3times 5times 7times 11times 13}(x)}$ tiene coeficientes desde −22 hasta 23, ${displaystyle Phi _{255255}(x)=Phi _{3times 5times 7times 11times 13times 17}(x)}$ , el más pequeño n con 6 primas diferentes, tiene coeficientes de magnitud hasta 532.

Sea A(n) el valor absoluto máximo de los coeficientes de Φ_n. Se sabe que para cualquier k positivo, el número de n hasta x con A( n) > n^k es al menos c(k)⋅x para un positivo c(k) dependiendo de k y x suficientemente grande. En sentido contrario, para cualquier función ψ(n) con tendencia a infinito con n tenemos A(n) delimitado arriba por n^ψ(n) para casi todos los n.

Una combinación de teoremas de Bateman resp. Vaughan afirma que por un lado, por cada $0}" xmlns="http://www.w3.org/1998/Math/MathML">ε ε ■0{displaystyle varepsilon }0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e04ec3670b50384a3ce48aca42e7cc5131a06b12" style="vertical-align: -0.338ex; width:5.344ex; height:2.176ex;"/>$ , tenemos

<math alttext="{displaystyle A(n)A()n).e()n()log⁡ ⁡ 2+ε ε ))/()log⁡ ⁡ log⁡ ⁡ n){displaystyle A(n) wone^{(n(log 2+varepsilon)/(log log n)}<img alt="{displaystyle A(n)

para todos los enteros positivos suficientemente grandes $n$ , y por otro lado, tenemos

e^{(nlog 2)/(log log n)}}" xmlns="http://www.w3.org/1998/Math/MathML">A()n)■e()nlog⁡ ⁡ 2)/()log⁡ ⁡ log⁡ ⁡ n){displaystyle A(n) confianzae^{(nlog 2)/(log log n)}e^{(nlog 2)/(log log n)}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/93894f037d19fff43b2dab363ee40f8f4d9ce364" style="vertical-align: -0.838ex; width:23.389ex; height:3.343ex;"/>

para infinitamente muchos números enteros positivos $n$ . Esto implica en particular que los polinomios univarios (concretamente) $x^{n}-1$ para infinitamente muchos números enteros positivos $n$ ) puede tener factores (como $Phi _{n}$ ) cuyos coeficientes son superpolynomially mayores que los coeficientes originales. Esto no está muy lejos del límite general de Landau-Mignotte.

Fórmula de Gauss

Sea n impar, sin cuadrados y mayor que 3. Entonces:

{displaystyle 4Phi _{n}(z)=A_{n}^{2}(z)-(-1)^{frac {n-1}{2}}nz^{2}B_{n}^{2}(z)}

donde tanto A_n(z) como B_n(z) tiene coeficientes enteros, A_n(z) tiene grado φ(n)/2, y B_n(z) tiene grado φ(n)/2 − 2. Además, A_n(z) es palindrómico cuando su grado es par; si su grado es impar es antipalindrómico. De manera similar, B_n(z) es palindrómico a menos que n sea compuesto y ≡ 3 (mod 4), en cuyo caso es antipalindrómico.

Los primeros casos son

{displaystyle {begin{aligned}4Phi _{5}(z)&=4(z^{4}+z^{3}+z^{2}+z+1)\&=(2z^{2}+z+2)^{2}-5z^{2}\[6pt]4Phi _{7}(z)&=4(z^{6}+z^{5}+z^{4}+z^{3}+z^{2}+z+1)\&=(2z^{3}+z^{2}-z-2)^{2}+7z^{2}(z+1)^{2}\[6pt]4Phi _{11}(z)&=4(z^{10}+z^{9}+z^{8}+z^{7}+z^{6}+z^{5}+z^{4}+z^{3}+z^{2}+z+1)\&=(2z^{5}+z^{4}-2z^{3}+2z^{2}-z-2)^{2}+11z^{2}(z^{3}+1)^{2}end{aligned}}}

Fórmula de Lucas

Sea n impar, sin cuadrados y mayor que 3. Entonces

{displaystyle Phi _{n}(z)=U_{n}^{2}(z)-(-1)^{frac {n-1}{2}}nzV_{n}^{2}(z)}

donde tanto U_n(z) como V_n(z) tiene coeficientes enteros, U_n(z) tiene grado φ(n)/2, y V_n(z) tiene grado φ(n)/2 − 1. Esto también se puede escribir

{displaystyle Phi _{n}left((-1)^{frac {n-1}{2}}zright)=C_{n}^{2}(z)-nzD_{n}^{2}(z).}

Si n es par, sin cuadrados y mayor que 2 (esto obliga a n/2 a ser impar),

{displaystyle Phi _{frac {n}{2}}left(-z^{2}right)=Phi _{2n}(z)=C_{n}^{2}(z)-nzD_{n}^{2}(z)}

donde tanto C_n(z) como D_n(z) tiene coeficientes enteros, C_n(z) tiene grado φ(n), y D_n(z) tiene grado φ( n) − 1. C_n(z) y D_n(z) son ambos palindrómicos.

Los primeros casos son:

{displaystyle {begin{aligned}Phi _{3}(-z)&=Phi _{6}(z)=z^{2}-z+1\&=(z+1)^{2}-3z\[6pt]Phi _{5}(z)&=z^{4}+z^{3}+z^{2}+z+1\&=(z^{2}+3z+1)^{2}-5z(z+1)^{2}\[6pt]Phi _{6/2}(-z^{2})&=Phi _{12}(z)=z^{4}-z^{2}+1\&=(z^{2}+3z+1)^{2}-6z(z+1)^{2}end{aligned}}}

Conjetura de la hermana Beiter

La conjetura de la Hermana Beiter está preocupada por el tamaño máximo (en valor absoluto) ${displaystyle A(pqr)}$ de los coeficientes polinomios ciclotómicos ternarios ${displaystyle Phi _{pqr}(x)}$ Donde ${displaystyle 3leq pleq qleq r}$ son tres números primos.

Polinomios ciclotómicos sobre un campo finito y sobre los enteros p-ádicos

Sobre un campo finito con un número primo $p$ de elementos, para cualquier entero $n$ que no es un múltiple $p$ , el polinomio ciclotómico $Phi _{n}$ factoriza en ${displaystyle {frac {varphi (n)}{d}}}$ polinomios irreducibles de grado $d$ , donde $varphi (n)$ es la función totient de Euler y $d$ es el orden multiplicativo $p$ modulo $n$ . En particular, $Phi _{n}$ es irreducible si y sólo si $p$ es una raíz primitiva modulo n, es decir, $p$ no divide $n$ , y su modulo de orden multiplicativo $n$ es $varphi (n)$ , el grado de $Phi _{n}$ .

Estos resultados también son ciertos sobre los enteros p-ádicos, ya que el lema de Hensel permite levantar una factorización sobre el campo con elementos $p$ a un factorización sobre los enteros $p$ -ádicos.

Valores de polinomios

Si $x$ toma cualquier valor real, entonces $0}" xmlns="http://www.w3.org/1998/Math/MathML">CCPR CCPR n()x)■0{displaystyle Phi _{n}(x) confía0}0}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5a1c422b585b2f92a5267c805e0e978b9b329335" style="vertical-align: -0.838ex; width:10.296ex; height:2.843ex;"/>$ para todos $n \geq 3$ (esto se deriva del hecho de que las raíces de un polinomio ciclotómico son todas no reales, para $n \geq 3$ ).

Para estudiar los valores que un polinomio ciclotómico puede tomar cuando $x$ se da un valor entero, basta considerar sólo el caso $n \geq 3$ , como los casos $n = 1$ y $n = 2$ son triviales (uno tiene ${displaystyle Phi _{1}(x)=x-1}$ y ${displaystyle Phi _{2}(x)=x+1}$ ).

Para $n \geq 2$ , uno tiene

{displaystyle Phi _{n}(0)=1,}

{displaystyle Phi _{n}(1)=1}

n

no es un poder primario,

{displaystyle Phi _{n}(1)=p}

n=p^{k}

es un poder primario con

k \geq 1

Los valores que un polinomio ciclotómico $Phi _{n}(x)$ puede tomar para otros valores enteros $x$ está fuertemente relacionado con el modulo de orden multiplicativo un número primo.

Más precisamente, dado un número primo $p$ y un entero $b$ coprime con $p$ , el orden multiplicativo $b$ modulo $p$ , es el entero positivo más pequeño $n$ tales que $p$ es un divisor de ${displaystyle b^{n}-1.}$ Para $b ■ 1$ , el orden multiplicativo $b$ modulo $p$ es también el período más corto de la representación de $1/ p$ en la base numeral $b$ (ver Unique prime; esto explica la elección de notación).

La definición del orden multiplicativo implica que, si $n$ es el orden multiplicativo $b$ modulo $p$ , entonces $p$ es un divisor de ${displaystyle Phi _{n}(b).}$ El contrario no es cierto, pero uno tiene lo siguiente.

Si $n > 0$ es un número entero positivo y $b > 1$ es un número entero, entonces (ver más abajo para una prueba)

{displaystyle Phi _{n}(b)=2^{k}gh,}

dónde

$k$ es un entero no negativo, siempre igual a 0 cuando $b$ es incluso. (De hecho, si $n$ no es 1 ni 2, entonces $k$ es 0 o 1. Además, si $n$ no es un poder de 2, entonces $k$ es siempre igual a 0)
$g$ es 1 o el factor principal más grande $n$ .
$h$ es raro, coprime con $n$ , y sus factores principales son exactamente los principios impares $p$ tales que $n$ es el orden multiplicativo $b$ modulo $p$ .

Esto implica que, si $p$ es un divisor primitivo raro ${displaystyle Phi _{n}(b),}$ entonces $n$ es un divisor de $p - 1$ o $p$ es un divisor de $n$ . En este último caso, $p^{2}$ no divide ${displaystyle Phi _{n}(b).}$

El teorema de Zsigmondy implica que los únicos casos en los que $b > 1$ y $h = 1$ son

0\Phi _{6}(2)&=3end{aligned}}}" xmlns="http://www.w3.org/1998/Math/MathML">CCPR CCPR 1()2)=1CCPR CCPR 2()2k− − 1)=2kk■0CCPR CCPR 6()2)=3{displaystyle {begin{aligned}phi _{1}(2) ¿Por qué?0\Phi _{6}(2)&=3end{aligned}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a4fde95495f0213d51e76724b6b71e019e012d25" style="vertical-align: -4.338ex; width:27.722ex; height:9.843ex;"/>

De la factorización anterior se deduce que los factores primos impares de

{displaystyle {frac {Phi _{n}(b)}{gcd(n,Phi _{n}(b))}}}

son exactamente los primos impares $p$ tales que $n$ es el orden multiplicativo de $b$ módulo $p$ . Esta fracción puede ser par solo cuando $b$ es impar. En este caso, el orden multiplicativo de $b$ módulo $2$ siempre es $1.$

Hay muchos pares $() n, b)$ con $b ■ 1$ tales que $Phi _{n}(b)$ es primo. De hecho, la conjetura Bunyakovsky implica que, por cada $n$ , hay infinitamente muchos $b ■ 1$ tales que $Phi _{n}(b)$ es primo. See OEIS: A085398 para la lista de los más pequeños $b ■ 1$ tales que $Phi _{n}(b)$ es primo (el más pequeño $b ■ 1$ tales que $Phi _{n}(b)$ es sobre primo ${displaystyle lambda cdot varphi (n)}$ , donde $lambda$ es Euler-Mascheroni constante, y $varphi$ es la función totiente de Euler). Véase también OEIS: A206864 para la lista de los primos más pequeños de la forma $Phi _{n}(b)$ con $n ■ 2$ y $b ■ 1$ , y, más generalmente, OEIS: A206942, para los números más pequeños positivos de esta forma.

Pruebas
Valores de ${displaystyle Phi _{n}(1).}$ Si ${displaystyle n=p^{k+1}}$ es un poder primario, entonces ${displaystyle Phi _{n}(x)=1+x^{p^{k}}+x^{2p^{k}}+cdots +x^{(p-1)p^{k}}qquad {text{and}}qquad Phi _{n}(1)=p.}$ Si $n$ no es un poder primario, vamos ${displaystyle P(x)=1+x+cdots +x^{n-1},}$ tenemos ${displaystyle P(1)=n,}$ y $P$ es el producto del ${displaystyle Phi _{k}(x)}$ para $k$ división $n$ y diferentes de $1$ . Si $p$ es un divisor primario de la multiplicidad $m$ dentro $n$ , entonces ${displaystyle Phi _{p}(x),Phi _{p^{2}}(x),cdotsPhi _{p^{m}}(x)}$ dividir $P () x)$ , y sus valores en $1$ son $m$ factores iguales a los $p$ de ${displaystyle n=P(1).}$ As $m$ es la multiplicidad de $p$ dentro $n$ , $p$ no puede dividir el valor $1$ de los demás factores ${displaystyle P(x).}$ Por lo tanto no hay prima que divide ${displaystyle Phi _{n}(1).}$ Si $n$ es el orden multiplicativo $b$ modulo $p$ , entonces ${displaystyle pmid Phi _{n}(b).}$ Por definición, ${displaystyle pmid b^{n}-1.}$ Si ${displaystyle pnmid Phi _{n}(b),}$ entonces $p$ dividiría otro factor ${displaystyle Phi _{k}(b)}$ de ${displaystyle b^{n}-1,}$ y así dividir ${displaystyle b^{k}-1,}$ mostrando que, si hubiera el caso, $n$ no sería el orden multiplicativo $b$ modulo $p$ . Los otros divisores principales de $Phi _{n}(b)$ son divisores de $n$ . Vamos $p$ ser un divisor de primera $Phi _{n}(b)$ tales que $n$ no es el orden multiplicativo $b$ modulo $p$ . Si $k$ es el orden multiplicativo $b$ modulo $p$ , entonces $p$ divide ambos $Phi _{n}(b)$ y ${displaystyle Phi _{k}(b).}$ El resultado de $Phi _{n}(x)$ y ${displaystyle Phi _{k}(x)}$ puede ser escrito ${displaystyle PPhi _{k}+QPhi _{n},}$ Donde $P$ y $Q$ son polinomios. Así $p$ divide este resultado. As $k$ divideciones $n$ , y el resultado de dos polinomios divide el discriminante de cualquier múltiple común de estos polinomios, $p$ divide también el discriminante $n^n$ de $x^{n}-1.$ Así $p$ divideciones $n$ . $g$ y $h$ son coprime. En otras palabras, si $p$ es un divisor común de primera $n$ y ${displaystyle Phi _{n}(b),}$ entonces $n$ no es el orden multiplicativo $b$ modulo $p$ . Por el pequeño teorema de Fermat, el orden multiplicativo $b$ es un divisor de $p - 1$ , y por lo tanto más pequeño que $n$ . $g$ es libre de cuadrado. En otras palabras, si $p$ es un divisor común de primera $n$ y ${displaystyle Phi _{n}(b),}$ entonces $p^{2}$ no divide ${displaystyle Phi _{n}(b).}$ Vamos $n = pm$ . Basta probar que $p^{2}$ no divide $S () b)$ para algunos polinomios $S () x)$ , que es un múltiplo de ${displaystyle Phi _{n}(x).}$ Nos llevamos ${displaystyle S(x)={frac {x^{n}-1}{x^{m}-1}}=1+x^{m}+x^{2m}+cdots +x^{(p-1)m}.}$ El orden multiplicativo $b$ modulo $p$ divideciones $gcd(n, p -1)$ , que es un divisor de $m = n / p$ . Así $c = b m - 1$ es un múltiple de $p$ . Ahora, ${displaystyle S(b)={frac {(1+c)^{p}-1}{c}}=p+{binom {p}{2}}c+cdots +{binom {p}{p}}c^{p-1}.}$ As $p$ es primo y mayor que 2, todos los términos pero el primero son múltiplos ${displaystyle p^{2}.}$ Esto prueba que ${displaystyle p^{2}nmid Phi _{n}(b).}$

Pruebas

Valores de ${displaystyle Phi _{n}(1).}$ Si ${displaystyle n=p^{k+1}}$ es un poder primario, entonces

{displaystyle Phi _{n}(x)=1+x^{p^{k}}+x^{2p^{k}}+cdots +x^{(p-1)p^{k}}qquad {text{and}}qquad Phi _{n}(1)=p.}

n

no es un poder primario, vamos

{displaystyle P(x)=1+x+cdots +x^{n-1},}

tenemos

{displaystyle P(1)=n,}

P

es el producto del

{displaystyle Phi _{k}(x)}

para

k

división

n

y diferentes de

1

. Si

p

es un divisor primario de la multiplicidad

m

dentro

n

, entonces

{displaystyle Phi _{p}(x),Phi _{p^{2}}(x),cdotsPhi _{p^{m}}(x)}

dividir

P () x)

, y sus valores en

1

son

m

factores iguales a los

p

{displaystyle n=P(1).}

m

es la multiplicidad de

p

dentro

n

p

no puede dividir el valor

1

de los demás factores

{displaystyle P(x).}

Por lo tanto no hay prima que divide

{displaystyle Phi _{n}(1).}

Si $n$ es el orden multiplicativo $b$ modulo $p$ , entonces ${displaystyle pmid Phi _{n}(b).}$ Por definición, ${displaystyle pmid b^{n}-1.}$ Si ${displaystyle pnmid Phi _{n}(b),}$ entonces $p$ dividiría otro factor ${displaystyle Phi _{k}(b)}$ de ${displaystyle b^{n}-1,}$ y así dividir ${displaystyle b^{k}-1,}$ mostrando que, si hubiera el caso, $n$ no sería el orden multiplicativo $b$ modulo $p$ .

Los otros divisores principales de $Phi _{n}(b)$ son divisores de $n$ . Vamos $p$ ser un divisor de primera $Phi _{n}(b)$ tales que $n$ no es el orden multiplicativo $b$ modulo $p$ . Si $k$ es el orden multiplicativo $b$ modulo $p$ , entonces $p$ divide ambos $Phi _{n}(b)$ y ${displaystyle Phi _{k}(b).}$ El resultado de $Phi _{n}(x)$ y ${displaystyle Phi _{k}(x)}$ puede ser escrito ${displaystyle PPhi _{k}+QPhi _{n},}$ Donde $P$ y $Q$ son polinomios. Así $p$ divide este resultado. As $k$ divideciones $n$ , y el resultado de dos polinomios divide el discriminante de cualquier múltiple común de estos polinomios, $p$ divide también el discriminante $n^n$ de $x^{n}-1.$ Así $p$ divideciones $n$ .

$g$ y $h$ son coprime. En otras palabras, si $p$ es un divisor común de primera $n$ y ${displaystyle Phi _{n}(b),}$ entonces $n$ no es el orden multiplicativo $b$ modulo $p$ . Por el pequeño teorema de Fermat, el orden multiplicativo $b$ es un divisor de $p - 1$ , y por lo tanto más pequeño que $n$ .

$g$ es libre de cuadrado. En otras palabras, si $p$ es un divisor común de primera $n$ y ${displaystyle Phi _{n}(b),}$ entonces $p^{2}$ no divide ${displaystyle Phi _{n}(b).}$ Vamos $n = pm$ . Basta probar que $p^{2}$ no divide $S () b)$ para algunos polinomios $S () x)$ , que es un múltiplo de ${displaystyle Phi _{n}(x).}$ Nos llevamos

{displaystyle S(x)={frac {x^{n}-1}{x^{m}-1}}=1+x^{m}+x^{2m}+cdots +x^{(p-1)m}.}

El orden multiplicativo

b

modulo

p

divideciones

gcd(n, p -1)

, que es un divisor de

m = n / p

. Así

c = b m - 1

es un múltiple de

p

. Ahora,

{displaystyle S(b)={frac {(1+c)^{p}-1}{c}}=p+{binom {p}{2}}c+cdots +{binom {p}{p}}c^{p-1}.}

p

es primo y mayor que 2, todos los términos pero el primero son múltiplos

{displaystyle p^{2}.}

Esto prueba que

{displaystyle p^{2}nmid Phi _{n}(b).}

Aplicaciones

Uso $Phi _{n}$ , uno puede dar una prueba elemental para la infinitud de primos congruentes a 1 modulo n, que es un caso especial del teorema de Dirichlet sobre progresiones aritméticas.

Prueba
Suppose ${displaystyle p_{1},p_{2},ldotsp_{k}}$ es una lista finita de primos congruentes a $1$ modulo $n.$ Vamos ${displaystyle N=np_{1}p_{2}cdots p_{k}}$ y considerar ${displaystyle Phi _{n}(N)}$ . Vamos $q$ ser un factor principal ${displaystyle Phi _{n}(N)}$ (para ver eso ${displaystyle Phi _{n}(N)neq pm 1}$ descomponerlo en factores lineales y observar que 1 es la raíz más cercana de la unidad a $N$ ). Desde ${displaystyle Phi _{n}(x)equiv pm 1{pmod {x}},}$ sabemos que $q$ es un nuevo primo no en la lista. Vamos a mostrar que ${displaystyle qequiv 1{pmod {n}}.}$ Vamos $m$ ser el orden $N$ modulo $q.$ Desde ${displaystyle Phi _{n}(N)mid N^{n}-1}$ tenemos ${displaystyle N^{n}-1equiv 0{pmod {q}}}$ . Así ${displaystyle mmid n}$ . Vamos a mostrar que $m=n$ . Asumo de contradicción $<math alttext="{displaystyle mm.n{displaystyle m won} <img alt="m$ . Desde ${displaystyle prod _{dmid m}Phi _{d}(N)=N^{m}-1equiv 0{pmod {q}}}$ tenemos ${displaystyle Phi _{d}(N)equiv 0{pmod {q}},}$ para algunos $<math alttext="{displaystyle dd.n{displaystyle d maden} <img alt="{displaystyle d$ . Entonces... $N$ es una raíz doble ${displaystyle prod _{dmid n}Phi _{d}(x)equiv x^{n}-1{pmod {q}}.}$ Así $N$ debe ser una raíz del derivado así ${displaystyle left.{frac {d(x^{n}-1)}{dx}}right\|_{N}equiv nN^{n-1}equiv 0{pmod {q}}.}$ Pero... ${displaystyle qnmid N}$ por lo tanto ${displaystyle qnmid n.}$ Es una contradicción. $m=n$ . El orden ${displaystyle N{pmod {q}},}$ que es $n$ , debe dividir $q-1$ . Así ${displaystyle qequiv 1{pmod {n}}.}$

Prueba

Suppose ${displaystyle p_{1},p_{2},ldotsp_{k}}$ es una lista finita de primos congruentes a $1$ modulo $n.$ Vamos ${displaystyle N=np_{1}p_{2}cdots p_{k}}$ y considerar ${displaystyle Phi _{n}(N)}$ . Vamos $q$ ser un factor principal ${displaystyle Phi _{n}(N)}$ (para ver eso ${displaystyle Phi _{n}(N)neq pm 1}$ descomponerlo en factores lineales y observar que 1 es la raíz más cercana de la unidad a $N$ ). Desde ${displaystyle Phi _{n}(x)equiv pm 1{pmod {x}},}$ sabemos que $q$ es un nuevo primo no en la lista. Vamos a mostrar que ${displaystyle qequiv 1{pmod {n}}.}$

Vamos $m$ ser el orden $N$ modulo $q.$ Desde ${displaystyle Phi _{n}(N)mid N^{n}-1}$ tenemos ${displaystyle N^{n}-1equiv 0{pmod {q}}}$ . Así ${displaystyle mmid n}$ . Vamos a mostrar que $m=n$ .

Asumo de contradicción $<math alttext="{displaystyle mm.n{displaystyle m won} <img alt="m$ . Desde

{displaystyle prod _{dmid m}Phi _{d}(N)=N^{m}-1equiv 0{pmod {q}}}

tenemos

{displaystyle Phi _{d}(N)equiv 0{pmod {q}},}

para algunos $<math alttext="{displaystyle dd.n{displaystyle d maden} <img alt="{displaystyle d$ . Entonces... $N$ es una raíz doble

{displaystyle prod _{dmid n}Phi _{d}(x)equiv x^{n}-1{pmod {q}}.}

Así $N$ debe ser una raíz del derivado así

{displaystyle left.{frac {d(x^{n}-1)}{dx}}right|_{N}equiv nN^{n-1}equiv 0{pmod {q}}.}

Pero... ${displaystyle qnmid N}$ por lo tanto ${displaystyle qnmid n.}$ Es una contradicción. $m=n$ . El orden ${displaystyle N{pmod {q}},}$ que es $n$ , debe dividir $q-1$ . Así ${displaystyle qequiv 1{pmod {n}}.}$

Contenido relacionado

Más resultados...