Aritmética modular

Imagem: The original uploader was Ivn at Spanish Wikipedia. · BY-SA · Openverse

Dado um inteiro n > 1 {\displaystyle n>1} , chamado módulo, dois inteiros são considerados congruentes (ou côngruos) módulo n {\displaystyle n} , se n {\displaystyle n} for um divisor de sua diferença (ou seja, se houver um inteiro k {\displaystyle k} tal que a − b = k n {\displaystyle a-b=kn} ). A congruência módulo n {\displaystyle n} é uma relação de congruência, o que significa que é uma relação de equivalência compatível com as operações de adição, subtração e multiplicação. A congruência módulo n {\displaystyle n} é denotada como: Os parênteses significam que ( mod n ) {\displaystyle ({\text{mod}}\ n)} se aplica a toda a equação, não apenas ao lado direito (aqui b {\displaystyle b} ). Esta notação não deve ser confundida com a notação b mod n {\displaystyle b{\bmod {n}}} (sem parênteses), que se refere à operação módulo. Na verdade, b mod n {\displaystyle b{\bmod {n}}} denota o número inteiro único a {\displaystyle a} tal que 0 ≤ a < n {\displaystyle 0\leq a<n} e a ≡ b ( mod n ) {\displaystyle a\equiv b\;({\text{mod}}\;n)} (ou seja, o restante de b {\displaystyle b} quando dividido por n {\displaystyle n} ).

A relação de congruência satisfaz todas as condições de uma relação de equivalência: Se a 1 ≡ b 1 ( mod n ) {\displaystyle a_{1}\equiv b_{1}{\pmod {n}}} e a 2 ≡ b 2 ( mod n ) {\displaystyle a_{2}\equiv b_{2}{\pmod {n}}} , ou se a ≡ b ( mod n ) {\displaystyle a\equiv b{\pmod {n}}} , então: Se a ≡ b ( mod n ) {\displaystyle a\equiv b{\pmod {n}}} , então geralmente é falso que k a ≡ k b ( mod n ) {\displaystyle k^{a}\equiv k^{b}{\pmod {n}}} . No entanto, o seguinte é verdadeiro: Para o cancelamento dos termos comuns, temos as seguintes regras: O inverso multiplicativo modular é definido pelas seguintes regras: O inverso multiplicativo x ≡ a − 1 ( mod n ) {\displaystyle x\equiv a^{-1}{\pmod {n}}} pode ser eficientemente calculado resolvendo a equação de Bézout a x + n y = 1 {\displaystyle ax+ny=1} para x , y {\displaystyle x,y} —usando o algoritmo Euclidiano estendido. Em particular, se p {\displaystyle p} é um número primo, então a {\displaystyle a} é coprimo com p {\displaystyle p} para todo a {\displaystyle a} tal que 0 < a < p {\displaystyle 0<a<p} ; assim, existe um inverso multiplicativo para todo a {\displaystyle a} que não é congruente a zero módulo p {\displaystyle p} .

Como qualquer relação de congruência, congruência módulo n é uma relação de equivalência, e as classes de equivalência do inteiro a, denotada por a ¯ n {\displaystyle {\overline {a}}_{n}} , é o conjunto { … , a − 2 n , a − n , a , a + n , a + 2 n , … } {\displaystyle \left\{\ldots ,a-2n,a-n,a,a+n,a+2n,\ldots \right\}} . Este conjunto, consistindo dos inteiros congruentes a a {\displaystyle a} modulo n {\displaystyle n} , é chamado a classe de congruência ou classe de resíduos ou simplesmente resíduo do inteiro a {\displaystyle a} modulo n {\displaystyle n} . Quando o módulo n {\displaystyle n} é conhecido pelo contexto, este resíduo também pode ser denotado por [ a ] {\displaystyle \displaystyle [a]} .

O conjunto de todas as classes de congruência módulo n é denotado Z / n Z {\displaystyle \mathbb {Z} /n\mathbb {Z} } ou Z / n {\displaystyle \mathbb {Z} /n} (a notação alternativa Z n {\displaystyle \mathbb {Z} _{n}} não é recomendada por causa da possível confusão com o conjunto dos inteiros p-ádicos). E é definida por: Z / n Z = { a ¯ n | a ∈ Z } . {\displaystyle \mathbb {Z} /n\mathbb {Z} =\left\{{\overline {a}}_{n}|a\in \mathbb {Z} \right\}.} Quando n ≠ 0 {\displaystyle n\neq 0} , Z / n Z {\displaystyle \mathbb {Z} /n\mathbb {Z} } tem n elementos, e pode ser escrita como: Quando n = 0, Z / n Z {\displaystyle \mathbb {Z} /n\mathbb {Z} } não tem elementos não nulos; daí é isomorfo a Z {\displaystyle \mathbb {Z} } , pois a ¯ 0 = { a } {\displaystyle {\overline {a}}_{0}=\left\{a\right\}} . Podemos definir adição, subtração e multiplicação em Z / n Z {\displaystyle \mathbb {Z} /n\mathbb {Z} } pelas seguintes regras:

