Raíz de la unidad módulo n

En teoría de números , una raíz k -ésima de la unidad módulo n para números enteros positivos k , n  ≥ 2, es una raíz de la unidad en el anillo de números enteros módulo n ; es decir, una solución x de la ecuación (o congruencia ) . Si k es el exponente más pequeño de x , entonces x se denomina raíz k- ésima primitiva de la unidad módulo n . ^[1] Véase aritmética modular para notación y terminología. ${\displaystyle x^{k}\equiv 1{\pmod {n}}}$

Las raíces de la unidad módulo n son exactamente los números enteros que son coprimos con n . De hecho, estos números enteros son raíces de la unidad módulo n según el teorema de Euler , y los otros números enteros no pueden ser raíces de la unidad módulo n , porque son divisores de cero módulo n .

Una raíz primitiva módulo n , es un generador del grupo de unidades del anillo de números enteros módulo n . Existen raíces primitivas módulo n si y sólo si donde y son respectivamente la función de Carmichael y la función totient de Euler . ${\displaystyle \lambda (n)=\varphi (n),}$${\estilo de visualización \lambda}$${\estilo de visualización \varphi}$

Una raíz de unidad módulo n es una raíz k -ésima primitiva de unidad módulo n para algún divisor k de y, a la inversa, hay raíces k- ésimas primitivas de unidad módulo n si y solo si k es un divisor de${\displaystyle \lambda (n),}$${\displaystyle \lambda (n).}$

• Si x es una raíz k -ésima de la unidad módulo n , entonces x es una unidad (invertible) cuyo inverso es . Es decir, x y n son coprimos .$estilo de visualización x^{k-1}}$
• Si x es una unidad, entonces es una raíz k (primitiva) de la unidad módulo n , donde k es el orden multiplicativo de x módulo n .
• Si x es una raíz k -ésima de la unidad y no es divisor de cero , entonces , porque${\estilo de visualización x-1}$${\displaystyle \suma _{j=0}^{k-1}x^{j}\equiv 0{\pmod {n}}}$

${\displaystyle (x-1)\cdot \sum _{j=0}^{k-1}x^{j}\equiv x^{k}-1\equiv 0{\pmod {n}}.}$

A falta de un símbolo ampliamente aceptado, denotamos el número de raíces k de la unidad módulo n por . Satisface una serie de propiedades: ${\displaystyle f(n,k)}$

• ${\displaystyle f(n,1)=1}$para${\displaystyle n\geq 2}$
• ${\displaystyle f(n,\lambda (n))=\varphi (n)}$donde λ denota la función de Carmichael y denota la función totiente de Euler${\estilo de visualización \varphi}$
• ${\displaystyle n\mapsto f(n,k)}$es una función multiplicativa
• ${\displaystyle k\mid \ell \implica f(n,k)\mid f(n,\ell )}$donde la barra denota divisibilidad
• ${\displaystyle f(n,\nombre del operador {mcm} (a,b))=\nombre del operador {mcm} (f(n,a),f(n,b))}$donde denota el mínimo común múltiplo${\displaystyle \operatorname {mcm} }$
• Para primos , no se conoce la aplicación precisa de a . Si se conociera, junto con la ley anterior, obtendríamos una forma de evaluar rápidamente.${\estilo de visualización p}$${\displaystyle \para todo i\en \mathbb {N} \ \existe j\en \mathbb {N} \ f(n,p^{i})=p^{j}}$${\estilo de visualización i}$${\estilo de visualización j}$${\estilo de visualización f}$

Sea y . En este caso, hay tres raíces cúbicas de la unidad (1, 2 y 4). Sin embargo, cuando solo hay una raíz cúbica de la unidad, la unidad 1 en sí. Este comportamiento es bastante diferente del campo de los números complejos donde cada número distinto de cero tiene k raíces k ésimas.${\estilo de visualización n=7}$${\displaystyle k=3}$${\estilo de visualización n=11}$

