UNIVERSIDADE ESTADUAL DE CAMPINAS

INSTITUTO DE MATEMÁTICA ESTATÍSTICA E COMPUTAÇÃO CIENTÍFICA

MONOGRAFIA

TEOREMA DO RESTO CHINÊS

MA673

Dario Silva Nascimento RA 139391

Felipe Ferreira RA 120919

Marcel Bento de Oliveira RA 119826

Campinas Setembro 2016

Sumário

Conteúdo

Sumário ......................................................................................................................................... 2

Introdução ..................................................................................................................................... 3

Um pouco mais sobre a História do Teorema Chinês do Resto ................................................ 3

O Desenvolvimento do Teorema do Resto Chinês .................................................................... 4

Sistemas de congruências ............................................................................................................. 7

Exemplo1 ................................................................................................................................... 7

Solução: ................................................................................................................................. 7

Exemplo 2 .................................................................................................................................. 8

Solução: ................................................................................................................................. 8

Aplicação ..................................................................................................................................... 10

Teorema Chinês dos Restos ........................................................................................................ 12

Demonstração ......................................................................................................................... 12

(Parte 1) ............................................................................................................................... 12

(Parte 2) ............................................................................................................................... 13

Conclusões .................................................................................................................................. 15

Referências .................................................................................................................................. 16

Introdução

O teorema chinês dos restos - bem como diversos outros assuntos estudados em matemática -

surgiu a partir de algum problema prático. Neste trabalho, articularemos sobre as origens do

teorema, sua parte histórica, aplicações e demonstração.

Não se sabe ao certo, mas a história mais comum sobre o surgimento deste teorema é através

do tipo de contagem que os generais chineses realizavam sobre suas tropas antes e após as

batalhas. Eles 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.

Por exemplo, um general chinês possuía 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 é utilizado o conceito de congruências e o teorema em questão.

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. Na prática, contar o

resto é muito mais fácil que contar o número total ou o quociente. Daí então o surgimento do

teorema. Resolveremos este exemplo mais adiante.

Um pouco mais sobre a História do Teorema Chinês do Resto

O mais antigo problema de resíduo do mundo foi descoberto no século III, no manuscrito

chinês intitulado Sun Zi Suanjing 孙子算经 (Manual de aritmética do mestre Sun), do qual o

autor era desconhecido.

Atualmente, o problema do resto de Sun Zi Suanjing é popularmente conhecido como o

Teorema Chinês do Resto, pelo motivo da sua primeira aparição no manuscrito do matemático

chinês.

O Teorema do Resto Chinês foi encontrado no Capitulo 3, problema 26 do Sun Zi Suanjing:

Existe um numero desconhecido de objetos, se nós contarmos de 3 em 3, teremos

resto 2, se contarmos de 5 em 5, teremos resto 3, se contarmos de 7 em 7, teremos

resto 2. Descubra o número de objetos.

Além da questão, o autor Sun Zi Suanjing também providenciou a resposta e o método da

solução como segue abaixo:

Desde a antiguidade, existem muitas pesquisas que foram feitas sobre o Teorema Chinês do

Resto, e atualmente esse teorema evoluiu para uma forma sistemática que pode facilmente

ser descoberto em muitos textos matemáticos.

Desde sua primeira aparição em Sun Zi Suanjing, o Teorema do Resto Chinês continua atraindo

muitos matemáticos antigos de outras civilizações para discutir e acrescentar comentários nos

seus respectivos estudos matemáticos.

O Desenvolvimento do Teorema do Resto Chinês

Somente uma solução foi encontrada em Sun Zi Suanjing. O autor não nos da maiores

explicações do porque os números 70,21 e 15 foram escolhidos nem porque um múltiplo de

105 precisa ser subtraído da soma dos produtos que foram adicionados. O método da solução

em Sun Zi Suanjing sem uma elaboração mais aprofundada levantou muitas questões dentre

os pesquisadores que desejavam dominar o método por completo.

Durante o século XI, o matemático muçulmano Ibn Tahir al-Baghdadi discutiu o Teorema

Chinês do Resto em seu manuscrito AITakmilafi 'lim ai-Hisab. O módulo que ele colocou foi o

