Orden del número de módulo

El exponente , u orden multiplicativo , de un módulo entero es el entero positivo más pequeño tal que [1] [2] $a$ $metro$ $\ana$

a^{\ell }\equiv 1{\pmod {m)).

El exponente se define solo para números primos relativos al módulo , es decir, para elementos del grupo de elementos invertibles del anillo de residuos módulo . Además, si se define el exponente del número de módulo , entonces es un divisor del valor de la función de Euler (consecuencia del teorema de Lagrange ) y el valor de la función de Carmichael . $a$ $metro$ $metro$ $a$ $metro$ $\varfi(m)$ $\lambda(m)$

Para mostrar la dependencia del indicador de y , también se denota , y si es fijo, entonces simplemente . $\ana$ $a$ $metro$ $P_m(a)$ $metro$ $Pensilvania)$

Propiedades

$a\equiv b\pmod m\Rightarrow P(a)=P(b)$ , por lo que podemos suponer que el exponente se da en la clase de módulo de residuos . ${\ barra {a}}$ $metro$
$a^n\equiv 1\pmod m\Rightarrow P(a)\mid n$ . En particular, y , donde es la función de Carmichael y es la función de Euler . $P(a)\mid\lambda(m)$ $P(a)\mid\varphi(m)$ $\lambda(m)$ $\varfi(m)$
$a^t\equiv a^s\pmod m \Leftrightarrow t\equiv s\pmod{P(a)}.$
$P(a^s)\mid P(a)$ ; si , entonces $\gcd(s,P(a))=1$ $P(a^s)=P(a).$
Si es un número primo y , entonces son todas las soluciones de la comparación . $pags$ $P(a)=k$ ${\displaystyle a,\;\ldots,\;a^{k))$ $x^k\equiv 1\pmod p$
Si es un número primo, entonces es un generador del grupo . $pags$ $P(a)=p-1\Flecha izquierda-derecha a$ $\mathbb {Z} _{p}$
Si es el número de clases de residuos con el indicador , entonces . E incluso para módulos simples . $\psi(k)$ $k$ $\sum \limits _{k\,\mid \,\varphi (m)}\psi (k)=\varphi (m)$ $\psi(k)=\varphi(k)$
Si es un número primo, entonces el grupo residuo es cíclico y, por lo tanto, si , donde es un generador, y es coprimo con , entonces . En el caso general, para un módulo arbitrario , se puede derivar una fórmula similar usando el teorema sobre la estructura del grupo de residuos multiplicativo . $pags$ ${\mathbb {Z}}_{p}^{{\veces}}$ $a=g^{dk}$ $gramo$ $d\mid p-1$ $k$ $p-1$ $P(a)=\frac{p-1}{d}$ $metro$ ${\mathbb {Z}}_{m}^{{\veces}}$

Ejemplo

Como , pero , , , entonces el orden de 2 módulo 15 es 4. $2^4\equivalente a 1\pmod{15}$ $2^1\no\equivalente a 1\pmod{15}$ $2^2\no\equivalente a 1\pmod{15}$ $2^3\no\equivalente a 1\pmod{15}$

Cálculo

Si se conoce la descomposición del módulo en factores primos y se conoce la descomposición de números en factores primos, entonces el exponente de un número dado se puede encontrar en tiempo polinomial desde . Para calcular, basta con encontrar la factorización de la función de Carmichael y calcular todo por todo . Dado que el número de divisores está limitado por el polinomio de , y el módulo de exponenciación ocurre en tiempo polinomial, el algoritmo de búsqueda será polinomial. $metro$ $p_{j}$ $p_j-1$ $a$ $\ln m$ $\lambda(m)$ $a^{d}\mod m$ $d\mid \lambda (m)$ $\ln m$

Aplicaciones

Personajes de Dirichlet

El módulo de carácter de Dirichlet está determinado por las relaciones obligatorias y . Para que estas relaciones se mantengan, es necesario que sea igual a alguna raíz compleja de unidad . $\ chi$ $metro$ $\chi(ab)=\chi(a)\chi(b)$ $\chi(a)=\chi(a+m)$ $\chi(a)$ $P_{m}(a)$

Orden del número de módulo

Propiedades

Ejemplo

Cálculo

Aplicaciones

Personajes de Dirichlet

Véase también

Notas

Literatura