• El exponente de base máximo posible para raíces primitivas módulo es , donde λ denota la función de Carmichael .${\estilo de visualización n}$${\displaystyle \lambda (n)}$
• Un exponente de base para una raíz primitiva de la unidad es un divisor de .${\displaystyle \lambda (n)}$
• Todo divisor de produce una raíz primitiva de la unidad. Se puede obtener dicha raíz eligiendo una raíz primitiva de la unidad (que debe existir por definición de λ), llamándola y calculando la potencia .${\estilo de visualización k}$${\displaystyle \lambda (n)}$${\estilo de visualización k}$${\displaystyle \lambda (n)}$${\estilo de visualización x}$${\displaystyle x^{\lambda (n)/k}}$
• Si x es una raíz k- ésima primitiva de la unidad y también una raíz ℓ- ésima (no necesariamente primitiva) de la unidad, entonces k es un divisor de ℓ. Esto es cierto, porque la identidad de Bézout produce una combinación lineal entera de k y ℓ igual a . Como k es mínimo, debe ser y es un divisor de  ℓ .${\displaystyle \mcd(k,\ell )}$${\displaystyle k=\mcd(k,\ell )}$${\displaystyle \mcd(k,\ell )}$

A falta de un símbolo ampliamente aceptado, denotamos el número de raíces k primitivas de la unidad módulo n por . Satisface las siguientes propiedades: ${\displaystyle g(n,k)}$

• ${\displaystyle g(n,k)={\begin{cases}>0&{\text{si }}k\mid \lambda (n),\\0&{\text{en caso contrario}}.\end{cases}}}$
• En consecuencia la función tiene valores distintos de cero, donde calcula el número de divisores .${\displaystyle k\mapsto g(n,k)}$${\displaystyle d(\lambda (n))}$${\estilo de visualización d}$
• ${\displaystyle g(n,1)=1}$
• ${\displaystyle g(4,2)=1}$
• ${\displaystyle g(2^{n},2)=3}$para , ya que -1 siempre es una raíz cuadrada de 1.${\displaystyle n\geq 3}$
• ${\displaystyle g(2^{n},2^{k})=2^{k}}$para${\displaystyle k\en [2,n-1)}$
• ${\displaystyle g(n,2)=1}$para y en (secuencia A033948 en la OEIS )${\displaystyle n\geq 3}$${\estilo de visualización n}$
• ${\displaystyle \sum _{k\in \mathbb {N} }g(n,k)=f(n,\lambda (n))=\varphi (n)}$siendo la función totiente de Euler${\estilo de visualización \varphi}$
• La conexión entre y se puede escribir de manera elegante utilizando una convolución de Dirichlet :${\estilo de visualización f}$${\estilo de visualización g}$

${\displaystyle f=\mathbf {1} *g}$, es decir${\displaystyle f(n,k)=\sum _{d\mid k}g(n,d)}$

Se pueden calcular valores de forma recursiva utilizando esta fórmula, que es equivalente a la fórmula de inversión de Möbius .${\displaystyle g}$${\displaystyle f}$

Mediante la exponenciación rápida , se puede comprobar que . Si esto es cierto, x es una raíz k- ésima de la unidad módulo n, pero no necesariamente primitiva. Si no es una raíz primitiva, entonces habría algún divisor ℓ de k , con . Para excluir esta posibilidad, sólo hay que comprobar si hay algunos ℓ iguales a k dividido por un primo. Es decir, lo que hay que comprobar es: ${\displaystyle x^{k}\equiv 1{\pmod {n}}}$${\displaystyle x^{\ell }\equiv 1{\pmod {n}}}$

${\displaystyle \forall p{\text{ prime dividing}}\ k,\quad x^{k/p}\not \equiv 1{\pmod {n}}.}$

Entre las raíces primitivas k -ésimas de la unidad, las raíces primitivas th son las más frecuentes. Por lo tanto, se recomienda probar algunos números enteros como raíz primitiva th, lo que dará resultado rápidamente. Para una raíz primitiva th x , el número es una raíz primitiva th de la unidad. Si k no divide a , entonces no habrá raíces k -ésimas de la unidad en absoluto. ${\displaystyle \lambda (n)}$${\displaystyle \lambda (n)}$${\displaystyle \lambda (n)}$${\displaystyle x^{\lambda (n)/k}}$${\displaystyle k}$${\displaystyle \lambda (n)}$

