Aritmética modular

Em matemática, aritmética modular (chamada também de aritmética do relógio) é um sistema de aritmética para inteiros, onde os números "retrocedem" quando atingem um certo valor, o módulo. O matemático suíço Euler foi o pioneiro na abordagem de congruência por volta de 1750, quando ele explicitamente introduziu a ideia de congruência módulo um número natural N. A abordagem moderna da aritmética modular foi desenvolvida por Carl Friedrich Gauss em seu livro Disquisitiones Arithmeticae, publicado em 1801.

A cronometragem neste relógio usa aritmética módulo 12

Um uso familiar da aritmética modular é no relógio de ponteiro, no qual o dia é divido em dois períodos de 12 horas cada. Se são 7:00 agora, então 8 horas depois serão 3:00. A adição usual sugere que o tempo futuro deveria ser $7+8=15$, mas o relógio "retrocede" a cada 12 horas. Da mesma forma, se o relógio começa em 12:00(meio-dia) e 21 horas passam, então a hora será 9:00 do dia seguinte, em vez de 33:00. Como o número de horas começa de novo depois que atinge 12, esta aritmética é chamada aritmética módulo 12. Em termos da definição abaixo, $15$ é congruente com $3$ módulo $12$, então "15:00" em um relógio de 24 horas é exibido "3:00 "em um relógio de 12 horas.

Congruência

Dado um inteiro $n>1$, chamado módulo, dois inteiros são considerados congruentes (ou côngruos) módulo $n$, se $n$ for um divisor de sua diferença (ou seja, se houver um inteiro $k$ tal que $a-b=kn$).

A congruência módulo $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$ é denotada como:

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

Os parênteses significam que $({\text{mod}}\ n)$ se aplica a toda a equação, não apenas ao lado direito (aqui $b$). Esta notação não deve ser confundida com a notação $b{\bmod {n}}$ (sem parênteses), que se refere à operação módulo. Na verdade, $b{\bmod {n}}$ denota o número inteiro único $a$ tal que $0\leq a<n$ e $a\equiv b\;({\text{mod}}\;n)$ (ou seja, o restante de $b$ quando dividido por $n$).

A relação de congruência pode ser reescrita como

$a=kn+b,$

mostrando explicitamente sua relação com a divisão euclidiana. No entanto, o $b$ aqui não precisa ser o resto da divisão de $a$ por $n$. Em vez disso, o que a declaração $a\equiv b{\pmod {n}}$ afirma é que $a$ e $b$ têm o mesmo resto quando divididos por $n$. Isso é,

$a=pn+r,$

$b=qn+r,$

onde $0\leq r<n$ é o resto comum. Subtraindo essas duas expressões, recuperamos a relação anterior:

$a-b=kn,$

definindo $k=p-q$.

Exemplos

Exemplo 1

No módulo 12, pode-se afirmar que:

$38\equiv 14{\pmod {12}}$

porque $38-14=24$, que é um múltiplo de 12. Outra maneira de expressar isso é dizer que 38 e 14 têm o mesmo resto 2—quando dividido por 12.

A definição de congruência também se aplica a valores negativos. Por exemplo:

${\begin{aligned}-8&\equiv 7{\pmod {5}}\\2&\equiv -3{\pmod {5}}\\-3&\equiv -8{\pmod {5}}.\end{aligned}}$

Exemplo 2

$38\equiv 2{\pmod {12}}$

pois $38-2=36$, que é múltiplo de 12. Note que ${\frac {38}{12}}$ e ${\frac {2}{12}}$ tem o mesmo resto 2. Observe que também, utilizando o exemplo anterior, $14-2=12$ é inteiro múltiplo de 12, isto é $14\equiv 2{\pmod {12}}$, concordando com a definição inicial de relação de congruência.

Notação

Como é comum considerar várias relações de congruência com diferentes módulos ao mesmo tempo, o módulo é incorporado na notação. Mesmo a notação sendo ternária, a relação de congruência para um módulo fixado é uma relação binária. Isto deve estar claro se a notação $a\equiv _{n}b$ for usada, em vez da notação tradicional.

Propriedades

A relação de congruência satisfaz todas as condições de uma relação de equivalência:

• Reflexividade: $a\equiv a{\pmod {n}}$
• Simetria: $a\equiv b{\pmod {n}}$ se $b\equiv a{\pmod {n}}$ para todo $a$, $b$ e $n$.
• Transitividade: Se $a\equiv b{\pmod {n}}$ e $b\equiv c{\pmod {n}}$, então $a\equiv c{\pmod {n}}$

Se $a_{1}\equiv b_{1}{\pmod {n}}$ e $a_{2}\equiv b_{2}{\pmod {n}}$, ou se $a\equiv b{\pmod {n}}$, então:

