Aritmética modular

Cubierta de la edición orixinal de Disquisitiones arithmeticae de Gauss, llibru fundamental de l'aritmética modular.

En matemática, la aritmética modular ye un sistema aritméticu pa clases d'equivalencia de númberos enteros llamaes clases de congruencia. L'aritmética modular foi introducida en 1801 por Carl Friedrich Gauß nel so llibru Disquisitiones Arithmeticae.

Delles vegaes llámase-y, sugerentemente, aritmética del reló, una y bones los númberos «dan la vuelta» n'algamando ciertu valor llamáu módulu.

Rellación de congruencia

El tiempu lleváu por esti reló usa aritmética en módulu 12.

L'aritmética modular pue ser construyida matemáticamente por aciu la rellación de congruencia ente enteros, que ye compatible coles operaciones nel aniellu d'enteros: suma y multiplicación. Pa un determináu módulu n, ésta defínese de la siguiente manera:

a y b atopar na mesma "clase de congruencia" módulu n, si dambos dexen el mesmu resto si estremar ente n, o, equivalentemente, si a − b ye un múltiplu de n.

Esta rellación puede espresase cómodamente utilizando la notación de Gauss:

$a\equiv b\ {\pmod {n}}$

Asina se tien por casu

$63\equiv 83\ {\pmod {10}}$

yá que dambos, 63 y 83 dexen el mesmu restu (3) al estremar ente 10, o, equivalentemente, 63 − 83 ye un múltiplu de 10. Lléese:

«63 ye congruente con 83, módulu 10», «en módulu 10, 63 y 83 son congruentes», o «63 y 83 son congruentes unu con otru, módulu 10».

«Módulu» dacuando embrívese cola pallabra «mod» al falar, de la mesma manera que como ta escritu y provién de la pallabra modulus del llatín, la llingua de los escritos orixinales de Gauss. Asina, el númberu n, que nesti exemplu ye 10, sería'l modulus.

Otru exemplu; cuando'l módulu ye 12, entós cualesquier dos númberos qu'estremaos ente dolce dean el mesmu restu son equivalentes (o "congruentes") unu con otru. Los númberos

..., −34, −22, −10, 14, 26,...

son toos "congruentes módulu 12" unos con otros, yá que cada unu dexa'l mesmu restu (2) cuando los estremamos ente 12. La coleición de toos esos númberos ye una clase de congruencia.

Propiedaes principales

Clases d'equivalencia módulo n

L'aritmética modular basar nuna rellación d'equivalencia, y les clases d'equivalencia d'un enteru a se denota con [a]_n (o a cencielles [a] si sobrentendemos el módulu.) Otres notaciones son por casu a + nZ o a mod n. El conxuntu de toles clases d'equivalencia se denota con Z/nZ = { [0]_n, [1]_n, [2]_n,..., [n-1]_n }.

Esta rellación d'equivalencia tien importantes propiedaes que se siguen darréu de la definición:

Si : $a_{1}\equiv b_{1}{\pmod {n}}$ y : $a_{2}\equiv b_{2}{\pmod {n}}$ entós : $a_{1}+a_{2}\equiv b_{1}+b_{2}{\pmod {n}}$ y : $a_{1}a_{2}\equiv b_{1}b_{2}{\pmod {n}}$

Lo qu'amuesa que la suma y la multiplicación son operaciones bien definíes sobre'l conxuntu de les clases d'equivalencia. N'otres pallabres, la suma y la multiplicación tán definíes sobre Z/nZ por aciu les fórmules siguientes:

$[a]_{n}+[b]_{n}=[a+b]_{n}\,\!$

$[a]_{n}\cdot [b]_{n}=[a\cdot b]_{n}$

D'esta miente, Z/nZ convertir nun aniellu con n elementos. Por casu, nel aniellu Z/12Z, tiense :[8]₁₂[3]₁₂ + [6]₁₂ = [30]₁₂ = [6]₁₂.

El conxuntu d'enteros en Z/pZ forma un cuerpu finito si y namái si p ye primu.

Resolución de congruencies