Una vez que se obtiene una raíz k- ésima primitiva de la unidad x , toda potencia es una raíz k-ésima de la unidad, pero no necesariamente una primitiva. La potencia es una raíz k-ésima primitiva de la unidad si y solo si y son coprimos . La prueba es la siguiente: Si no es primitiva, entonces existe un divisor de con , y como y son coprimos, existen números enteros tales que . Esto da ${\displaystyle x^{\ell }}$${\displaystyle k}$${\displaystyle x^{\ell }}$${\displaystyle k}$${\displaystyle k}$${\displaystyle \ell }$${\displaystyle x^{\ell }}$${\displaystyle m}$${\displaystyle k}$${\displaystyle (x^{\ell })^{m}\equiv 1{\pmod {n}}}$${\displaystyle k}$${\displaystyle \ell }$${\displaystyle a,b}$${\displaystyle ak+b\ell =1}$

${\displaystyle x^{m}\equiv (x^{m})^{ak+b\ell }\equiv (x^{k})^{ma}((x^{\ell })^{m})^{b}\equiv 1{\pmod {n}}}$,

lo que significa que no es una raíz primitiva de la unidad porque existe el exponente menor . ${\displaystyle x}$${\displaystyle k}$${\displaystyle m}$

Es decir, al potenciar x se pueden obtener diferentes raíces primitivas k- ésimas de la unidad, pero puede que no todas sean raíces de ese tipo. Sin embargo, encontrarlas todas no es tan fácil. ${\displaystyle \varphi (k)}$

¿En qué anillos de clase de residuo entero existe una raíz k- ésima primitiva de la unidad? Se puede utilizar para calcular una transformada de Fourier discreta (más precisamente, una transformada teórica de números ) de un vector entero de dimensión . Para realizar la transformada inversa, se divide por ; es decir, k también es una unidad módulo${\displaystyle k}$${\displaystyle k}$${\displaystyle n.}$

Una forma sencilla de encontrar un n de este tipo es comprobar si existen raíces k -ésimas primitivas con respecto a los módulos en la progresión aritmética. Todos estos módulos son coprimos con k y, por lo tanto, k es una unidad. Según el teorema de Dirichlet sobre progresiones aritméticas, hay infinitos primos en la progresión y, para un primo , se cumple . Por lo tanto, si es primo, entonces , y, por lo tanto, existen raíces k- ésimas primitivas de la unidad. Pero la prueba para primos es demasiado estricta y puede haber otros módulos apropiados. ${\displaystyle k+1,2k+1,3k+1,\dots }$${\displaystyle p}$${\displaystyle \lambda (p)=p-1}$${\displaystyle mk+1}$${\displaystyle \lambda (mk+1)=mk}$

Para encontrar un módulo tal que haya raíces primitivas de unidad módulo , el siguiente teorema reduce el problema a uno más simple: ${\displaystyle n}$${\displaystyle k_{1}{\text{th}},k_{2}{\text{th}},\ldots ,k_{m}{\text{th}}}$${\displaystyle n}$

Porque dado que hay raíces primitivas de unidad módulo n si y sólo si hay una raíz primitiva de unidad módulo  n .${\displaystyle n}$${\displaystyle k_{1}{\text{th}},\ldots ,k_{m}{\text{th}}}$${\displaystyle n}$${\displaystyle \operatorname {lcm} (k_{1},\ldots ,k_{m})}$

Prueba

Dirección hacia atrás: Si existe una raíz primitiva de unidad módulo llamada , entonces es una raíz primitiva de unidad módulo . ${\displaystyle \operatorname {lcm} (k_{1},\ldots ,k_{m})}$${\displaystyle n}$${\displaystyle x}$${\displaystyle x^{\operatorname {lcm} (k_{1},\ldots ,k_{m})/k_{l}}}$${\displaystyle k_{l}}$${\displaystyle n}$

Dirección hacia adelante: Si hay raíces primitivas de unidad módulo , entonces todos los exponentes son divisores de . Esto implica y esto a su vez significa que hay una raíz primitiva de unidad módulo . ${\displaystyle k_{1}{\text{th}},\ldots ,k_{m}{\text{th}}}$${\displaystyle n}$${\displaystyle k_{1},\dots ,k_{m}}$${\displaystyle \lambda (n)}$${\displaystyle \operatorname {lcm} (k_{1},\dots ,k_{m})\mid \lambda (n)}$${\displaystyle \operatorname {lcm} (k_{1},\ldots ,k_{m})}$${\displaystyle n}$