mesmo que Sun Zi Suanjing, o qual 𝑚1 = 3, 𝑚2 = 5, 𝑚3 = 7. Entretanto, seu problema foi

𝑥 ≡ 𝑎(𝑚𝑜𝑑 3) ≡ 𝑏(𝑚𝑜𝑑 5) ≡ 𝑐(𝑚𝑜𝑑 7)que não é inteiramente o mesmo que Sun Zi

Suanjing. Estava claro que Ibn Tahir havia avançado em suas escritas sobre o problema do

resto, no qual a,b e c eram restos arbitrários dados em seu problema.

É interessante notar que Ibn Tahir foi o primeiro matemático na antiguidade a explicar a

relação do porque os números 70,21 e 15 foram relacionados com o módulo 3,5 e 7

respectivamente. Ele explicou que para cada módulo, o número relacionado era obtido pela

multiplicação de outro módulo envolvido no problema, dados que os pares são relativamente

primos entre si. Depois disso, a divisão era feita na soma da multiplicação repetidamente ate

que o resto seja 1.

Resposta: 23.

Método: Se contarmos de 3 em 3 e tivermos resto 2, consideramos 140. Se

contarmos de 5 em 5 e tivermos resto 3, consideramos 63. Se contarmos de 7 em 7

e tivermos resto 2, consideramos 30. Adicionando-os, obtemos 233 e subtraindo

210 chegamos a resposta. Se contarmos de 3 em 3 e tivermos resto 1,

consideramos 70. Se contarmos de 5 em 5 e tivermos resto 1, consideramos 21. Se

contarmos de 7 em 7 e tivermos resto 1, consideramos 15. Quando (um número)

excede 106, o resultado é obtido subtraindo por 105.

O Teorema Chinês do Resto encontrou o seu caminho para a Europa no famoso manuscrito

matemático do Italiano Leonardo Fibonacci, em 1202 intitulado Liber Abaci. Embora o módulo

dado seja o mesmo, o problema do resto no Liber Abaci era levemente diferente que o de Sun

Zi Suanjing no sentido que um dos restos dados era diferente. Entretanto, o método da

solução dada no Liber Abaci era completamente o mesmo que em Sun Zi Suanjing.

Desde Sun Zin Suanjing, o Teorema Chinês do Resto não foi descoberto novamente por

nenhum manuscrito chinês até o século XIII, no livro Xugu Zhaiqi Suanfa 續古摘奇算法

(Continuação do Método Matemático para Esclarecer o Desconhecido) em Yang Hui

Suanfa 楊輝算法 (O Método Computacional de Yang Hui). Yang Hui Suanfa foi uma coleção de

3 livros do Matemático Chinês Yang Hui em 1278.

O problema do resto em Xugu Zhaiqi Suanfa foi exatamente o mesmo que o problema do resto

original e a mesma solução única foram dados para o problema. Em Xugu Zhaiqi Suanfa, Yang

Hui claramente estabeleceu o que ele havia pego o problema do resto do Sun Zi Suanjing.

Entretanto, acrescentou no problema do resto original, propondo outro problema e tornando

assim 4 problemas de resto.

Fibonacci foi o primeiro Europeu a levar adiante a discussão sobre o Teorema do Resto Chinês

em suas escritas. Mais tarde, no século XIV e XV, Isaac Argyros e FraterFrederius discutiram o

problema do resto chinês em suas dissertações Eisagoge Arithmetic e Munich Manuscript

respectivamente, com a mesma solução dada pelo matemático mulçumano Ibn Tahir. Frater

Frederius foi o único matemático depois de Ibn Tahir que ofereceu uma explicação em relação

a um número especifico que era relacionado com o seu respectivo módulo, um mistério não

resolvido desde Sunzi Suanjing.

Não é nenhuma surpresa que a discussão do problema do resto nos trabalhos de Argyros e

Frederius foram similares aos de Ibn Tahir. Em geral muitos trabalhos

de matemáticos europeus na antiguidade eram bastante influenciados em suas pesquisas

pelos trabalhos dos matemáticos muçulmanos. Fibonacci foi o pioneiro dos matemáticos