Si a y b son enteros, la congruencia: ax ≡ b (mod n) tien solución x si y namái si'l máximu común divisor (a, n) estrema a b. Los detalles tán recoyíos nel teorema de congruencia llinial. Sistemes de congruencies más complicaos con módulos distintos pueden resolvese usando'l teorema chinu del restu o'l métodu de sustitución socesiva.

Nel aniellu d'enteros, si consideramos la ecuación ax ≡ 1 (mod n), vemos que a tien un inversu multiplicativu si y namái si a y n son coprimos. Por tanto, Z/nZ ye un cuerpu si y namái si n ye un primu. Puede probase que cada cuerpu finito ye una estensión de Z/pZ pa dalgún primu p.

Pequeñu teorema de Fermat y teorema de Euler

Artículos principales: Pequeñu teorema de Fermat y Teorema de Euler

Un fechu importante sobre aritmética modular, cuando los módulos son númberos primos ye'l pequeñu teorema de Fermat: si p ye un númberu primu, entós:

Si a ye cualesquier enteru:

$a^{p}\equiv a{\pmod {p}}$

Si a ye un enteru non divisible ente p:

$a^{p-1}\equiv 1{\pmod {p}}$

Esto foi xeneralizáu por Euler: pa tou enteru positivu n y tou enteru a relativamente primu a n, :a^φ(n) ≡ 1 (mod n), onde φ(n) denota función phi de Euler que cunta'l númberu d'enteros ente 1 y n que sían coprimos con al respective de n. El teorema de Euler ye una consecuencia del teorema de Lagrange, aplicáu al casu del grupu de les unidaes del aniellu Z/nZ.

Xeneralizaciones

Dos enteros a, b son congruentes módulu n, escritu como:a ≡ b (mod n) si la so diferencia a − b ye divisible ente n, esto ye, si a − b = kn pa dalgún enteru k.

Usando esta definición, podemos xeneralizar a módulos non enteros. Por casu, podemos definir a ≡ b (mod 2π) si a − b = k2π pa dalgún enteru k. Esta idea desenvuélvese dafechu nel contestu de la teoría de los aniellos y funciones trigonométriques.

En Álxebra astracta vese que l'aritmética modular ye un casu especial del procesu de crear un aniellu factorial d'un aniellu módulu un ideal. Si R ye un aniellu conmutativu, y I ye un ideal de R, entós dos elementos a y b de R dícense congruentes módulu I si a − b ye un elementu de I. Como pasaba col aniellu d'enteros, esto conviértese nuna rellación d'equivalencia, y la suma y la multiplicación convertir n'operaciones bien definíes sobre l'aniellu factorial R/I.

Aplicaciones de l'aritmética modular

L'aritmética modular, estudiada sistemáticamente en primer llugar por Carl Friedrich Gauss a la fin del Sieglu XVIII, aplicar en teoría de númberos, álxebra astracta, criptografía, y n'artes visuales y musicales.

Les operaciones aritmétiques qu'anguaño faen la mayoría de los ordenadores son aritméticu modulares, onde'l módulu ye 2^b (b ye'l númberu de bits de los valores sobre los qu'operamos). Esto vese claro na compilación de llinguaxes de programación como'l C; onde por casu toles operaciones aritmétiques sobre "int", enteros, tómense módulu 2³² na mayoría de los ordenadores.

Nel arte

En música, por cuenta de la equivalencia d'octaves y equivalencia enarmónica (esto ye, los pasos en razones de 1/2 o 2/1 son equivalentes, y Do# ye lo mesmo que Reb), l'aritmética modular úsase cuando consideramos la escala de doce tono igualmente temperada, especialmente nel dodecafonismu. N'artes visuales esta aritmética puede usase pa crear patrones artísticos basaos nes tables de multiplicación módulo n (ver enllaz embaxo).

Ver tamién

• Residuu cuadrático
• Teorema chinu del restu
• Pequeñu teorema de Fermat
• Teorema de Euler
• Criteriu de Euler
• Teorema de Lagrange (teoría de grupos)
• Aritmética de saturación

Enllaces esternos

• Weisstein, Eric W. «Modular arithmetic» (inglés). MathWorld. Wolfram Research.
• Perl arithmetic enhancements - esplica les razones que s'atopen tres l'operador de Perl %

• Datos: Q319400
• Multimedia: Modular arithmetic