Saltar para o conteúdo
Topos Uranos
Português

Congruências e aritmética modular

Resumo

Esta aula converte a classificação dos inteiros segundo seu resto em um cálculo. Define a congruência módulo nn, demonstra que ela equivale a deixar o mesmo resto, que é uma relação de equivalência e que respeita a soma, o produto e as potências, e constrói com suas classes o conjunto Zn\mathbb{Z}_n dos restos, com suas tábuas de somar e de multiplicar. Com a identidade de Bézout decide quais restos têm inverso e resolve por completo as congruências lineares; demonstra o teorema chinês do resto e o pequeno teorema de Fermat, relê os critérios de divisibilidade como congruências, e aplica tudo isso aos dígitos verificadores, ao calendário e ao sistema criptográfico RSA, cuja correção fica demonstrada.

Objetivos de aprendizagem

  1. Demonstrar que a congruência módulo nn é uma relação de equivalência compatível com a soma, o produto e as potências, e usá-la para calcular restos de números grandes.
  2. Construir as tábuas de somar e de multiplicar de Zn\mathbb{Z}_n e decidir, por meio do máximo divisor comum, quais restos têm inverso.
  3. Decidir se uma congruência linear tem solução, calcular quantas soluções tem módulo nn e encontrá-las todas.
  4. Resolver sistemas de congruências com módulos primos entre si por meio do teorema chinês do resto, construindo a solução e demonstrando sua unicidade.
  5. Demonstrar o pequeno teorema de Fermat e aplicá-lo a restos de potências, a divisibilidades que valem para todo inteiro e à correção do sistema RSA.
  6. Analisar quais erros um dígito verificador detecta e calcular dias da semana por meio de congruências.

A relação de congruência

Se hoje é segunda-feira, daqui a 1515 dias será terça-feira, e daqui a 10001000 dias será domingo: para sabê-lo não é preciso contar os dias um por um, porque basta o resto da divisão do número de dias por 77. Do mesmo modo, 55 horas depois das 99 são 22 horas em um relógio de 1212 horas, e o último algarismo de um produto depende só dos últimos algarismos dos fatores. Nos três casos se calcula com restos e se esquece o quociente. A aula sobre divisibilidade e divisão com resto repartiu os inteiros em classes segundo o resto que deixam ao serem divididos por um natural, e demonstrou que o resto de uma soma, de um produto e de uma potência depende só dos restos dos dados. Esta aula dá a essas observações uma linguagem própria, a das congruências, que Gauss introduziu em 1801 em suas Disquisitiones Arithmeticae, e a converte em um instrumento de cálculo. Como naquela aula, os inteiros são usados antecipadamente, com as regras de sua aritmética e de sua ordem que se fundamentam na aula sobre os números inteiros.

Definição (congruência). Seja nn um natural. Dois inteiros aa e bb são congruentes módulo nn se nn divide sua diferença a−ba - b. Escreve-se a≡b(modn)a \equiv b \pmod{n} e lê-se «aa é congruente a bb módulo nn»; o natural nn chama-se módulo da congruência.
a≡b(modn)↔n∣a−ba \equiv b \pmod{n} \leftrightarrow n \mid a - b

Assim, 17≡2(mod5)17 \equiv 2 \pmod{5}, porque 17−2=1517 - 2 = 15; −3≡9(mod4)-3 \equiv 9 \pmod{4}, porque −3−9=−12-3 - 9 = -12; e um inteiro é par exatamente quando é congruente a 00 módulo 22. Que aa seja múltiplo de nn escreve-se agora a≡0(modn)a \equiv 0 \pmod{n}. Com o módulo 11 todos os inteiros são congruentes entre si, porque 11 divide todo inteiro; esse caso carece de interesse, e nos exemplos o módulo será pelo menos 22. O sinal ≡\equiv, de três traços, lembra o da igualdade porque, como se verá, a congruência se comporta em quase tudo como ela; a exceção, a divisão, ocupará a seção sobre os inversos.

A definição pela diferença é a mais cômoda para demonstrar, mas a intuição dos exemplos iniciais é a do resto. A proposição seguinte assegura que ambas dizem o mesmo; seu conteúdo já foi observado, de outra forma, na aula sobre a divisibilidade, ao fundamentar os critérios de divisibilidade, e aqui é demonstrado com todos os seus passos.

ProposiçãoA congruência e o resto

Dois inteiros são congruentes módulo nn se e somente se deixam o mesmo resto ao serem divididos por nn. Sejam a=nq+ra = nq + r e b=ns+tb = ns + t as divisões com resto de aa e de bb por nn, com 0≤r<n0 \leq r < n e 0≤t<n0 \leq t < n. A figura dispõe os inteiros desde −10-10 até 2424 em filas de 55, de modo que cada coluna reúne os que deixam um mesmo resto.

Demonstração

  1. a−b=(nq+r)−(ns+r)=n(q−s)a - b = (nq + r) - (ns + r) = \resaltar{n(q - s)}

    Se os restos coincidem, r=tr = t, ao subtrair as duas divisões o resto se cancela, e a diferença é múltiplo de nn.

  2. a=b+nk=ns+t+nk=n(s+k)+ta = \resaltar{b} + nk = \resaltar{ns + t} + nk = \dato{d}{n(s + k) + t}

    Reciprocamente, suponhamos que nn divide a−ba - b, isto é, que a=b+nka = b + nk para algum inteiro kk. Substituímos a divisão de bb.

  3. 0≤t<n→r=t0 \leq t < n \rightarrow \resaltar{r = t}

    Como 0≤t<n0 \leq t < n, esta igualdade é uma divisão de aa por nn com resto tt. Pela unicidade do quociente e do resto, tt é o resto de aa, isto é, t=rt = r.

  4. 23≡8≡−2≡−7≡3(mod5)23 \equiv 8 \equiv -2 \equiv -7 \equiv 3 \pmod{5}

    Na figura, −7-7, −2-2, 33, 88, 1313, 1818 e 2323 ocupam a mesma coluna: todos deixam resto 33, e suas diferenças são múltiplos de 55.

Em particular, todo inteiro é congruente módulo nn a seu resto, que é um dos nn inteiros 0,1,…,n−10, 1, \ldots, n - 1, e a um só deles, porque dois desses inteiros são seus próprios restos e, se são distintos, deixam restos distintos. Calcular módulo nn consiste em substituir cada número por um representante cômodo de sua coluna: o resto, ou às vezes um número negativo pequeno, como −1-1 em lugar de n−1n - 1.