Universidade Estadual de Campinas – UNICAMP Instituto de Matemática e
Computação Científica – IMECC Matemática – Licenciatura.
Gabriel Luiz Martinez
Ra: 135800
Teorema do resto Chinês e aplicações.
Campinas, Maio de 2015.
1
Sumário
1.Introdução...3
2.Objetivos...4
3.Origem...5
4. Teorema Chinês do resto...6
4.1 Prova para 2 equações...6
4.2 Teorema Chinês do Resto (versão forte) Enunciado...6
4.3 Demonstração do Teorema Chinês do Resto (versão forte)...7
4.4 Exemplo...7
5. Aplicação em grupos...8
5.1 Produtos cartesianos em Z...8
5.2 exemplo 1...8
5.3 exemplo 2...8
5.4 casos gerais...9
6. Conclusão...10
7. Referências...11
2
1. Introdução
Teorema Chinês do Resto (caso com duas equações) Dados dois inteiros 𝑚1 , 𝑚2 ≥ 2
primos entre si (isto é, mdc(𝑚1 , 𝑚2 ) = 1), e dados outros dois inteiros quaisquer 𝑎1 , 𝑎2 ,
o sistema:
𝑥 ≡ 𝑎1 𝑚𝑜𝑑 𝑚1
(1)
{
𝑥 ≡ 𝑎2 𝑚𝑜𝑑 𝑚2
Possui uma solução x = 𝑥0 . Além disso, um inteiro x será solução do sistema se e
somente se:
x ≡ 𝑥0 mod 𝑚1 𝑚2.
A conclusão do Teorema também pode ser expressa assim: O conjunto de soluções
do sistema é sempre da forma {𝑥0 + k𝑚1 𝑚2; k ∈ Z}. Em particular, a solução é única
mod 𝑚1 𝑚2.
Esse teorema pode ser generalizado para n equações e podendo ser utilizado em uma
gama de problemas matemáticos. Aqui nos centralizaremos em estudar o teorema e
sua aplicação na área de grupos.
3
2. Objetivos
Obter conhecimento a respeito da origem do Teorema Chinês do resto, entender o
teorema e expandi-lo para n termos; apresentar alguns resultados e demonstrações
para o melhor entendimento; e, além disso, dar exemplos e aplicações na área de
grupos.
4
3. Origem
O teorema teve uma de suas primeiras aparições em “Manual de aritmética do mestre
Sun”, um livro chinês que data de 287 d.C. a 473 d.C.. Ele foi desenvolvido
simultaneamente por gregos e chineses com o intuito de resolver alguns problemas
relativos à astronomia.
História Lírica
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.
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, é 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.
5
4. Teorema Chinês do Resto
4.1 Prova para 2 equações
Primeiro veremos que existe pelo menos uma solução. Um inteiro x satisfaz o sistema
(1) se e somente se existem inteiros 𝑦1 e 𝑦2 tais que
𝑥 = 𝑚1 𝑦1 + 𝑎1 (3)
𝑥 = 𝑚2 𝑦2 + 𝑎2 (4)
Subtraindo as duas equações e reordenando temos 𝑚1 𝑦1 − 𝑚2 𝑦2 = 𝑎2 − 𝑎1 . (5)
Agora, como mdc(𝑚1 , 𝑚2 ) = 1, sabemos [já foi explicado antes] que a equação (5)
possui alguma solução (𝑦1 , 𝑦2 ) ∈ 𝑍 2 . Fixe tal solução e defina x = 𝑥0 pela equação (3).
Então usando (5) vemos que também vale a equação (4). Portanto este x = 𝑥0 é uma
solução do sistema (1).
Uma vez encontrada uma solução 𝑥0 , vejamos que qualquer x ≡ 𝑥0 mod 𝑚1 𝑚2 é
solução: de fato x = 𝑥0 + k𝑚1 𝑚2 implica x ≡ 𝑥0 mod 𝑚1 e x ≡ x0 mod 𝑚2 .
Por outro lado, veremos que todas as soluções são dessa forma. Suponha x solução
do sistema (1). Como 𝑥1 também é solução, temos que y = x−𝑥0 satisfaz.
y ≡ 𝑎1 − 𝑎1 ≡ 0 mod 𝑚1 (6)
y ≡ 𝑎2 − 𝑎2 ≡ 0 mod m2 (7)
Por (6), m1 divide y, isto é, existe ℓ tal que y = ℓm1. Por (7), 𝑚2 divide y = ℓ𝑚1 . Como
𝑚1 e 𝑚2 são primos entre si, 𝑚2 divide ℓ, isto é, existe k tal que ℓ = k𝑚2 .
Portanto y = k𝑚1 𝑚2 ≡ 0 mod 𝑚1 𝑚2, ou seja, x ≡ x0 mod 𝑚1 𝑚2, como queríamos
provar.
4.2 Teorema Chinês do Resto (versão forte) Enunciado
Sejam 𝑚1 ,. . . , 𝑚𝑘 inteiros ≥ 2 dois a dois primos entre si (isto é, mdc(𝑚𝑖 , 𝑚𝑗 ) = 1
sempre que i≠ 𝑗). Sejam 𝑎1 , . . . , 𝑎𝑘 inteiros quaisquer. Então o sistema
𝑥 ≡ 𝑎1 𝑚𝑜𝑑 𝑚1
𝑥
{ ≡ 𝑎2 𝑚𝑜𝑑 𝑚2 ⋯ (8)
𝑥 ≡ 𝑎𝑘 𝑚𝑜𝑑 𝑚𝑘
Possui uma solução x = 𝑥0 . Além disso, um inteiro x é solução do sistema se e
somente se x ≡ 𝑥0 mod 𝑚1 · · ·𝑚𝑘 .
6
4.3 Demonstração do Teorema Chinês do Resto (versão forte)
A prova é por indução no número k ≥ 2 de equações. Já vimos que o teorema vale
para 2 equações. Agora fixe k > 2 e suponha que o teorema vale para k − 1 equações.
Dados 𝑚1 , . . . , 𝑚𝑘 dois a dois primos entre si, e 𝑎1 , . . . , 𝑎𝑘 quaisquer, considere o
sistema formado apenas pelas k − 1 primeiras equações em (8). Pela hipótese de
indução, existe um b tal que este subsistema é equivalente a uma única equação, a
saber,
x ≡ b mod M, onde M = 𝑚1 · · · 𝑚𝑘−1 .
Portanto o sistema inteiro (8) é equivalente a um sistema com duas equações:
𝑥 ≡ 𝑏 𝑚𝑜𝑑 𝑀
{
𝑥 ≡ 𝑎𝑘 𝑚𝑜𝑑 𝑚𝑘
Notando que M e 𝑚𝑘 são primos entre si, e usando que o teorema vale para duas
equações, temos que existe solução 𝑥0 . Além disso, x é solução se e somente se
x ≡ 𝑥0 módulo M𝑚𝑘 = 𝑚1 . . . 𝑚𝑘−1 𝑚𝑘 , como queríamos demonstrar.
4.4 Exemplo
Ao tentar formar grupos de trabalho numa turma, conclui-se que se os grupos tiverem
3 elementos ficam dois alunos de fora, se tiverem quatro fica 1 de fora, mas que se
consegue formar grupos de 5 elementos desde que o professor faça parte de um
deles. Quantos alunos terá a turma?
Resolução: o problema corresponde à resolução do sistema de congruências
𝑥 ≡ 2 𝑚𝑜𝑑 3
{𝑥 ≡ 1 𝑚𝑜𝑑 4
𝑥 ≡ 4 𝑚𝑜𝑑 5
Como os módulos das congruências são primos dois a dois, o Teorema Chinês dos
Restos garante a existência de uma solução única mod 120 (e é de esperar que o
número de alunos de uma turma seja inferior a 120).
A primeira equação implica x = 2 + 3k;
Substituindo na segunda ficamos com 3k ≡ −1 mod 4 ⇔ k ≡ 1 mod 4 e portanto k = 1 +
4j, x = 2 + 3(1 + 4j) = 5 + 12j
Substituindo na última equação 12j + 5 ≡ 4 mod 5 ⇔ 2j ≡ 4 mod 5 ⇔ j ≡ 2 mod 5 ou
seja j = 2 + 5t e portanto x = 5 + 12(2 + 5t) = 29 + 120t
7
5. Aplicação em grupos
5.1 Produtos cartesianos em Z.
Considere m,n ∈ N={1,2,...}
Z= (Z,+)= grupo, 𝑍𝑚 𝑥𝑍𝑛 = grupo como produto
ɸ: 𝑍 → 𝑍𝑚 𝑥𝑍𝑛
ɸ
z→ (𝑧̅𝑚𝑜𝑑 𝑚 , 𝑧̅ 𝑚𝑜𝑑 𝑛)
Seja ɸHomeomorfismo de grupo.
ɸ(𝑧 + 𝑤) = ɸ(𝑧) + ɸ(𝑤)
5.2 Exemplo 1
ɸ: 𝑍 → 𝑍2 𝑥𝑍3
7 → (7̅, 7̅) = (1,1) // 8 → (8̅, 8̅) = (0,2)
Contradomínio:
CD= {(0,0), (0,1),(0,2),(1,0),(1,1),(1,2)}
∃ 𝑧 ∈ 𝑍 𝑡𝑎𝑙 𝑞𝑢𝑒 𝑧 = (𝑎, 𝑏) ∀ 𝑎 ∈ 𝑍2 𝑒 ∀𝑏 ∈ 𝑍3 ?
ou seja, nossa pergunta aqui é se nossa ɸ é sobrejetora. Para isso devemos ser
capazes de resolver o sistema:
𝑧 ≡ 𝑎 𝑚𝑜𝑑 2
,
{
𝑧 ≡ 𝑏 𝑚𝑜𝑑 3
Como vimos, Garantimos que existe solução devido ao Teorema Chinês do resto, pois
mdc(2,3)=1.
Logo nesse caso temos ɸ é sobrejetora.
5.3 Exemplo 2
ɸ: 𝑍 → 𝑍2 𝑥𝑍4
7 → (7̅, 7̅) = (1,3) // 5 → (5̅, 5̅) = (1,1)
Contradomínio:
CD={(0,0), (0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(1,3)}
ɸ é sobrejetora?
Aqui, não podemos utilizar o Teorema chinês do resto, pois mdc(2,4) = 2.
É fácil notar que existem alguns pontos do contradomínio inalcançáveis por ɸ. Como
por exemplo, (0,1).
𝑧 ≡ 0 𝑚𝑜𝑑 2
{
𝑧 ≡ 1 𝑚𝑜𝑑 4
Esse sistema é impossível de ser resolvido uma vez que z = 2k, a seguir substituindo
na segunda, 2k≡ 1 𝑚𝑜𝑑 4, que é impossível de ser resolvido para k∈ 𝑍.
8
5.4 Casos Gerais
ɸ: 𝑍 → 𝑍𝑚 𝑥𝑍𝑛
Como visto nos exemplos, para que ɸ seja sobrejetora teremos que resolver esse
sistema:
𝑧 ≡ 𝑎 𝑚𝑜𝑑 𝑚
{
𝑧 ≡ 𝑏 𝑚𝑜𝑑 𝑛
Que pelo que aprendemos no capitulo anterior só tem garantia de solução caso
mdc(n,m) =1.
O caso de ɸ ser injetora (1-1) não foi avaliado pelo simples motivo de Z ter infinitos
elementos enquanto 𝑍𝑚 𝑥𝑍𝑛 tem 𝑚. 𝑛 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜𝑠, logo não sendo injetora.
Num caso mais geral como, por exemplo:
ɸ: 𝑍 → 𝑍𝑖1 𝑥𝑍𝑖2 𝑥 … 𝑥𝑍𝑖𝑛 , com 𝑖𝑘 ∈ 𝑍, ∀ 𝑘 ∈ {1, … , 𝑛}.
Aqui claramente devemos utilizar a versão forte do teorema para comprovar se vale ou
não a sobrejetividade.
Propomos ao leitor mostrar que:
a) ɸ: 𝑍 → 𝑍2 𝑥𝑍3 𝑥𝑍5 é sobrejetor, apresentando o contradomínio e a proposta de
resolução
b) ɸ: 𝑍 → 𝑍4 𝑥𝑍5 𝑥𝑍6 não é sobrejetor, apresentando elemento do Contradomínio que
não terá correspondente.
9
6. Conclusão
O Teorema Chinês do Resto tem uma vasta gama de aplicações. Aqui apenas
mostramos um pequeno relance de onde ele pode ser utilizado.
Aqui conseguimos demonstrá-lo e aplica-lo de maneira ínfima. Sugere-se ao leitor que
pesquise sobre o tema para se aprofundar na área.
10
7. Referências
http://www.mat.puc-rio.br/~jairo/MAT1310/20092/TCR.pdf
http://www.ime.unicamp.br/~ftorres/ENSINO/MONOGRAFIAS/AG_M1_FM_2013.pdf
http://www.ime.unicamp.br/~ftorres/ENSINO/MONOGRAFIAS/GB_M1_FM_2013.pdf
http://www.ic.unicamp.br/~rdahab/cursos/MO829MC932/Welcome_files/slides/algTeoNum_II.pdf
http://www.math.ist.utl.pt/~pmartins/EMF/Exerc/Exercsolv2.pdf
http://www.matmidia.mat.puc-rio.br/tomlew/MAT1310_11.1/TCR.pdf
https://anotacoesdeaula.wordpress.com/2014/08/29/bc1405-congruencias-lineares-eteorema-chines-do-resto/
11