Aritmética modular
En matemáticas , la aritmética modular es un sistema de aritmética para números enteros , donde los números "se envuelven" cuando alcanzan un cierto valor, llamado módulo . El enfoque moderno de la aritmética modular fue desarrollado por Carl Friedrich Gauss en su libro Disquisitiones Arithmeticae , publicado en 1801.
Un uso familiar de la aritmética modular es el reloj de 12 horas , en el que el día se divide en dos períodos de 12 horas. Si son las 7:00 ahora, 8 horas después serán las 3:00. La suma simple daría como resultado 7 + 8 = 15 , pero los relojes se "envuelven" cada 12 horas. Debido a que el número de la hora comienza de nuevo después de llegar a 12, este es el módulo aritmético 12. En términos de la definición siguiente, 15 es congruente con 3 módulo 12, por lo que se muestra " 15:00" en un reloj de 24 horas "3:00 "en un reloj de 12 horas.
Dado un número entero n > 1 , llamado módulo , dos enteros una y b se dice que son congruentes módulo n , si n es un divisor de su diferencia (es decir, si hay un número entero k tal que un - b = kN ).
El módulo de congruencia n es una relación de congruencia , lo que significa que es una relación de equivalencia que es compatible con las operaciones de suma , resta y multiplicación . El módulo de congruencia n se denota:
Los paréntesis significan que (mod n ) se aplica a toda la ecuación, no solo al lado derecho (aquí b ). Esta notación no debe confundirse con la notación b mod n (sin paréntesis), que se refiere a la operación módulo . De hecho, b mod n denota el único entero a tal que 0 ≤ a < n y (es decir, el resto de cuando se divide por ).
mostrando explícitamente su relación con la división euclidiana . Sin embargo, aquí no es necesario que b sea el resto de la división de a por n . En su lugar, lo que la declaración de un ≡ b (mod n ) afirma que es una y B tienen el mismo resto cuando se divide por n . Es decir,
