O teorema chinês do resto explicado

Um número deixa resto 2 na divisão por 3, resto 3 na divisão por 5 e resto 2 na divisão por 7. Que número é? Experimente os números um a um e ao fim de algum tempo chega a 23, mas a pergunta esconde um teorema: desde que os divisores não tenham fatores comuns, há sempre exatamente uma resposta abaixo do seu produto, e encontra-se sem experimentar nada. O teorema tem cerca de 1500 anos e continua a trabalhar em calendários, na aritmética dos computadores e na criptografia que protege a web.

Três filas de marcas para os números que deixam resto 2 mod 3, 3 mod 5 e 2 mod 7, alinhadas numa única coluna no 23
Três filas de marcas para os números que deixam resto 2 mod 3, 3 mod 5 e 2 mod 7, alinhadas numa única coluna no 23

Um problema do Sunzi Suanjing

O Sunzi Suanjing, um livro de aritmética chinês dos séculos III a V, pergunta por um número de coisas que, contadas de três em três, deixa 2, de cinco em cinco deixa 3 e de sete em sete deixa 2. A sua resposta é 23, e o seu método é o que ainda se ensina: tome 70 por cada coisa que sobra ao contar de três em três, 21 por cada uma que sobra ao contar de cinco em cinco e 15 por cada uma que sobra ao contar de sete em sete, some e subtraia 105 tantas vezes quanto possível. 2 × 70 + 3 × 21 + 2 × 15 = 233, e 233 − 2 × 105 = 23. Um poema da época Ming manteve os números 70, 21, 15 e 105 na memória durante séculos. Qin Jiushao deu um método geral em 1247, o mesmo problema aparece no Liber Abaci de Fibonacci de 1202, e Carl Friedrich Gauss enunciou o teorema na sua forma moderna nas Disquisitiones Arithmeticae de 1801.

Uma página de uma edição Qing do Sunzi Suanjing, o tratado de aritmética chinês dos séculos III–V que pede um número que deixe 2, 3 e 2 ao contar de três em três, de cinco em cinco e de sete em sete.
Uma página de uma edição Qing do Sunzi Suanjing, o tratado de aritmética chinês dos séculos III–V que pede um número que deixe 2, 3 e 2 ao contar de três em três, de cinco em cinco e de sete em sete.
Carl Friedrich Gauss, num retrato de Christian Albrecht Jensen de 1840. Introduziu a notação de congruência a ≡ b (mod n) nas Disquisitiones Arithmeticae de 1801.
Carl Friedrich Gauss, num retrato de Christian Albrecht Jensen de 1840. Introduziu a notação de congruência a ≡ b (mod n) nas Disquisitiones Arithmeticae de 1801.

O que diz o teorema

Tome módulos n₁, n₂, …, nₖ dos quais nenhum par tem um fator comum, e restos quaisquer a₁, a₂, …, aₖ. Então existe exatamente um número inteiro x de 0 a N − 1, onde N = n₁ × n₂ × … × nₖ, que deixa resto aᵢ na divisão por nᵢ, para cada i. Todas as outras soluções diferem dele por um múltiplo de N. Na notação da aritmética modular: o sistema x ≡ aᵢ (mod nᵢ) tem solução, e ela é única mod N. Dito de outra forma, um número de 0 a N − 1 e a sua lista de restos contêm exatamente a mesma informação: 3 × 5 × 7 = 105 números e 3 × 5 × 7 = 105 listas de restos possíveis, cada uma usada uma vez.

Construir a solução

Os números 70, 21 e 15 não são mágicos. Cada um deixa resto 1 na divisão pelo seu próprio módulo e resto 0 na divisão pelos outros: 70 = 2 × 35 é múltiplo de 5 e de 7 e deixa resto 1 na divisão por 3. Em geral, toma-se Nᵢ = N / nᵢ, múltiplo de todos os módulos exceto nᵢ, e multiplica-se por yᵢ, o inverso de Nᵢ mod nᵢ. O inverso existe porque Nᵢ e nᵢ não têm fatores comuns, e o algoritmo de Euclides estendido encontra-o: faz as divisões de Euclides para o máximo divisor comum e volta para trás até à identidade de Bézout 1 = s × nᵢ + t × Nᵢ, de modo que t é o inverso. Então x = a₁N₁y₁ + a₂N₂y₂ + …, reduzido mod N, satisfaz todas as equações, porque cada termo encaixa na sua própria equação e desaparece em todas as outras.

Uma equação de cada vez

Há um segundo método, que não precisa do produto de todos os módulos. Toda a solução de x ≡ 2 (mod 3) tem a forma x = 2 + 3t. Substituindo na equação seguinte, fica 2 + 3t ≡ 3 (mod 5), ou seja, 3t ≡ 1 (mod 5), e multiplicando por 2, o inverso de 3 mod 5, obtém-se t ≡ 2 (mod 5). Então x = 2 + 3 × 2 = 8, e as duas primeiras equações juntas dizem x ≡ 8 (mod 15). Repetindo com a terceira equação, 8 + 15t ≡ 2 (mod 7) dá t ≡ 1, por isso x ≡ 23 (mod 105). Esta substituição mantém os números mais pequenos, é a forma como um computador costuma resolver estes sistemas e continua a funcionar quando os módulos têm um fator comum.