• $a+k\equiv b+k{\pmod {n}}$ para qualquer inteiro $k$ (compatibilidade com translação)
• $ka\equiv kb{\pmod {n}}$ para qualquer inteiro $k$ (compatibilidade com escala)
• $a_{1}+a_{2}\equiv b_{1}+b_{2}{\pmod {n}}$ (compatibilidade com adição)
• $a_{1}-a_{2}\equiv b_{1}-b_{2}{\pmod {n}}$ (compatibilidade com subtração)
• $a_{1}a_{2}\equiv b_{1}b_{2}{\pmod {n}}$ (compatibilidade com multiplicação)
• $a^{k}\equiv b^{k}{\pmod {n}}$ para qualquer inteiro não negativo $k$ (compatibilidade com exponenciação)
• $p(a)\equiv p(b){\pmod {n}}$, para qualquer polinômio $p(x)$ com coeficientes inteiros (compatibilidade com avaliação polinomial)

Se $a\equiv b{\pmod {n}}$, então geralmente é falso que $k^{a}\equiv k^{b}{\pmod {n}}$. No entanto, o seguinte é verdadeiro:

• Se $c\equiv d{\pmod {\varphi (n)}}$, onde $\varphi$ é a função totiente de Euler, então $a^{c}\equiv a^{d}{\pmod {n}}$—desde que $a$ seja coprimo com $n$.

Para o cancelamento dos termos comuns, temos as seguintes regras:

• Se $a+k\equiv b+k{\pmod {n}}$ para qualquer inteiro $k$, então $a\equiv b{\pmod {n}}$
• Se $ka\equiv kb{\pmod {n}}$ e $k$ é coprimo com $n$, então $a\equiv b{\pmod {n}}$

O inverso multiplicativo modular é definido pelas seguintes regras:

• Existência: existe um inteiro denotado $a^{-1}$ tal que $aa^{-1}\equiv 1{\pmod {n}}$ se e somente se $a$ é coprimo com $n$. Este inteiro $a^{-1}$ é chamado de inverso multiplicativo modular de $a$ módulo $n$.
• Se $a\equiv b{\pmod {n}}$ e $a^{-1}$ existem, então $a^{-1}\equiv b^{-1}{\pmod {n}}$ (compatibilidade com o inverso multiplicativo e, se $a=b$, unicidade módulo $n$)
• Se $ax\equiv b{\pmod {n}}$ e $a$ é coprimo com $n$, então a solução para esta congruência linear é dada por $x\equiv a^{-1}b{\pmod {n}}$

O inverso multiplicativo $x\equiv a^{-1}{\pmod {n}}$ pode ser eficientemente calculado resolvendo a equação de Bézout $ax+ny=1$ para $x,y$—usando o algoritmo Euclidiano estendido.

Em particular, se $p$ é um número primo, então $a$ é coprimo com $p$ para todo $a$ tal que $0<a<p$; assim, existe um inverso multiplicativo para todo $a$ que não é congruente a zero módulo $p$.

Algumas das propriedades mais avançadas das relações de congruência são as seguintes:

• Pequeno teorema de Fermat: Se $p$ é primo e não divide $a$, então $a^{p-1}\equiv 1{\pmod {p}}$.
• Teorema de Euler: Se $a$ e $n$ são coprimos, então a $a^{\varphi (n)}\equiv 1{\pmod {n}}$, onde $\varphi$ é a função totiente de Euler
• Uma consequência simples do pequeno teorema de Fermat é que se $p$ é primo, então $a^{-1}\equiv a^{p-2}{\pmod {p}}$ é o inverso multiplicativo de $0<a<p$. De maneira mais geral, a partir do teorema de Euler, se $a$ e $n$ são coprimos, então $a^{-1}\equiv a^{\varphi (n)-1}{\pmod {n}}$.
• Outra consequência simples é que se $a\equiv b{\pmod {\varphi (n)}}$, onde $\varphi$ é a função totiente de Euler, então $k^{a}\equiv k^{b}{\pmod {n}}$ desde que $k$ seja coprimo com $n$.
• Teorema de Wilson: $p$ é primo se e somente se $(p-1)!\equiv -1{\pmod {p}}$.
• Teorema do resto chinês: Para qualquer $a$, $b$ e coprimo $m$, $n$, existe um único $x{\pmod {mn}}$ tal que $x\equiv a{\pmod {m}}$ e $x\equiv b{\pmod {n}}$. De fato, $x\equiv b{m_{n}}^{-1}m+a{n_{m}}^{-1}n{\pmod {mn}}$ onde ${m_{n}}^{-1}$ é o inverso de $m$ módulo $n$ e ${n_{m}}^{-1}$ é o inverso de $n$ módulo $m$.
• Teorema de Lagrange: A congruência $f(x)\equiv 0{\pmod {p}}$, onde $p$ é primo, e $f(x)=a_{0}x^{n}+...+a_{n}$ é um polinômio com coeficientes inteiros tais que $a_{0}\neq 0{\pmod {p}}$ , tem no máximo $n$ raízes.
• Raiz primitiva módulo n: Um número $g$ é uma raiz primitiva módulo $n$ se, para cada inteiro um coprimo com $n$, existe um inteiro $k$ tal que $g^{k}\equiv a{\pmod {n}}$. Uma raiz primitiva módulo $n$ existe se e somente se $n$ for igual a $2$, $4$, $p^{k}$ ou $2p^{k}$, onde $p$ é um número primo ímpar e $k$ é um inteiro positivo. Se existe uma raiz primitiva módulo $n$, então existem exatamente $\varphi (\varphi (n))$ tais raízes primitivas, onde $\varphi$ é a função totiente de Euler.
• Resíduo quadrático: Um inteiro $a$ é um resíduo quadrático módulo $n$, se existir um inteiro $x$ tal que $x^{2}\equiv a{\pmod {n}}$. O critério de Euler afirma que, se $p$ é um primo ímpar, e $a$ não é um múltiplo de $p$, então $a$ é um resíduo quadrático módulo $p$ se e somente se

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

