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 ahora son las 7:00, 8 horas después serán las 3:00. La suma simple daría como resultado 7 + 8 = 15 , pero los relojes "recorren" 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 siguiente definición, 15 es congruente con 3 módulo 12, por lo que "15:00" en un reloj de 24 horas se muestra "3:00 " en un reloj de 12 horas.
Dado un entero n > 1 , llamado módulo , se dice que dos enteros a y b son congruentes módulo n , si n es un divisor de su diferencia (es decir, si hay un entero k tal que a − b = kn ).
La congruencia módulo n es una relación de congruencia , lo que significa que es una relación de equivalencia 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 de módulo . De hecho, b mod n denota el entero único a tal que 0 ≤ a < ny ( es decir, el resto de cuando se divide por ).
mostrando explícitamente su relación con la división euclidiana . Sin embargo, la b aquí no necesita ser el resto de la división de a por n . En cambio, lo que afirma la declaración a ≡ b (mod n ) es que a y b tienen el mismo resto cuando se dividen por n . Es decir,
