Aritmética modular: diferenças entre revisões
m Removing Link FA template (handled by wikidata) |
→Relação de congruência: Correção de espaços, pontuação e gralhas. |
||
Linha 2: | 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'''. |
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 |
O matemático suíço [[Leonhard Euler|Euler]] foi o pioneiro na abordagem de [[Congruência (álgebra)|congruência]] por volta de 1750, quando ele explicitamente introduziu a ideia de congruência [[módulo]] um número natural ''N''.<ref name="enciclopédia britânica" /> |
||
A aritmética modular foi desenvolvida posteriormente por [[Carl Friedrich Gauss]] em seu livro ''[[Disquisitiones Arithmeticae]]'', publicado em 1801. |
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.]] |
[[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 |
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 para 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. |
||
==Relação de congruência== |
==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 ''' |
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 '''congruentes''' (ou '''côngruos''') '''módulo''' ''n'', e escrevemos |
||
:<math>a \equiv b \pmod n,</math> |
:<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. |
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: | Linha 18: | ||
pois 38 − 2 = 36, que é múltiplo de 12. |
pois 38 − 2 = 36, que é múltiplo de 12. |
||
A mesma regra |
A mesma regra vale para valores negativos: |
||
:<math> -8 \equiv 7 \pmod 5.</math> |
:<math> -8 \equiv 7 \pmod 5.</math> |
||
:<math> 2 \equiv -3 \pmod 5.</math> |
:<math> 2 \equiv -3 \pmod 5.</math> |
||
Linha 25: | 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 |
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> |
:<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 |
porque ambos <math>38/12</math> e <math>14/12</math> tem o mesmo resto 2. Observe que também se tem <math>38 - 14 = 24</math> um inteiro múltiplo de 12, concordando com a definição inicial de relação de congruência. |
||
Uma observação sobre a notação: |
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'' {{unicode|≡}}<sub>''n''</sub> ''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. |
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: | Linha 39: | ||
*<math>a_1 - a_2 \equiv b_1 - b_2 \pmod n</math> |
*<math>a_1 - a_2 \equiv b_1 - b_2 \pmod n</math> |
||
Deve |
Deve notar-se que as propriedades acima continuam válidas se expandirmos a teoria para incluir todos os [[Número real|números reais]], mas a propriedade seguinte não vale necessariamente nesse contexto ampliado |
||
*<math> a_1 a_2 \equiv b_1 b_2 \pmod n.</math> |
*<math> a_1 a_2 \equiv b_1 b_2 \pmod n.</math> |
||
Não se faz divisão em congruências |
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 <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>. |
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== |
==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>. |
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 |
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: <math>\mathbb{Z}/n\mathbb{Z} = \left\{ \overline{a}_n | a \in \mathbb{Z}\right\}. </math> |
||
Quando <math>n\neq 0</math>, <math>\mathbb{Z}/n\mathbb{Z}</math> tem ''n'' elementos, e pode ser escrita como: |
Quando <math>n\neq 0</math>, <math>\mathbb{Z}/n\mathbb{Z}</math> tem ''n'' elementos, e pode ser escrita como: |
||
Linha 68: | Linha 68: | ||
como na aritmética do relógio de ponteiro. |
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]] |
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. |
||
<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" /> |
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> |
O conjunto <math>\mathbb{Z}/n\mathbb{Z}</math> 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 <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]]. |
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== |
==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 |
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 "≡"). |
||
é 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, |
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 {{nowrap|−5 ≡ −17 (mod 12)}}, em vez de {{nowrap|1=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 (linguagem de programação)|C]], [[Java (linguagem de programação)|Java]], [[Javascript]], [[Perl]] e [[Python (linguagem de programação)|Python]]) ou "mod" (p.ex. in [[Pascal (linguagem de programação)|Pascal]], [[BASIC]], [[SQL]], [[Haskell (linguagem de programação)|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 (linguagem de programação)|Ruby]]). |
||
Em [[ciência da computação]], o operador resto é normalmente indicado por "%" |
|||
⚫ | ( |
||
Os parenteses às vezes não são escritos na expressão, por exemplo |
Os parenteses às vezes não são escritos na expressão, por exemplo {{nowrap|38 ≡ 14 mod 12}} ou {{nowrap|1=2 = 14 mod 12}}, ou são colocados em volta do divisor, por exemplo {{nowrap|38 ≡ 14 mod (12)}}. Notações como {{nowrap|38 (mod 12)}} também existem, mas são ambíguas sem um contexto. |
||
===Representação funcional da operação resto=== |
===Representação funcional da operação resto=== |
||
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 |
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> |
:<math>b = a - \left\lfloor \frac{a}{n} \right\rfloor \times n,</math> |
||
onde <math>\left\lfloor \frac{a}{n} \right\rfloor</math> |
onde <math>\left\lfloor \frac{a}{n} \right\rfloor</math> é o maior inteiro menor ou igual a <math>\frac{a}{n}</math>, então |
||
::<math>\begin{array}{lcl} |
::<math>\begin{array}{lcl} |
||
a \equiv b \pmod n \text{ e,}\\ |
a \equiv b \pmod n \text{ e,}\\ |
||
Linha 102: | Linha 99: | ||
== Sistema de resíduos == |
== Sistema de resíduos == |
||
Cada classe de resíduo |
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''.<ref name="Plinio"/> |
||
O conjunto de inteiros {0, 1, 2, ..., ''n'' - 1} é chamado o '''menor sistema de resíduos 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: |
É 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: | Linha 114: | ||
Alguns conjuntos que não são um sistema completo de resíduos módulo 4 são: |
Alguns conjuntos que não são um sistema completo de resíduos módulo 4 são: |
||
*{-5,0,6,22} |
*{-5,0,6,22} pois 6 é congruente a 22 módulo 4. |
||
*{5,15} |
*{5,15} pois um sistema completo de resíduos deve ter exatamente 4 elementos. |
||
=== Sistemas reduzidos de resíduos === |
=== 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'' |
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== |
==Referências== |
||
Linha 127: | Linha 124: | ||
<ref name="enciclopédia britânica">http://www.ams.org/samplings/feature-column/fcarc-eulers-formula</ref> |
<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="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> |
<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> |
</references> |
||
Revisão das 13h58min de 13 de julho de 2017
Este artigo ou se(c)ção está a ser traduzido. |
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 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.[1]
A aritmética modular foi desenvolvida posteriormente por Carl Friedrich Gauss em seu livro Disquisitiones Arithmeticae, publicado em 1801.
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 para 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.
Relação de congruência
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 congruentes (ou côngruos) módulo n, e escrevemos
quando a diferença deles . é um inteiro múltiplo de n. O número n é chamado o módulo da congruência.
Por exemplo,
pois 38 − 2 = 36, que é múltiplo de 12.
A mesma regra vale para valores negativos:
Se e são ou os dois positivos ou os dois negativos, então pode ser visto como a afirmação de que e tem o mesmo resto. Por exemplo
porque ambos e tem o mesmo resto 2. Observe que também se tem um inteiro múltiplo 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
e
então:
Deve notar-se 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
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 na divisão por não é interessante usarmos o módulo , pois para quaisquer e inteiros sempre teremos .
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 classes de equivalência do inteiro a, denotada por , é o conjunto . 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 .
O conjunto de todas as classes de congruência módulo n é denotado ou (a notação alternativa não é recomendada por causa da possível confusão com o conjunto dos inteiros p-ádicos). E é definida por:
Quando , tem n elementos, e pode ser escrita como:
Quando n = 0, não tem elementos não nulos; daí é isomorfo a , pois .
Podemos definir adição, subtração e multiplicação em pelas seguintes regras:
A verificação que esta é uma definição adequada usa as propriedades mencionadas antes.
Desta forma, se torna um anel comutativo. Por exemplo, no anel , temos
como na aritmética do relógio de ponteiro.
A notação é usada, por que ele é anel quociente de pelo ideal consistindo de todos os inteiros divisíveis por n, onde é o conjunto unitário . Assim é um corpo quando é um ideal máximal, ou seja, quando é primo.
Em termos de grupos, a classe de resíduos é a classe lateral de a no grupo quociente , um grupo cíclico.[2]
O conjunto 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 (que, como mencionado antes, é isomorfo ao anel 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
onde é o maior inteiro menor ou igual a , então
Se em vez do resto b o intervalo −n ≤ b < 0 é requirido, então
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.[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
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
- ↑ http://www.ams.org/samplings/feature-column/fcarc-eulers-formula
- ↑ Arnaldo Garcia e Yves Lequain. Elementos de Álgebra - Rio de Janeiro, IMPA, 2002. 326 páginas (Projeto Euclides), ISBN 978-85-244-0190-9
- ↑ 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