Classes de congruência

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 ${\overline {a}}_{n}$, é o conjunto $\left\{\ldots ,a-2n,a-n,a,a+n,a+2n,\ldots \right\}$. Este conjunto, consistindo dos inteiros congruentes a $a$ modulo $n$, é chamado a classe de congruência ou classe de resíduos ou simplesmente resíduo do inteiro $a$ modulo $n$. Quando o módulo $n$ é conhecido pelo contexto, este resíduo também pode ser denotado por $\displaystyle [a]$.

Anel de classes de congruência

O conjunto de todas as classes de congruência módulo n é denotado $\mathbb {Z} /n\mathbb {Z}$ ou $\mathbb {Z} /n$ (a notação alternativa $\mathbb {Z} _{n}$ não é recomendada por causa da possível confusão com o conjunto dos inteiros p-ádicos). E é definida por: $\mathbb {Z} /n\mathbb {Z} =\left\{{\overline {a}}_{n}|a\in \mathbb {Z} \right\}.$

Quando $n\neq 0$, $\mathbb {Z} /n\mathbb {Z}$ tem n elementos, e pode ser escrita como:

$\mathbb {Z} /n\mathbb {Z} =\left\{{\overline {0}}_{n},{\overline {1}}_{n},{\overline {2}}_{n},\ldots ,{\overline {n-1}}_{n}\right\}.$

Quando n = 0, $\mathbb {Z} /n\mathbb {Z}$ não tem elementos não nulos; daí é isomorfo a $\mathbb {Z}$, pois ${\overline {a}}_{0}=\left\{a\right\}$.

Podemos definir adição, subtração e multiplicação em $\mathbb {Z} /n\mathbb {Z}$ pelas seguintes regras:

• ${\overline {a}}_{n}+{\overline {b}}_{n}={\overline {(a+b)}}_{n}$
• ${\overline {a}}_{n}-{\overline {b}}_{n}={\overline {(a-b)}}_{n}$
• ${\overline {a}}_{n}{\overline {b}}_{n}={\overline {(ab)}}_{n}.$

A verificação que esta é uma definição adequada usa as propriedades mencionadas antes.

Desta forma, $\mathbb {Z} /n\mathbb {Z}$ se torna um anel comutativo. Por exemplo, no anel $\mathbb {Z} /24\mathbb {Z}$, temos

${\overline {12}}_{24}+{\overline {21}}_{24}={\overline {9}}_{24}$

como na aritmética do relógio de ponteiro.

A notação $\mathbb {Z} /n\mathbb {Z}$ é usada, por que ele é anel quociente de $\mathbb {Z}$ pelo ideal $n\mathbb {Z}$ consistindo de todos os inteiros divisíveis por n, onde $0\mathbb {Z}$ é o conjunto unitário $\left\{0\right\}$. Assim $\mathbb {Z} /n\mathbb {Z}$ é um corpo quando $n\mathbb {Z}$ é um ideal máximal, ou seja, quando $n$ é primo.

Em termos de grupos, a classe de resíduos ${\overline {a}}_{n}$ é a classe lateral de a no grupo quociente $\mathbb {Z} /n\mathbb {Z}$, um grupo cíclico.

O conjunto $\mathbb {Z} /n\mathbb {Z}$ tem várias propriedades matemáticas importantes que são o fundamento de vários ramos da matemática.

Em vez de excluir o caso n=0, é mais útil incluir $\mathbb {Z} /0\mathbb {Z}$ (que, como mencionado antes, é isomorfo ao anel $\mathbb {Z}$ dos inteiros), por exemplo quando discutindo característica de um anel.