europeus que fez pesquisas extensivas nos trabalhos matemáticos muçulmanos como Tara'if

al-Hisab do Abu Kamil. Ele mais tarde incorporou muitos dos problemas em seu grande

manuscrito Liber Abar.

A ordem do desenvolvimento cronológico do Teorema do Resto Chinês segue abaixo:

Matemático

Século

Título do manuscrito

Civilização

Sun Zi

3

Sun Zi Suanjing

Chinesa

Ibn Tahir

11

Al-Tàkmila fi’ Ilm Al- Hisab

Árabe

Leonardo Fibonacci

13

Liber abaci

Europeia

Yabg Hui

13

Buku Xuga Zhaiqi Suanfa dalam

Yang Hui Suanfa

Chinesa

Isaac Argyros

14

Eisagog’ e Arithm’etik’e

Europeia

Frater Frederius

15

Munich Manuscript

Europeia

Sistemas de congruências

Exemplo1

Em um cesto, há uma quantidade N de ovos. Se os ovos forem agrupados de 3 em 3,

sobram 2. Se os ovos forem agrupados de 4 em 4, sobra 1. Quantos ovos pode haver

no cesto?

Solução:

• 𝑁 ≡ 2 𝑚𝑜𝑑 3 → 𝑁 = 3.𝑎 + 2, 𝑎 ∈ ℕ (1)

• 𝑁 = 1 𝑚𝑜𝑑 4 (2)

Substituindo (1) em (2):

𝑁 ≡ 3.𝑎 + 2 ≡ 1 𝑚𝑜𝑑 4

3.𝑎 + 2 ≡ 1 𝑚𝑜𝑑 4

3.𝑎 ≡ −2 + 1 𝑚𝑜𝑑 4

3.𝑎 ≡ −1 𝑚𝑜𝑑 4

3.𝑎 ≡ 3 𝑚𝑜𝑑 4

Como 3 e 4 são co-primos, vale a lei do cancelamento, assim:

𝑎 ≡ 1 𝑚𝑜𝑑 4

𝑎 ≡ 4. 𝑏 + 1, 𝑏 ∈ ℕ (3)

Substituindo (3) em (1):

𝑁 = 3 4.𝑏 + 1 + 2 = 12. 𝑏 + 3 + 2 = 12. 𝑏 + 5 ⟹𝑁 ≡ 5(𝑚𝑜𝑑12)

Portanto, a quantidade de ovos é 5.

Exemplo 2

Um general possui 2000soldados para uma batalha. Terminado o confronto o general

precisou verificar suas baixas. Então, mandou que os soldados formassem alinhados de

7 em 7 e verificou que sobraram 5. Em seguida, ordenou que formassem alinhados de

9 em 9 e verificou que sobraram 4. Por fim, fez com que os soldados formassem

alinhados de 10 em 10 e sobrou apenas 1.

Quantos soldados morreram em combate se há mais de 1500 indivíduos na formatura?

Solução:

Podemos traduzir o enunciado do seguinte modo:

• 𝑁 ≡ 5(𝑚𝑜𝑑 7) (1)

• 𝑁 ≡ 4(𝑚𝑜𝑑 9) (2)

• 𝑁 ≡ 1(𝑚𝑜𝑑 10) (3)

Reescrevemos (1) como:

𝑁 = 7.𝑎 + 5 (4)

Substituindo (4) em (2);

7.𝑎 + 5 ≡ 4 𝑚𝑜𝑑 9 ⟹ 7.𝑎 ≡ −5 + 4 𝑚𝑜𝑑 9 ⟹

7.𝑎 ≡ −1(𝑚𝑜𝑑 9) ⟹ 7.𝑎 ≡ 8(𝑚𝑜𝑑 9)

Considerando que não vale a lei do cancelamento, procuramos a classe inversa do 7,

módulo 9. Note que 4 é a classe inversa, pois:

4.7 ≡ 1(𝑚𝑜𝑑 9)

Então,

1𝑎 ≡ 32 𝑚𝑜𝑑 9 ⟹ 𝑎 ≡ 5 𝑚𝑜𝑑 9 ⟹ 𝑎 = 9𝑏 + 5 (5)