Módulos com um fator comum

Se dois módulos têm um fator comum, as suas equações sobrepõem-se: x ≡ 1 (mod 4) já diz que x é ímpar, e x ≡ 4 (mod 6) diz que x é par, por isso nenhum x satisfaz as duas. Em geral, x ≡ a (mod m) e x ≡ b (mod n) podem verificar-se ao mesmo tempo exatamente quando a e b deixam o mesmo resto na divisão por g = gcd(m, n), isto é, quando g divide a − b. A solução é então única mod lcm(m, n) = m × n / g, e não mod m × n. O velho enigma do cesto de ovos, que deixa 1 quando se tiram de 2 em 2, de 3 em 3, de 4 em 4, de 5 em 5 ou de 6 em 6 e nenhum quando se tiram de 7 em 7, tem a resposta 301, que se repete a cada 420 = lcm(2, 3, 4, 5, 6, 7). Um sistema tem solução exatamente quando cada par das suas equações concorda, por isso um sistema impossível contém sempre um par em conflito.

Calendários, computadores e RSA

Em 1583, Joseph Scaliger combinou três ciclos do calendário, o ciclo solar de 28 anos, o ciclo lunar de 19 anos e a indição de 15 anos, no período juliano de 28 × 19 × 15 = 7980 anos. Pelo teorema, cada ano tem a sua própria combinação dos três números de ciclo, e o período começa em 4713 a.C., o último ano em que os três valiam 1; os astrónomos ainda contam os dias julianos a partir daí. Os computadores usam o teorema para calcular com números enormes como listas de restos pequenos, que se podem somar e multiplicar em separado e em paralelo, e juntar no fim. A decifração RSA funciona da mesma forma: c^d mod n com n = p × q é calculado como duas potências mod p e mod q juntas com o teorema, cerca de quatro vezes mais depressa do que uma potência mod n. Os esquemas de partilha de segredos, como os de Mignotte e de Asmuth e Bloom, escondem um segredo em restos, de modo que só restos suficientes em conjunto o revelam.

Ron Rivest, Adi Shamir e Len Adleman (da esquerda para a direita)
Ron Rivest, Adi Shamir e Len Adleman (da esquerda para a direita)

Experimente

Abra a calculadora para escrever qualquer sistema de congruências, até 20 equações e números até 200 algarismos, ou escolha um dos exemplos resolvidos: o problema de Sunzi, o cesto de ovos, o período juliano, dois horários de autocarro, a decifração RSA e um sistema sem solução. A resolução é escrita com os seus números, pela construção ou por substituição, com o algoritmo de Euclides estendido para cada inverso. A imagem marca os números que satisfazem cada equação, para ver a única coluna em que todas se encontram, ou dispõe os restos de duas equações numa tabela em que cada número tem a sua própria célula.

Perguntas frequentes

A solução de um sistema de congruências é única?

Só a menos de um múltiplo do módulo. Se x = 23 resolve o problema de Sunzi, também o resolvem 23 + 105 = 128, 233 e −82, porque somar 105 não muda nenhum dos restos. O teorema diz que há exatamente uma solução de 0 a 104; com módulos com fatores comuns, exatamente uma abaixo do seu mínimo múltiplo comum.

Porque têm os módulos de ser primos entre si?

Para a construção, porque Nᵢ tem de ter inverso mod nᵢ, e isso só existe quando não têm fatores comuns. Para o próprio teorema, porque os fatores comuns fazem algumas equações sobrepor-se: então um sistema ou não tem solução ou tem menos soluções diferentes, e as soluções repetem-se a cada mínimo múltiplo comum em vez de a cada produto.

Como encontro um inverso modular à mão?

Com o algoritmo de Euclides estendido. Para o inverso de 15 mod 7: 15 = 2 × 7 + 1, logo 1 = 15 − 2 × 7, e 15 × 1 ≡ 1 (mod 7): o inverso é 1. Para 35 mod 3: 35 = 11 × 3 + 2 e 3 = 1 × 2 + 1, logo 1 = 3 − 2 = 3 − (35 − 11 × 3) = 12 × 3 − 35, e o inverso de 35 mod 3 é −1 ≡ 2. Com módulos pequenos, também pode simplesmente experimentar 1, 2, 3, … até o produto deixar resto 1.

O que tem o teorema a ver com relógios?

Um resto mod n é uma posição num relógio de n horas. Dois relógios de 3 e 5 horas, que começam juntos e avançam uma hora de cada vez, mostram cada um dos 15 pares de posições uma vez antes de voltarem ao início, porque 3 e 5 não têm fatores comuns. Relógios de 4 e 6 horas voltam ao início ao fim de 12 passos e só mostram 12 dos 24 pares: uma posição ímpar e uma par nunca aparecem juntas.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Abrir a calculadora do teorema chinês do resto