ARITIMETRICA 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 "voltam pra trás" quando atingem um certo valor, o módulo.

O matemático suiç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.^[1]

A aritmética modular foi desenvolvida posteriormente por Carl Friedrich Gauss em seu livro Disquisitiones Arithmeticae, publicado em 1801.

O 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 a hora é 7 horas agora, então daqui a 8 horas serão 3 horas. A adição usual sugere que o tempo futuro deveria ser 7 + 8 = 15, mas esta é a resposta errada por que o relógio "volta pra tràs" a cada 12 horas; não existe "15 horas" no relógio de ponteiro. 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. 12 é congruente não só a 12 mesmo, mas também a 0, assim a hora chamada "12:00" pode também ser chamada "0:00", pois 0 ≡ 12 mod 12.

Índice

  [esconder] 

• 1Relação de congruência
• 2Anel de classes de congruência
• 3Restos
  • 3.1Representação funcional da operação resto
• 4Sistema de resíduos
  • 4.1Sistemas reduzidos de resíduos
• 5Referências

Relação de congruência[editar | editar código-fonte]

Aritmética modular pode ser tratada matematicamente introduzindo uma relação de congruência no conjunto dos inteiros que é compatível com as operações do anel dos inteiros: adição, subtração e multiplicação. Para um inteiro positivo n, dois inteiros a e b são ditos congruêntes (ou côngruos) módulo n, e escrevemos

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

quando a diferença deles ${\displaystyle a-b}$. é um inteiro múltiplo de n. O número n é chamado o módulo da congruência.

Por exemplo,

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

pois 38 − 2 = 36, que é múltiplo de 12.

A mesma regra é vale para valores negativos:

${\displaystyle -8\equiv 7{\pmod {5}}.}$

${\displaystyle 2\equiv -3{\pmod {5}}.}$

${\displaystyle -3\equiv -8{\pmod {5}}.}$

Se ${\displaystyle a}$ e ${\displaystyle b}$ são ou os dois positivos ou os dois negativos, então ${\displaystyle a\equiv b{\pmod {n}}}$ pode ser visto como a afirmação de que ${\displaystyle a/n}$ e ${\displaystyle b/n}$ tem o mesmo resto. Por exemplo

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

porque ambos ${\displaystyle 38/12}$ e ${\displaystyle 14/12}$ tem o mesmo resto 2. Observe que também tem-se ${\displaystyle 38-14=24}$ um inteiro multiplo de 12, concordando com a definição inicial de relação de congruência.

Uma observação sobre a 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 ≡_n b for usada, em vez da notação tradicional.

As propriedades que fazem desta relação uma relação de congruência (com respeito à adição, subtração e multiplicação) são as seguintes.

Se

${\displaystyle a_{1}\equiv b_{1}{\pmod {n}}}$

e

${\displaystyle a_{2}\equiv b_{2}{\pmod {n}},}$

então:

• ${\displaystyle a_{1}+a_{2}\equiv b_{1}+b_{2}{\pmod {n}}}$
• ${\displaystyle a_{1}-a_{2}\equiv b_{1}-b_{2}{\pmod {n}}}$

Deve-se notar que as propriedades acima continuam válidas se expandirmos a teoria para incluir todos os números reais, mas a propriedade seguinte não vale necessariamente nesse contexto ampliado

• ${\displaystyle a_{1}a_{2}\equiv b_{1}b_{2}{\pmod {n}}.}$

Não se faz divisão em congruências, ao invés disso, faz-se uma multiplicação em ambos os membros por um número conveniente.

Pelo fato de todo número ter resto ${\displaystyle 0}$ na divisão por ${\displaystyle 1}$ não é interessante usarmos o módulo ${\displaystyle 1}$,pois para quaisquer ${\displaystyle a}$ e ${\displaystyle b}$ inteiros sempre teremos ${\displaystyle a\equiv b\equiv 0\mod {1}}$.

Anel de classes de congruência[editar | editar código-fonte]

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 ${\displaystyle {\overline {a}}_{n}}$, é o conjunto ${\displaystyle \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 \displaystyle [a]}$.

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

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

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

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

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

• ${\displaystyle {\overline {a}}_{n}+{\overline {b}}_{n}={\overline {(a+b)}}_{n}}$
• ${\displaystyle {\overline {a}}_{n}-{\overline {b}}_{n}={\overline {(a-b)}}_{n}}$
• ${\displaystyle {\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, ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ se torna um anel comutativo. Por exemplo, no anel ${\displaystyle \mathbb {Z} /24\mathbb {Z} }$, temos

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

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

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

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

O conjunto ${\displaystyle \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 ${\displaystyle \mathbb {Z} /0\mathbb {Z} }$ (que, como mencionado antes, é isomorfo ao anel ${\displaystyle \mathbb {Z} }$ dos inteiros), por exemplo quando discutindo característica de um anel.

Restos[editar | editar código-fonte]

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, por que 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 "%" (e.g. in C, Java, Javascript, Perl e Python) ou "mod" (e.g. in Pascal, BASIC, SQL, Haskell), com exceções(e.g. 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 (e.g. 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[editar | editar código-fonte]

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

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

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

${\displaystyle {\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

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

Sistema de resíduos[editar | editar código-fonte]

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.^[3]

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[editar | editar código-fonte]

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 .

Referências[editar | editar código-fonte]

1. Ir para cima↑ http://www.ams.org/samplings/feature-column/fcarc-eulers-formula
2. Ir para cima↑ Arnaldo Garcia e Yves Lequain. Elementos de Álgebra - Rio de Janeiro, IMPA, 2002. 326 páginas (Projeto Euclides), ISBN 978-85-244-0190-9
3. Ir para cima↑ José Plinio de Oliveira Santos - Introdução à Teoria dos Números - Rio de Janeiro, IMPA, 1998. 198 péginas (projeto Euclides), ISBN 978-85-244-0142-8

[Expandir] v • e Tópicos principais sobre teoria dos números

Categorias: 

• Aritmética modular
• Matemática
• Matemática discreta

Menu de navegação

• Não autenticado
• Discussão
• Contribuições
• Criar uma conta
• Entrar

• Artigo
• Discussão

• Ler
• Editar
• Editar código-fonte
• Ver histórico

Busca

• Página principal
• Conteúdo destacado
• Eventos atuais
• Esplanada
• Página aleatória
• Portais
• Informar um erro

Colaboração

• Boas-vindas
• Ajuda
• Página de testes
• Portal comunitário
• Mudanças recentes
• Manutenção
• Criar página
• Páginas novas
• Contato
• Donativos

Imprimir/exportar

• Criar um livro
• Descarregar como PDF
• Versão para impressão

Noutros projetos

• Wikimedia Commons

Ferramentas

• Páginas afluentes
• Alterações relacionadas
• Carregar ficheiro
• Páginas especiais
• Ligação permanente
• Informações da página
• Elemento Wikidata
• Citar esta página

Noutros idiomas

• Català
• English
• Español
• Français
• Italiano
• 日本語
• 한국어
• Русский
• 中文

Editar ligações

• Esta página foi editada pela última vez à(s) 16h02min de 23 de setembro de 2015.
• Este texto é disponibilizado nos termos da licença Creative Commons - Atribuição - Compartilha Igual 3.0 Não Adaptada (CC BY-SA 3.0); pode estar sujeito a condições adicionais. Para mais detalhes, consulte as condições de uso.