Substituindo (5) em (4):

𝑁 = 7. 9𝑏 + 5 + 5 ⟹𝑁 = 63𝑏 + 40 (6)

Aplicando (6) na equação (3):

63𝑏 + 40 ≡ 1 𝑚𝑜𝑑 10 ⟹ 3𝑏 + 0 ≡ 1 𝑚𝑜𝑑 10 ⟹ 3𝑏 ≡ 1(𝑚𝑜𝑑10)

Novamente, não é possível fazer o cancelamento; então, buscamos a classe de inversa

de 3, módulo 10. Note que 7 é a classe inversa pois:

3.7 ≡ 1(𝑚𝑜𝑑 10)

Logo,

7.3𝑏 ≡ 7.1 𝑚𝑜𝑑 10 ⟹ 21𝑏 ≡ 7(𝑚𝑜𝑑 10) ⟹

1𝑏 ≡ 7 𝑚𝑜𝑑 10 ⟹ 𝑏 ≡ 7 𝑚𝑜𝑑 10 ⟹

𝑏 = 10. 𝑐 + 7 𝑐 ∈ ℕ (7)

Substituindo (7) em (6):

𝑁 = 63. 10𝑐 + 7 + 40 ⟹𝑁 = 630𝑐 + 481 ⟹𝑁 ≡ 481(𝑚𝑜𝑑 630)

Observe que630 = 7.9.10que são os módulos do sistema inicial, mas isso não é uma

coincidência, e mais á frente entenderemos o porque.

As soluções para o sistema são:

𝑁 = 481 𝑚𝑜𝑑 630

{481, 1111, 1741,… }

A Solução que procuramos está limitada pelo enunciado entre 1500 e 2000; assim, a

solução para o problema é 1741.

Aplicação

Dado o exemplo resolvido pelo sistema de congruências, vamos resolver o mesmo

problema utilizando um algoritmo que se justifica pelo teorema chinês dos restos.

𝐴 𝑀 𝑀′ (𝑀′)−1 𝐴.𝑀. (𝑀′)−1 𝑁 ≡ 5(𝑚𝑜𝑑 7) 5 90 6 6 2700

𝑁 ≡ 4(𝑚𝑜𝑑 9) 4 70 7 4 1120

𝑁 ≡ 1(𝑚𝑜𝑑 10) 1 63 3 7 441

Para a construção da tabela acima consideramos que:

•Na primeira coluna, descrevemos as equações dadas no problema.

•Na segunda coluna, 𝐴, preenchemos com os restos de cada equação.

•Na terceira coluna, 𝑀, o primeiro número está associado à primeira equação de

modo que, tomamos o produto dos dois outros módulos, ou seja:

₋ Referente à equação 𝑁 ≡ 5(𝑚𝑜𝑑 7), tem-se 𝑀 = 9.10 = 90, e assim

sucessivamente.

•Na quarta coluna, 𝑀′, escrevemos a classe de equivalência de cada um dos elementos

da terceira coluna𝑚𝑜𝑑 7, 𝑚𝑜𝑑 9 𝑒 𝑚𝑜𝑑 10.

90 (𝑚𝑜𝑑 7) ≡ 6

70 (𝑚𝑜𝑑 9) ≡ 7

63 (𝑚𝑜𝑑 10) ≡ 3

•Na quinta coluna, (𝑀′)−1,calculamos a classe inversa de cada elemento da coluna 𝑀′,

sempre respeitando o módulo referente a cada linha.

A classe inversa de 6 (𝑚𝑜𝑑 7) é 6, pois 6.6 = 36 ≡ 1 (𝑚𝑜𝑑 7).

A classe inversa de 7 (𝑚𝑜𝑑 9) é 4, pois 7.4 = 28 ≡ 1 (𝑚𝑜𝑑 9).

A classe inversa de 3 (𝑚𝑜𝑑 10) é 7, pois 3.7 = 21 ≡ 1 (𝑚𝑜𝑑 10).

•Na sexta coluna, 𝐴.𝑀. (𝑀′)−1, fazemos o produto dos elementos, referentes à cada

linha

