View
0
Download
0
Category
Preview:
Citation preview
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
Recommended