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.[1] 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 , 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, é congruente com módulo , então "15:00" em um relógio de 24 horas é exibido "3:00 "em um relógio de 12 horas.

CongruênciaEditar

Dado um inteiro  , chamado módulo, dois inteiros são considerados congruentes (ou côngruos) módulo  , se   for um divisor de sua diferença (ou seja, se houver um inteiro   tal que  ).

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

 

Os parênteses significam que   se aplica a toda a equação, não apenas ao lado direito (aqui  ). Esta notação não deve ser confundida com a notação   (sem parênteses), que se refere à operação módulo. Na verdade,   denota o número inteiro único   tal que   e   (ou seja, o restante de   quando dividido por  [2]).

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

 

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

 
 

onde   é o resto comum. Subtraindo essas duas expressões, recuperamos a relação anterior:

 

definindo  .

ExemplosEditar

Exemplo 1Editar

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

 

porque  , 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:

 

Exemplo 2Editar

 

pois  , que é múltiplo de 12. Note que   e   tem o mesmo resto 2. Observe que também, utilizando o exemplo anterior,   é inteiro múltiplo de 12, isto é  , concordando com a definição inicial de relação de congruência.

NotaçãoEditar

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   for usada, em vez da notação tradicional.

PropriedadesEditar

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

  • Reflexividade:  
  • Simetria:   se   para todo  ,   e  .
  • Transitividade: Se   e  , então  

Se   e  , ou se  , então:

  •   para qualquer inteiro   (compatibilidade com translação)
  •   para qualquer inteiro   (compatibilidade com escala)
  •   (compatibilidade com adição)
  •   (compatibilidade com subtração)
  •   (compatibilidade com multiplicação)
  •   para qualquer inteiro não negativo   (compatibilidade com exponenciação)
  •  , para qualquer polinômio   com coeficientes inteiros (compatibilidade com avaliação polinomial)

Se  , então geralmente é falso que  . No entanto, o seguinte é verdadeiro:

  • Se  , onde   é a função totiente de Euler, então  —desde que   seja coprimo com  .

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

  • Se   para qualquer inteiro  , então  
  • Se   e   é coprimo com  , então  

O inverso multiplicativo modular é definido pelas seguintes regras:

  • Existência: existe um inteiro denotado   tal que   se e somente se   é coprimo com  . Este inteiro   é chamado de inverso multiplicativo modular de   módulo  .
  • Se   e   existem, então   (compatibilidade com o inverso multiplicativo e, se  , unicidade módulo  )
  • Se   e   é coprimo com  , então a solução para esta congruência linear é dada por  

O inverso multiplicativo   pode ser eficientemente calculado resolvendo a equação de Bézout   para  —usando o algoritmo Euclidiano estendido.

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

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

  • Pequeno teorema de Fermat: Se   é primo e não divide  , então  .
  • Teorema de Euler: Se   e   são coprimos, então a  , onde   é a função totiente de Euler
  • Uma consequência simples do pequeno teorema de Fermat é que se   é primo, então   é o inverso multiplicativo de  . De maneira mais geral, a partir do teorema de Euler, se   e   são coprimos, então  .
  • Outra consequência simples é que se  , onde   é a função totiente de Euler, então   desde que   seja coprimo com  .
  • Teorema de Wilson:   é primo se e somente se  .
  • Teorema do resto chinês: Para qualquer  ,   e coprime  ,  , existe um único   tal que   e  . De fato,   onde   é o inverso de   módulo   e   é o inverso de   módulo  .
  • Teorema de Lagrange: A congruência  , onde   é primo, e   é um polinômio com coeficientes inteiros tais que   , tem no máximo   raízes.
  • Raiz primitiva módulo n: Um número   é uma raiz primitiva módulo   se, para cada inteiro um coprimo com  , existe um inteiro   tal que  . Uma raiz primitiva módulo   existe se e somente se   for igual a  ,  ,   ou  , onde   é um número primo ímpar e   é um inteiro positivo. Se existe uma raiz primitiva módulo  , então existem exatamente   tais raízes primitivas, onde   é a função totiente de Euler.
  • Resíduo quadrático: Um inteiro   é um resíduo quadrático módulo  , se existir um inteiro   tal que  . O critério de Euler afirma que, se   é um primo ímpar, e   não é um múltiplo de  , então   é um resíduo quadrático módulo   se e somente se
 

Classes de congruênciaEditar

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   modulo  , é chamado a classe de congruência ou classe de resíduos ou simplesmente resíduo do inteiro   modulo  . Quando o módulo   é conhecido pelo contexto, este resíduo também pode ser denotado por  .

Anel de classes de congruênciaEditar

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

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.

RestosEditar

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 restoEditar

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 −nb < 0 é requirido, então

 

Sistema de resíduosEditar

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.[4]

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íduosEditar

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)[5]Editar

Considere a equação  , onde  ,   é um primo (ímpar) e  . Podemos observar que   e como   é ímpar temos  . Assim, a equação acima é equivalente a  . Ao completarmos quadrados obtemos  . Ao fazermos   e  , vem  . Para descobrir as soluções da equação quadrática, basta descobrir as soluções da equações da forma  . Pois se   (lê-se "p divide a") obtemos desinteressante a equação   e, por essa razão   o que torna indispensável assumir que   ("p não divide a") a fim de evitarmos soluções triviais.

ExemploEditar

Resolva a congruência  .

Como   e   é primo ímpar temos que  , no qual ao multiplicarmos a congruência em questão e completar quadrados obtemos  . Com isso encontramos  , onde ao resolvermos a congruência linear   temos  , enquanto a partir da congruência linear  , obtemos  . Dessa maneira,   e   são as únicas soluções incongruentes. De fato, se   e  . Se   e  .

ReferênciasEditar

  1. http://www.ams.org/samplings/feature-column/fcarc-eulers-formula
  2. «Comprehensive List of Algebra Symbols». Math Vault (em inglês). 25 de março de 2020. Consultado em 12 de agosto de 2020 
  3. Arnaldo Garcia e Yves Lequain. Elementos de Álgebra - Rio de Janeiro, IMPA, 2002. 326 páginas (Projeto Euclides), ISBN 978-85-244-0190-9
  4. 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
  5. SAID, Sidki. Introdução à Teoria dos Números. Colóquio Brasileiro de Matemática, IMPA, 1975.