O general e o Teorema Chinês dos Restos

Na antiguidade, os generais chineses costumavam contar suas tropas perdidas após a guerra da seguinte forma: ordenavam que as tropas formassem várias colunas com um determinado tamanho e depois contavam quantas sobravam, e faziam isto para vários tamanhos diferentes [1].

Por exemplo, um general chinês possuia 1200 tropas antes da guerra. Após a guerra, ele alinhou as tropas de 5 em 5 de forma que sobraram 3 tropas. Quando alinhou de 6 em 6, também sobraram 3 tropas. Quando alinhou de 7 em 7, sobrou 1 tropa. E quando alinhou de 11 em 11, não sobrou nenhuma tropa. Quantas tropas o general tinha?

Para resolver este problema, é necessário saber lidar com congruências. Além disso, vamos utilizar uma poderosa arma em Teoria dos Números, chamada de Teorema Chinês dos Restos. De fato, o problema apresentado acima é uma aplicação direta deste teorema.

Basta então um pequeno esforço para interpretar o problema. Quando o general alinha suas tropas, formando colunas de tamanho n, ele está realizando uma divisão do número de tropas por n, e depois verificando seu resto.

Observe que, na prática, contar o resto é muito mais fácil que contar o número total, ou o quociente. Aliás, quem conhece um pouco de Teoria dos Números, sabe que raramente estamos interessados no quociente, o resto é o que importa.

O teorema

Não vou apresentar uma prova do Teorema Chinês dos Restos aqui. Simplesmente vou enunciá-lo (e exibir a forma geral de sua solução) para que possamos ir direto ao objetivo do artigo. Existem várias provas desse teorema e elas podem ser achadas na internet ou em livros.

Teorema Chinês dos restos : Sejam inteiros positivos e primos entre si. O sistema de congruências

tem solução única , onde , e é tal que (ou seja, é o inverso multiplicativo de módulo ).

Solução

Primeiramente, vamos organizar as informações do enunciado de forma matemática. Se x é o número de tropas restantes, temos:



Como 5, 6, 7 e 11 são primos entre si, basta aplicar o Teorema Chinês dos Restos. Para isso, vamos usar a "fórmula" mencionada anteriormente. Temos que:









Para calcular os é simples. Vou deduzir o primeiro deles, os outros irei omitir por serem análogos.

é tal que

Mas 462 deixa resto 2 quando dividido por 5, isto quer dizer que , substituindo acima temos que



Que número multiplicamos por 2 que o resto é 1 quando dividido por 5? é 3. Pois (na pior das hipóteses, só teríamos de testar 5-1=4 casos).

Então .

Repetindo o processo, temos



.

Pronto, agora basta jogar tudo na fórmula:







Portanto

que é equivalente a para todo q natural.

Mas queremos x maior que e menor que , o que implica que .

Isto significa que podemos comunicar ao general que lhe sobraram 1023 tropas após o combate [2].

Espero que tenha gostado... não o general, você.

Notas:

[1] Não consegui averiguar a veracidade deste fato. Como vi este problema originalmente num livro de matemática, pode ser que seja apenas fruto da imaginação de algum matemático. Contudo, acho bem plausível que um método como este (ou parecido) possa ter sido usado pelos chineses antigamente, visto que o teorema aplicado para a resolução do problema já era conhecido por eles. Se alguém souber se é verdade ou não, me avise!

[2] Note que o general organizou as tropas módulo 5, módulo 6, módulo 7 e módulo 11. Você consegue dizer se ele poderia ter organizado as tropas de outra forma? Além disso, note que M = 2310 é maior que 1200. Por que precisamos que M fosse maior que 1200?

Imagens de miniaturas legais que eu queria ganhar de presente retiradas de http://wargames.spyz.org.

Obs.: Post feito em homenagem ao Anônimo.