AMIGOS PARA SIEMPRE: ÁLGEBRA ABSTRACTA

ARITMÉTICA MODULAR :
En teoría de números, concretamente en aritmética modular, el criterio de Euler es utilizado para calcular si un número entero x es un residuo cuadrático módulo un número primo. Su nombre se debe al matemático suizo Leonhard Euler.

Sea p > 2 un número primo. Entonces x es un residuo cuadrático módulo p si y sólo si

x^{(p-1)/2} \equiv 1 \pmod p

Como corolario de este teorema se obtiene que:

Si x no es un residuo cuadrático módulo p entonces

x^{(p - 1)/2} \equiv -1 \pmod p.

Así, el criterio de Euler puede ser reformulado de manera más compacta usando el símbolo de Legendre:

x^{(p-1)/2} \equiv \left(\frac{x}{p}\right) \pmod p.

Supongamos que

x \equiv y^2 \pmod p

. Se sabe por el pequeño teorema de Fermat que si p es primo, entonces

x^{p-1} \equiv 1 \pmod p

. Luego tenemos

$x^{(p-1)/2}$	$\equiv (y^2)^{(p-1)/2} \pmod p$
	$\equiv y^{p-1} \pmod p$
	$\equiv 1 \pmod p$

A la inversa, suponemos que

x^{(p-1)/2} \equiv 1 \pmod p

. Sea b un elemento primitivo modulo p. Entonces

x \equiv b^i \pmod p

para algún i. Entonces tenemos

$x^{(p-1)/2}$	$\equiv (b^i)^{(p-1)/2} \pmod p$
	$\equiv b^{i(p-1)/2} \pmod p$

Como b es de orden p-1, debe darse el caso que p-1 divide a i(p-1)/2. Por lo tanto, i es par, y las raíces cuadradas de x son

\pm b^{i/2}

For

an odd prime and a positive integer

which is not a multiple of

where

is the Legendre symbol.

La exponenciación modular es un tipo de exponenciación realizada sobre un módulo. Es particularmente útil en ciencias de la computación, especialmente en el campo de lacriptografía.

Una «exponenciación modular» calcula el residuo cuando un número entero positivo b (la base) se eleva a la e-ésima potencia (el exponente), b^e, y es dividido por el entero positivo m, llamado módulo. En símbolos, esto es, dada la base b, el exponente e, y el módulo m, la exponenciación modular c es:

c \equiv b^e \pmod{m}

Por ejemplo, dado b = 5, e = 3, y m = 13, la solución, c = 8, es el resto de dividir

5^3

por 13.

Si b, e, y m no son negativos, y b < m, entonces una única solución c existe con la propiedad 0 ≤ c < m.

La exponenciación modular se puede realizar con exponente negativo e encontrando el inverso multiplicativo modular d de b modulo m usando el algoritmo extendido de Euclides. Esto es:

c \equiv b^{e} \equiv d^{\left|e\right|} \pmod{m}

donde e < 0 y

b \cdot d \equiv 1 \pmod{m}

Problemas de exponenciación modular similares al descrito arriba son considerados fáciles de resolver, incluso cuando los números que se manejan son enormes. Por otro lado, el cálculo del logaritmo discreto — es decir, la tarea de encontrar el exponente e si es dado un b, c, y m — se cree que es difícil. Este comportamiento de función unidireccionalhace a la exponenciación modular un candidato para su uso en algoritmos criptográficos.

En Teoría de números, la función de Carmichael de un entero positivo n, denotada λ(n), se define como el menor entero m tal que cumple:

a^m \equiv 1 \pmod{n}

para cada número entero a coprimo con n. En otras palabras, define el exponente del grupo multiplicativo de residuos módulo n (Z/nZ)^×.

Los primeros valores de λ(n) son 1, 1, 2, 2, 4, 2, 6, 2, 6, 4, 10, 2, 12, 6, 4, 4, 16, 6, 18, 4, 6, 10, 22, 2, 20, 12

La función puede definirse recursivamente, como sigue:

Para un primo p y un entero positivo k tal que p ≥ 3 o k ≤ 2:

\lambda(p^k) = p^{k-1}(p-1).\,

(De la misma manera que la función φ de Euler).

Para un entero k ≥ 3,

\lambda(2^k) = 2^{k-2}\,

Para distintos primos

p_1,p_2,\ldots,p_t

y enteros positivos

k_1,k_2,\ldots,k_t

\lambda(p_1^{k_1} p_2^{k_2} \cdots p_t^{k_t}) = \mathrm{mcm}( \lambda(p_1^{k_1}), \lambda(p_2^{k_2}), \cdots, \lambda(p_t^{k_t}) )

donde mcm denota el mínimo común múltiplo.

En forma compactada, la función queda como:

\lambda(n)= \begin{cases} p^{k-1}(p-1) & \mathrm{si} \ \ n=p^k, \; p \geq 3,\; k \leq 2\\ 2^{k-2} & \mathrm{si} \ \ n=2^k, \; k \geq 3\\ \mathrm{mcm}( \lambda(p_1^{k_1}), \lambda(p_2^{k_2}), \cdots, \lambda(p_t^{k_t}) ) & \mathrm{si} \ \ n=\prod_{i=1}^t p_i^{k_i} \end{cases}

Con la función de Carmichael, se puede elaborar un teorema, similar al teorema de Euler, éste dice:

Si a es un número coprimo con n, entonces a^λ(n) ≡ 1 (mod n)

donde

\lambda

es la función de Carmichael. Éste puede probarse considerando cualquier raíz primitiva módulo n y el teorema chino del resto.

Hay dos definiciones de la función de Carmichael. Una es la reducción de la función totient (también llamada la función exponente menos universal), definido como el número entero más pequeño

de tal manera que

para todos primos a . El orden multiplicativo de (mod ) es como máximo (Ribenboim 1989). Los primeros valores de esta función, implementado como CarmichaelLambda [ n ], son 1, 1, 2, 2, 4, 2, 6, 2, 6, 4, 10, ... (OEISA002322 ).

Se da por la fórmula

(1)

donde

son primarias .

Se puede definir de forma recursiva como

$lambda (n) = {phi (n) para n = p ^ alfa, con p = 2 y alfa <= 2, o p> = 3; 1 / 2phi (n) para n = 2 ^ alfa y alfa> = 3; LCM [lambda (p_i ^ (alpha_i))] _ i para n = producto_ (i) p_i ^ (alpha_i).$