En matemáticas , es decir , la teoría de anillos , una k -ésima raíz de la unidad módulo n para 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 a la ecuación (o congruencia ). Si k es el exponente más pequeño de x , entonces x se llama una raíz k -ésima primitiva de módulo unitario n . [1] Ver aritmética modular para notación y terminología.
No confunda esto con una raíz primitiva módulo n , que es un generador del grupo de unidades del anillo de números enteros módulo n . Las raíces primitivas módulo n son las primitivas-raíces de unidad módulo n , dondees la función totient de Euler .
Raíces de unidad
Propiedades
- Si x es una k -ésima raíz de la unidad módulo n , entonces x es una unidad (invertible) cuya inversa es. Es decir, X y n son primos entre sí .
- Si x es una unidad, entonces es una k -ésima raíz (primitiva) de la unidad módulo n , donde k es el orden multiplicativo de x módulo n .
- Si x es una k -ésima raíz de la unidad yno es un divisor de cero , entonces, porque
Número de raíces k -ésimas
A falta de un símbolo ampliamente aceptado, denotamos el número de k -ésimas raíces de la unidad módulo n por. Satisface una serie de propiedades:
- por
- donde λ denota la función de Carmichael ydenota la función totient de Euler
- es una función multiplicativa
- donde la barra denota divisibilidad
- dónde denota el mínimo común múltiplo
- Para prima , . El mapeo preciso de a no es conocido. Si se conociera, entonces, junto con la ley anterior, daría una forma de evaluar rápidamente.
Raíces primitivas de la unidad
Propiedades
- El máximo exponente de raíz posible para raíces primitivas módulo es , donde λ denota la función de Carmichael .
- Un exponente de base para una raíz primitiva de unidad es un divisor de.
- Cada divisor de produce un primitivo -ésima raíz de la unidad. Puede obtener uno eligiendo un-ésima raíz primitiva de la unidad (que debe existir por definición de λ), llamada y calcular la potencia .
- Si x es una raíz k -ésima primitiva de la unidad y también una raíz ℓ-ésima de la unidad (no necesariamente primitiva), 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. Dado que k es mínimo, debe ser y es un divisor de ℓ.
Número de raíces k primitivas
A falta de un símbolo ampliamente aceptado, denotamos el número de k -ésimas raíces primitivas de unidad módulo n por. Satisface las siguientes propiedades:
- En consecuencia, la función posee valores diferentes de cero, donde calcula el número de divisores .
- por , ya que -1 es siempre una raíz cuadrada de 1.
- por
- por y en (secuencia A033948 en la OEIS )
- con siendo la función totient de Euler
- La conexión entre y se puede escribir de una manera elegante usando una convolución de Dirichlet :
- , es decir
- Puede calcular valores de recursivamente desde utilizando esta fórmula, que es equivalente a la fórmula de inversión de Möbius .
Prueba de si x es una raíz k primitiva de la unidad módulo n
Mediante una exponenciación rápida 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 unos pocos ℓ iguales a k divididos por un primo. Es decir, lo que debe comprobarse es:
Encontrar una raíz k -ésima primitiva de la unidad módulo n
Entre las k -ésimas raíces primitivas de la unidad, la primitiva-ésimas raíces son las más frecuentes. Por tanto, se recomienda probar algunos enteros por ser un primitivo-th root, lo que tendrá éxito rápidamente. Para un primitivo-th raíz x , el número es un primitivo -ésima raíz de la unidad. Si k no divide, entonces no habrá k -ésimas raíces de unidad, en absoluto.
Encontrar múltiples raíces k -ésimas primitivas módulo n
Una vez que tenga una raíz k -ésima primitiva de la unidad x , cada potencia es un -ésima raíz de la unidad, pero no necesariamente primitiva. El poder es un primitivo -ésima raíz de la unidad si y solo si y son coprime . La prueba es la siguiente: Si no es primitivo, entonces existe un divisor de con , y desde y son coprime, existe una inversa de modulo . Esto produce, Lo que significa que no es un primitivo -ésima raíz de la unidad porque existe el exponente más pequeño .
Es decir, exponencializando x se puede obtenerdiferentes raíces k -ésimas primitivas de unidad, pero pueden no ser todas esas raíces. Sin embargo, encontrarlos todos no es tan fácil.
Encontrar una n con una raíz k primitiva de unidad módulo n
Es posible que desee saber, en qué anillos de clases de residuos enteros tiene una raíz k -ésima primitiva de la unidad. Lo necesita, por ejemplo, si desea calcular una transformada discreta de Fourier (más precisamente una transformada teórica numérica ) de unnúmero entero -dimensional vector . Para realizar la transformación inversa, también necesita dividir por, es decir, k también será una unidad módulo
Una forma sencilla de encontrar tal n es comprobar las raíces k -ésimas primitivas con respecto a los módulos en la progresión aritmética . Todos estos módulos son coprimos de k y, por tanto, k es una unidad. Según el teorema de Dirichlet sobre progresiones aritméticas, hay infinitos números primos en la progresión, y para un primo se mantiene . Así que si es primo entonces y así tienes k -ésimas raíces primitivas de unidad. Pero la prueba de los números primos es demasiado fuerte, puede encontrar otros módulos apropiados.
Encontrar una n con múltiples raíces primitivas de unidad módulo n
Si quieres tener un módulo tal que hay primitivos -th, -th, ..., -th raíces de la unidad módulo , el siguiente teorema reduce el problema a uno más simple:
- Por dado hay primitivos -th, ..., -th raíces de la unidad módulo si y solo si hay un primitivo -ésima raíz de la unidad módulo n .
- Prueba
Dirección hacia atrás: si hay una primitiva -th raíz de módulo de unidad llamada , luego es un -th raíz de módulo de unidad .
Dirección de avance: si hay primitivos -th, ..., -th raíces de la unidad módulo , luego todos los exponentes son divisores de . Esto implica y esto a su vez significa que hay un primitivo -th raíz de módulo de unidad .
Referencias
- ^ Finch, Stephen; Martin, Greg; Sebah y Pascal (2010). "Raíces de unidad y nulidad módulo n " (PDF) . Actas de la American Mathematical Society . 138 (8): 2729–2743. doi : 10.1090 / s0002-9939-10-10341-4 . Consultado el 20 de febrero de 2011 .