A resposta para o nosso problema será dada em (𝑚𝑜𝑑 7.9.10) e somando-se os

resultados da sexta coluna, ou seja:

4261 𝑚𝑜𝑑 630 ⟹ 481(𝑚𝑜𝑑 630)

Assim, as possíveis respostas para o número 𝑁têm a forma:

𝑁 = 481 + 630𝑛que nos permite as soluções {481, 1111, 1741, 2371,… }e, como

já vimos, a solução é 1741.

Conhecido o algoritmo, segue o enunciado do teorema chinês dos restos.

Teorema Chinês dos Restos

Sejam 𝑚1 ,𝑚2 ,… ,𝑚𝑘 inteiros positivos primos dois a dois. Então o sistema

𝑥 ≡ 𝐴1(𝑚𝑜𝑑 𝑚1)

…𝑥 ≡ 𝐴𝑘(𝑚𝑜𝑑 𝑚𝑘)

Tem solução única (𝑚𝑜𝑑(𝑚1 .𝑚2 .… .𝑚𝑘))

Apresentado o algoritmo, faremos a generalização e, a partir da sua compreensão,

estabeleceremos a demonstração do teorema.

𝐴 𝑀 𝑀′ (𝑀′)−1 𝐴.𝑀. (𝑀′)−1

𝑥 ≡ 𝐴1(𝑚𝑜𝑑 𝑚1)

...

𝑥 ≡ 𝐴𝑘(𝑚𝑜𝑑 𝑚𝑘)

𝐴1

... 𝐴𝑘

𝑀1

...

𝑀𝑘

𝑀′1

...

𝑀′𝑘

(𝑀′1)−1

...

(𝑀′𝑘)−1

∗

... ∗

Este algoritmo mostra a solução do nosso sistema de congruências tem a forma:

𝑋 = 𝐴1 .𝑀1 . (𝑀1′)−1 + 𝐴2 .𝑀2 . (𝑀2′)

−1 + ⋯+ 𝐴𝑘 .𝑀𝑘 . (𝑀𝑘 ′)−1

Em que:

𝑀1 = 𝑚2 .𝑚3 .𝑚4 .… .𝑚𝑘

𝑀2 = 𝑚1 .𝑚3 .𝑚4 .… .𝑚𝑘

𝑀3 = 𝑚1 .𝑚2 .𝑚4 .… .𝑚𝑘

𝑀4 = 𝑚1 .𝑚2 .𝑚3 .… .𝑚𝑘

… 𝑀𝑘 = 𝑚1 .𝑚2 .𝑚3 .… .𝑚𝑘−1

Demonstração

(Parte 1)

Mostrar que existe solução e que esta solução tem forma:

𝑋 = 𝐴1 .𝑀1 . (𝑀1′)−1 + 𝐴2 .𝑀2 . (𝑀2′)

−1 + ⋯+ 𝐴𝑘 .𝑀𝑘 . (𝑀𝑘 ′)−1

Para tanto, reescreveremos a suposta solução em módulo 𝑚1:

(𝑚𝑜𝑑 𝑚1 )𝑋 = 𝐴1 .𝑀1 . (𝑀1′)−1 + 𝐴2 .𝑀2 . (𝑀2′)

−1 + ⋯+ 𝐴𝑘 .𝑀𝑘 . (𝑀𝑘 ′)−1

Note que, 𝑀2 = 𝑚1 .𝑚3 .𝑚4 .… .𝑚𝑘 , isto é, 𝑚1|(𝐴2.𝑀2 . (𝑀2′)−1).

Assim, podemos dizer que 𝐴2 .𝑀2 . (𝑀2′)−1 ≡ 0(𝑚𝑜𝑑 𝑚1).

De forma análoga, estendemos a ideia para os termos seguintes:

𝑚1| (𝐴3 .𝑀3 . (𝑀3′)

−1) ⟹ 𝐴3 .𝑀3 . (𝑀3′)−1 ≡ 0(𝑚𝑜𝑑 𝑚1)

…𝑚𝑘 | (𝐴𝑘 .𝑀𝑘 . (𝑀𝑘 ′)

−1) ⟹ 𝐴𝑘 .𝑀𝑘 . (𝑀𝑘 ′)−1 ≡ 0(𝑚𝑜𝑑 𝑚1)