A noção de aritmética modular está relacionada com a de resto da divisão. A operação de achar o resto é algumas vezes chamada de operação módulo, nesse contexto escrevemos, por exemplo, 2 = 14 (mod 12). A diferença está no uso da congruência, indicado por "≡", e da igualdade indicado por "=". Igualdade implica especificamente o "resíduo comum", o menor inteiro não negativo membro de uma classe de equivalência. Quando estamos trabalhando com aritmética modular, cada classe de equivalência é geralmente representada pelo seu resíduo comum, por exemplo 38 ≡ 2 (mod 12), que pode ser encontrado usando divisão longa. Segue disso que enquanto é correto dizer 38 ≡ 14 (mod 12) e 2 ≡ 14 (mod 12), é incorreto dizer 38 = 14 (mod 12) (com "=" no lugar de "≡"). A diferença é mais clara quando estamos dividindo um número negativo, porque neste caso os restos são negativos. Assim para expressar o resto devemos escrever −5 ≡ −17 (mod 12), em vez de 7 = −17 (mod 12), pois equivalência só pode ser considerada para resíduos com o mesmo sinal.

Cada classe de resíduo modulo n pode ser representada por um de seus membros, embora nós geralmente representemos cada classe residual pelo menor inteiro não negativo pertencente à classe (pois este é o próprio resto que resulta da divisão). Note que quaisquer dois membros de diferentes classes residuais módulo n são congruentes módulo n. Além disso cada inteiro pertence a uma e somente uma classe residual módulo n. O conjunto de inteiros {0, 1, 2, ..., n - 1} é chamado o menor sistema de resíduos módulo n. Qualquer outro conjunto de n inteiros, com nenhum par deles congruente módulo n é chamado um sistema completo de resíduos módulo n. É claro que o menor sistema de resíduos é uma sistema completo de resíduos e que um sistema completo de resíduos é simplesmente um conjunto contendo precisamente um representante de cada classe de resíduo módulo n. O menor sistema de resíduos módulo 4 é {0, 1, 2, 3}. Alguns outros sistemas de resíduos módulo 4 são:

Considere a equação a x 2 + b x + c ≡ 0 ( mod p ) {\displaystyle ax^{2}+bx+c\equiv 0{\pmod {p}}} , onde a , b , c ∈ Z {\displaystyle a,b,c\in \mathbb {Z} } , p {\displaystyle p} é um primo (ímpar) e a ≢ 0 ( mod p ) {\displaystyle a\not \equiv 0{\pmod {p}}} . Podemos observar que ( a , p ) = 1 {\displaystyle (a,p)=1} e como p {\displaystyle p} é ímpar temos ( 4 a , p ) = 1 {\displaystyle (4a,p)=1} . Assim, a equação acima é equivalente a 4 a ( a x 2 + b x + c ) ≡ 0 ( mod p ) {\displaystyle 4a(ax^{2}+bx+c)\equiv 0{\pmod {p}}} . Ao completarmos quadrados obtemos ( 2 a x + b ) 2 − ( b 2 − 4 a c ) ≡ 0 ( mod p ) {\displaystyle (2ax+b)^{2}-(b^{2}-4ac)\equiv 0{\pmod {p}}} . Ao fazermos y = 2 a x + b {\displaystyle y=2ax+b} e d = b 2 − 4 a c {\displaystyle d=b^{2}-4ac} , vem y 2 ≡ d ( mod p ) {\displaystyle y^{2}\equiv d{\pmod {p}}} . Para descobrir as soluções da equação quadrática, basta descobrir as soluções da equações da forma x 2 ≡ a ( mod p ) {\displaystyle x^{2}\equiv a{\pmod {p}}} . Pois se p ∣ a {\displaystyle p\mid a} (lê-se "p divide a") obtemos desinteressante a equação x 2 ≡ 0 ( mod p ) {\displaystyle x^{2}\equiv 0{\pmod {p}}} e, por essa razão x ≡ 0 ( mod p ) {\displaystyle x\equiv 0{\pmod {p}}} o que torna indispensável assumir que p ∤ a {\displaystyle p\nmid a} ("p não divide a") a fim de evitarmos soluções triviais.