Restos

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.

Em ciência da computação, o operador resto é normalmente indicado por "%" (p.ex. em C, Java, Javascript, Perl e Python) ou "mod" (p.ex. in Pascal, BASIC, SQL, Haskell), com exceções (p.ex. em Excel). Estes operadores são normalmente pronunciados como "mod", mas o que é efetivamente computado é um resto (pois em C++ são retornados números negativos se o primeiro argumento é negativo e em Python um número negativo é retornado se o segundo argumento é negativo). A função modulo em vez de mod, como em 38 ≡ 14 (modulo 12), é algumas vezes usada para indicar um resíduo comum em vez do resto (p.ex. em Ruby).

Os parenteses às vezes não são escritos na expressão, por exemplo 38 ≡ 14 mod 12 ou 2 = 14 mod 12, ou são colocados em volta do divisor, por exemplo 38 ≡ 14 mod (12). Notações como 38 (mod 12) também existem, mas são ambíguas sem um contexto.

Representação funcional da operação resto

A operação resto pode ser representada usando a função piso. Se b = a (mod n), onde n > 0, então se o resto é b ele é dado por

$b=a-\left\lfloor {\frac {a}{n}}\right\rfloor \times n,$

onde $\left\lfloor {\frac {a}{n}}\right\rfloor$ é o maior inteiro menor ou igual a ${\frac {a}{n}}$, então

${\begin{array}{lcl}a\equiv b{\pmod {n}}{\text{ e,}}\\0\leq b<n.\end{array}}$

Se em vez do resto b o intervalo −n ≤ b < 0 é requirido, então

$b=a-\left\lfloor {\frac {a}{n}}\right\rfloor \times n-n.$

Sistema de resíduos

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:

• {1,2,3,4}
• {13,14,15,16}
• {-2,-1,0,1}
• {-13,4,17,18}
• {-5,0,6,21}
• {27,32,37,42}

Alguns conjuntos que não são um sistema completo de resíduos módulo 4 são:

• {-5,0,6,22} pois 6 é congruente a 22 módulo 4.
• {5,15} pois um sistema completo de resíduos deve ter exatamente 4 elementos.

Sistemas reduzidos de resíduos

Qualquer conjunto com φ(n) inteiros que são primos com n e que são incongruentes entre si módulo n, onde φ(n) denota a Função totiente de Euler, é chamado um sistema reduzido de resíduos módulo n.

Congruências quadráticas (ou do segundo grau)

Considere a equação $ax^{2}+bx+c\equiv 0{\pmod {p}}$, onde $a,b,c\in \mathbb {Z}$, $p$ é um primo (ímpar) e $a\not \equiv 0{\pmod {p}}$. Podemos observar que $(a,p)=1$ e como $p$ é ímpar temos $(4a,p)=1$. Assim, a equação acima é equivalente a $4a(ax^{2}+bx+c)\equiv 0{\pmod {p}}$. Ao completarmos quadrados obtemos $(2ax+b)^{2}-(b^{2}-4ac)\equiv 0{\pmod {p}}$. Ao fazermos $y=2ax+b$ e $d=b^{2}-4ac$, vem $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}\equiv a{\pmod {p}}$. Pois se $p\mid a$ (lê-se "p divide a") obtemos desinteressante a equação $x^{2}\equiv 0{\pmod {p}}$ e, por essa razão $x\equiv 0{\pmod {p}}$ o que torna indispensável assumir que $p\nmid a$ ("p não divide a") a fim de evitarmos soluções triviais.

Exemplo

Resolva a congruência $8x^{2}+5x+1\equiv 0{\pmod {23}}$.

Como $(8,23)=1$ e $p=23$ é primo ímpar temos que $(4\cdot 8,23)=(32,23)=1$, no qual ao multiplicarmos a congruência em questão e completar quadrados obtemos $(16x+5)^{2}+32-25\equiv 0{\pmod {23}}\Rightarrow (16x+5)^{2}\equiv 16{\pmod {23}}$. Com isso encontramos $16x+5\equiv \pm 4{\pmod {23}}$, onde ao resolvermos a congruência linear $16x\equiv -1{\pmod {23}}$ temos $x\equiv 10{\pmod {23}}$, enquanto a partir da congruência linear $x\equiv -9{\pmod {23}}$, obtemos $x\equiv 21{\pmod {23}}$. Dessa maneira, $10$ e $21$ são as únicas soluções incongruentes. De fato, se $x=10\Rightarrow 8x^{2}+5x+1=851$ e $851\equiv 0{\pmod {23}}$. Se $x=21\Rightarrow 8x^{2}+5x+1=3634$ e $3634\equiv 0{\pmod {23}}$.