Aritmética modular: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m Removing Link FA template (handled by wikidata) |
→Relação de congruência: Correção de espaços, pontuação e gralhas. |
||
Linha 2:
Em [[matemática]], '''aritmética modular''' (chamada também de '''aritmética do relógio''') é um sistema de aritmética para [[inteiro]]s, onde os números "voltam pra trás" quando atingem um certo valor, o '''módulo'''.
O matemático
A aritmética modular foi desenvolvida posteriormente por [[Carl Friedrich Gauss]] em seu livro ''[[Disquisitiones Arithmeticae]]'', publicado em 1801.
[[Imagem:Clock group.svg|thumb|right|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
==Relação de congruência==
Aritmética modular pode ser tratada matematicamente introduzindo uma [[Congruência (álgebra)|relação de congruência]] no conjunto dos [[inteiro]]s que é compatível com as operações do [[Anel (álgebra)|anel]] dos inteiros: [[adição]], [[subtração]] e [[multiplicação]]. Para um inteiro positivo ''n'', dois inteiros ''a'' e ''b'' são ditos '''
:<math>a \equiv b \pmod n,</math>
quando a diferença deles <math>a-b</math>. é um inteiro [[múltiplo]] de ''n''. O número ''n'' é chamado o '''módulo''' da congruência.
Linha 18:
pois 38 − 2 = 36, que é múltiplo de 12.
A mesma regra
:<math> -8 \equiv 7 \pmod 5.</math>
:<math> 2 \equiv -3 \pmod 5.</math>
Linha 25:
Se <math>a</math> e <math>b</math> são ou os dois positivos ou os dois negativos, então <math>a \equiv b \pmod n</math> pode ser visto como a afirmação de que <math>a/n</math> e <math>b/n</math> tem o mesmo [[Resto da divisão inteira|resto]]. Por exemplo
:<math>38 \equiv 14 \pmod {12}</math>
porque ambos <math>38/12</math> e <math>14/12</math> tem o mesmo resto 2. Observe que também
Uma observação sobre a notação:
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.
Linha 39:
*<math>a_1 - a_2 \equiv b_1 - b_2 \pmod n</math>
Deve
*<math> a_1 a_2 \equiv b_1 b_2 \pmod n.</math>
Não se faz divisão em congruências
Pelo fato de todo número ter resto <math>0</math> na divisão por <math>1</math> não é interessante usarmos o módulo <math>1</math>, pois para quaisquer <math>a</math> e <math>b</math> inteiros sempre teremos <math>a\equiv b\equiv0\mod{1}</math>.
==Anel de classes de congruência==
Como qualquer relação de congruência, congruência módulo ''n'' é uma [[relação de equivalência]], e as [[classe de equivalência|classes de equivalência]] do inteiro ''a'', denotada por <math>\overline{a}_n</math>, é o conjunto <math>\left\{\ldots, a - 2n, a - n, a, a + n, a + 2n, \ldots \right\}</math>. 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 <math>\displaystyle [a]</math>.
O conjunto de todas as classes de congruência módulo ''n'' é denotado <math>\mathbb{Z}/n\mathbb{Z}</math> ou <math>\mathbb{Z}/n</math> (a notação alternativa <math>\mathbb{Z}_n</math> não é recomendada por causa da possível confusão com o conjunto dos [[Número p-ádico|inteiros p-ádicos]]). E é definida por
Quando <math>n\neq 0</math>, <math>\mathbb{Z}/n\mathbb{Z}</math> tem ''n'' elementos, e pode ser escrita como:
Linha 68:
como na aritmética do relógio de ponteiro.
A notação <math>\mathbb{Z}/n\mathbb{Z}</math> é usada, por que ele é [[anel quociente]] de <math>\mathbb{Z}</math> pelo [[Ideal (teoria dos anéis)|ideal]] <math>n\mathbb{Z}</math> consistindo de todos os inteiros divisíveis por ''n'', onde <math>0\mathbb{Z}</math> é o [[conjunto unitário]] <math>\left\{0\right\}</math>. Assim <math>\mathbb{Z}/n\mathbb{Z}</math> é um [[corpo (matemática)|corpo]] quando <math>n\mathbb{Z}</math> é um [[ideal máximal]], ou seja, quando <math>n</math> é primo.
Em termos de grupos, a classe de resíduos <math>\overline{a}_n</math> é a [[classe lateral]] de ''a'' no [[grupo quociente]] <math>\mathbb{Z}/n\mathbb{Z}</math>, um [[grupo cíclico]].<ref name="Arnaldo" />
O conjunto <math>\mathbb{Z}/n\mathbb{Z}</math>
Em vez de excluir o caso ''n''=0, é mais útil incluir <math>\mathbb{Z}/0\mathbb{Z}</math> (que, como mencionado antes, é isomorfo ao anel <math>\mathbb{Z}</math> dos inteiros), por exemplo quando discutindo característica de um [[Anel (álgebra)|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, {{nowrap|1=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 {{nowrap|38 ≡ 2 (mod 12)}}, que pode ser encontrado usando [[divisão longa]]. Segue disso que enquanto é correto dizer {{nowrap|38 ≡ 14 (mod 12)}} e {{nowrap|2 ≡ 14 (mod 12)}}, é incorreto dizer {{nowrap|1=38 = 14 (mod 12)}} (com "=" no lugar de "≡").
A diferença é mais clara quando estamos dividindo um número negativo,
Em [[ciência da computação]], o operador resto é normalmente indicado por "%" (
▲(e.g. in [[C (linguagem de programação)|C]], [[Java (linguagem de programação)|Java]], [[Javascript]], [[Perl]] e [[Python (linguagem de programação)|Python]]) ou "mod" (e.g. in [[Pascal (linguagem de programação)|Pascal]], [[BASIC]], [[SQL]], [[Haskell (linguagem de programação)|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 (linguagem de programação)|Ruby]]).
Os parenteses às vezes não são escritos na expressão, por exemplo
===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
:<math>b = a - \left\lfloor \frac{a}{n} \right\rfloor \times n,</math>
onde <math>\left\lfloor \frac{a}{n} \right\rfloor</math>
::<math>\begin{array}{lcl}
a \equiv b \pmod n \text{ e,}\\
Linha 102 ⟶ 99:
== Sistema de resíduos ==
Cada classe de resíduo
O conjunto de inteiros {0, 1, 2, ..., ''n'' - 1} é chamado o '''menor sistema 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:
Linha 117 ⟶ 114:
Alguns conjuntos que não são um sistema completo de resíduos módulo 4 são:
*{-5,0,6,22}
*{5,15}
=== 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''
==Referências==
Linha 127 ⟶ 124:
<ref name="enciclopédia britânica">http://www.ams.org/samplings/feature-column/fcarc-eulers-formula</ref>
<ref name="Arnaldo">Arnaldo Garcia e Yves Lequain. Elementos de Álgebra - Rio de Janeiro, IMPA, 2002. 326 páginas (Projeto Euclides), ISBN 978-85-244-0190-9</ref>
<ref name="Plinio">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</ref>
</references>
| |||