Assim, temos que,

(𝑚𝑜𝑑 𝑚1 )𝑋 = 𝐴1 .𝑀1. (𝑀1′)−1

Mas, tratando-se de congruências, podemos trocar 𝑀1pela classe de

equivalência (𝑚𝑜𝑑 𝑚1 ):

(𝑚𝑜𝑑 𝑚1 )𝑋 = 𝐴1 .𝑀1. (𝑀1′)−1 ≡ 𝐴1 .𝑀′1 . (𝑀1′)

−1. De forma que

(𝑚𝑜𝑑 𝑚1 )𝑋 ≡ 𝐴1. Mostramos que o modelo resolve a primeira equação do

sistema de congruências.

Utilizando a mesma ideia nas outras equações do sistema, podemos verificar que:

(𝑚𝑜𝑑 𝑚1 )𝑋 ≡ 𝐴1 .𝑀1 . (𝑀1′)

−1 ≡ 𝐴1 .𝑀′1 . (𝑀1′)

−1 ≡ 𝐴1

(𝑚𝑜𝑑 𝑚2 )𝑋 ≡ 𝐴2 .𝑀2 . (𝑀2′)−1 ≡ 𝐴2 .𝑀′

2 . (𝑀2′)−1 ≡ 𝐴2

… (𝑚𝑜𝑑 𝑚𝑘 )𝑋 ≡ 𝐴𝑘 .𝑀𝑘 . (𝑀𝑘 ′)

−1 ≡ 𝐴𝑘 .𝑀′𝑘 . (𝑀𝑘 ′)

−1 ≡ 𝐴𝑘

Deste modo, mostra-se que o modelo proposto resolveu as k equações do sistema de

congruências.

(Parte 2)

Tendo visto que o sistema de congruências tem solução da forma

𝑋 = 𝐴1 .𝑀1 . (𝑀1′)−1 + 𝐴2 .𝑀2 . (𝑀2′)

−1 + ⋯+ 𝐴𝑘 .𝑀𝑘 . (𝑀𝑘 ′)−1

Vamos mostrar que essa solução é única (𝑚𝑜𝑑(𝑚1 .𝑚2 .… .𝑚𝑘))

Vamos supor que exista uma solução 𝑦 tal que 𝑦 ≢ 𝑥. Como 𝑦 é solução do

sistema, em particular

𝑦 ≡ 𝐴1(𝑚𝑜𝑑 𝑚1)𝑥 ≡ 𝐴1(𝑚𝑜𝑑 𝑚1)

⇒ 𝑦 − 𝑥 ≡ 0(𝑚𝑜𝑑 𝑚1) ⇒ 𝑚1|𝑦 − 𝑥

Analogamente;

𝑚2|𝑦 − 𝑥𝑚3|𝑦 − 𝑥

…𝑚𝑘 |𝑦 − 𝑥

Como 𝑚1 ,𝑚2 ,… ,𝑚𝑘 são primos entre si 2 a 2, pode-se afirmar que

(𝑚1 .𝑚2 .𝑚3 .… .𝑚𝑘)|𝑦 − 𝑥 ⇒ 𝑦 − 𝑥 ≡ 0(𝑚𝑜𝑑(𝑚1 .𝑚2 .𝑚3 .… .𝑚𝑘)), que é

um absurdo! Isso mostra que a solução é única

∎

Conclusões

Fica claro que na utilização do teorema em questão e do algoritmo, o problema da

contagem de grandes grupos torna-se, de certa forma, muito mais fácil e eficiente.

Portanto o Teorema dos Restos Chinês é de suma importância nesse tipo de problema.

Referências

https://pt.wikipedia.org/wiki/Teorema_chin%C3%AAs_do_resto

Monografias do acervo

http://legauss.blogspot.com.br/2009/06/o-general-e-o-teorema-chines-dos-

restos.html

Introdução à Aritmética Modular; George Darmiton da Cunha Cavalcanti; CIn – UFPE

https://www.youtube.com/watch?v=tcgi_4DRZM0