Teorema chinês do resto

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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[editar | editar código-fonte]

Dizem que o Teorema Chinês dos Restos surgiu com os antigos generais, chineses, pois esses 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.

Digamos, que 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.( resposta dessa questão no exemplo "d")

Enunciado[editar | editar código-fonte]

Se mk é um inteiro positivo e mdc(mi,mj) = 1 (i ≠ j)(números primos entre si) então o sistema de congruências lineares:

x ≡ a1 (mod.m1)

x ≡ a2 (mod.m2)

x ≡ a3 (mod.m3)

x ≡ a4 (mod.m4)

x ≡ a5 (mod.m5)

x ≡ a6 (mod.m6)

...

x ≡ an-1 (mod.mn-1)

x ≡ an (mod.mn)

Tem uma única solução: x ≡ X (mod.m) m=m1m2m3...mn-1 mn

O valor de X pode ser encontrado utilizando-se o Teorema do Resto Chinês:

X= a1.M1.x1+ a2.M2.x2+ a3.M3.x3+ a4.M4.x4+ ...+ an.Mn.xn

Ma é o produto de todos os mk com exceção de ma (Exemplo: M1=m2.m3.....mn)

xa é o número que torna Ma.xa≡1(mod ma)

Demonstração[editar | editar código-fonte]

Veremos como calcular um inteiro que satisfaz simultaneamente a várias congruências com módulos distintos: o chamado algoritmo chinês do resto.

1.1 Algoritmo Chinês do Resto

 Começamos analisando um exemplo bastante simples.

 Considere o seguinte problema: determine o menor inteiro positivo que deixa resto 1 na divisão por 3 e resto 2 na divisão por 5.

Note que este exemplo é simples o suficiente para que possamos resolvê-lo “de cabeça”. Contudo, nas aplicações ao RSA, encontraremos sistemas muito maiores, que só conseguiremos resolver procedendo de maneira sistemática, que é outra forma de dizer usando um algoritmo. Começaremos descrevendo a aplicação do algoritmo geral ao exemplo acima.

Chamando de n o inteiro que buscamos, podemos escrever as equações correspondentes à divisão de n por 3 e 5 na forma 

n = 3q1 + 1,

n = 5q2 + 2.

À primeira vista a reformulação foi ótima; afinal, sobrou apenas uma variável: o que podia ser melhor? O problema é como usar as congruências para determinar o inteiro desejado. Geralmente, quando temos mais de uma equação para resolver, tentamos combiná- las para achar a resposta desejada. Entretanto, estas duas congruências têm módulos diferentes e, portanto, não podemos combiná-las diretamente. O que fazer?

A saída é usar uma estratégia híbrida: substituiremos n = 5q2 +2 não na equação n = 3 · q1 + 1, mas sim na primeira congruência, isto é, em n ≡ 1 (mod 3). Efetuando a substituição, obtemos

5q2 + 2 ≡ 1 (mod 3)

Acontece que 5 ≡ 2 (mod 3), de forma que a congruência pode ser reescrita na forma

2q2 + 2 ≡ 1 (mod 3)

 Subtraindo 2 dos dois lados da congruência, chegamos a                                                                    2q2 ≡ −1 (mod 3);

ou ainda a

2q2 ≡ 2 (mod 3),

já que −1 ≡ 2 (mod 3). Como 2 é inversível módulo 3, podemos cancelá-lo na congruência acima pelo teorema 2, o que nos dá

q2 ≡ 1 (mod 3).

Em outras palavras, q2 deixa resto 1 na divisão por 3, de modo que podemos escrevê-lo como

q2 = 3q3 + 1,

onde q3 corresponde ao quociente desta divisão.

Voltando ao problema original, temos, além das equações

n = 3q1 + 1,

n = 5q2 + 2,

originalmente obtidas, uma nova equação

q2 = 3q3 + 1,

que explicita q2, ainda que seja ao preço de introduzir uma nova variável. Mas isto nos permite substituir o valor de q2 diretamente na segunda das duas equações originalmente obtidas, o que nos dá

n = 5q2 + 2 = 5(3q3 + 1) + 2.

Fazendo as contas,

n = 15q3 + 7.

E daí? Tínhamos duas equações. Fizemos uma peripécia usando congruências. Chegamos a uma nova equação em tudo semelhante às originais. Grande coisa!

Se estes pensamentos lhe passaram pela cabeça, então prepare-se para uma surpresa. O que acontece se dividirmos 15q3 + 7 por 3? Para começar, 15 = 3 · 5, de forma que

15q3 + 7 = 3 · 5q3 + 7.

Se 7 fosse menor que 3, seria o resto desta divisão, como 7 ≥ 3, precisamos escrevê-lo na forma

7 = 3 · 2 + 1.

Combinando as duas equações e pondo 3 em evidência, obtemos

15q3 + 7 = 3 · (5q3 + 2) + 1;

logo 15q3+7 deixa resto 1 na divisão por 3, exatamente o que queríamos que acontecesse com o n a ser determinado em nosso problema. Com uma vantagem: isto acontece qualquer que seja o valor escolhido para q3! 

Passando à divisão por 5, temos que

15q3 + 7 = 5 · 3q3 + 5 + 2 = 5(3q3 + 1) + 2;

de forma que 15q3 + 7 deixa resto 2 na divisão por 5, satisfazendo, mais uma vez, ao que foi pedido no problema. Isto sugere que devemos considerar a solução como sendo n = 15q3 + 7. Observe, contudo, que o que obtivemos não foi uma solução, mas sim uma família de soluções. De fato, obteremos uma solução diferente para cada valor inteiro que escolhermos para q3, como ilustrado na tabela 1.1.

q3

15q3 + 7

-3

-38

-2

-23

-1

-8

0

7

1

22

2

37

3

52

Tabela 1.1  Tabelando n = 15q3 + 7

Dito isto, fica difícil não perguntar se todas as possíveis soluções deste problema podem ser obtidas da fórmula n = 15q3 + 7 simplesmente escolhendo um valor adequado para q3. A resposta é sim, mas para entender porque você terá que esperar até a seção 1.2.

Relendo o problema, verificamos que ainda há uma condição a ser satisfeita: queremos o menor n positivo que satisfaz as duas condições sobre os restos. Entretanto, como mostra a tabela 4.1:

• se q3 < 0, então 15q3 + 7 < 0;

 • se q3 > 0, então 15q3 + 7 > 7;

de modo que o valor desejado é mesmo n = 7.

 Antes de passar a um novo exemplo, vamos refazer a verificação de que n = 15q3 + 7 nos dá uma família de soluções para a equação. Só que desta vez usaremos congruências. Da igualdade n = 15q3 + 7 obtemos a congruência

 n ≡ 15q3 + 7 ≡ 1 (mod 3);

pois 15 ≡ 0 (mod 3) e 7 ≡ 1 (mod 3). Da forma semelhante, n ≡ 15q3 + 7 ≡ 2 (mod 5). Estas verificações são muito mais diretas e automáticas e, daqui por diante, serão usadas como nossa maneira-padrão de testar a correção de nossas soluções.

Um Exemplo Astronômico

 Desta vez o problema trata de tempos e não de restos:

Três satélites passarão sobre o Rio esta noite. O primeiro à 1 hora da madrugada, o segundo às 4 horas e o terceiro às 8 horas da manhã. Cada satélite tem um período diferente. O primeiro leva 13 horas para completar uma volta em torno da Terra, o segundo 15 horas e o terceiro 19 horas. Determine quantas horas decorrerão, a partir da meia noite, até que os três satélites passem ao mesmo tempo sobre o Rio.

Podemos formular o problema de maneira muito semelhante à que adotamos na seção anterior, basta lembrar nossa interpretação do módulo como o período de um movimento que se repete a intervalos regulares. Neste caso, o movimento é o dos satélites que giram em torno da Terra.

 Chamaremos de x o número de horas, contadas a partir da meia noite de hoje, quando os três satélites passarão juntos sobre o Rio. O primeiro satélite passa sobre o Rio a cada 13 horas, a contar da 1 da madrugada. Logo precisamos ter que x = 1 + 13n1, para algum inteiro positivo n1, que representa o número de voltas que o satélite 1 tem que dar em torno da Terra antes que passe junto com os dois outros satélites.

As equações correspondentes aos outros dois satélites são

x = 4 + 15n2 e x = 8 + 19n3;

onde n2 e n3 representam o número de voltas que os satélites 2 e 3 darão antes dos três passarem juntos.

Como fizemos para o problema anterior, podemos reformular estas equações em termos de congruências, o que nos dá

x ≡ 1 (mod 13),                                          (1.1.1)

x ≡ 4 (mod 15),

x ≡ 8 (mod 19).

Desta vez temos três equações, ao contrário das duas do problema anterior, mas não vamos nos deixar intimidar. Já que o método que desenvolvemos só permite resolver duas equações de cada vez, começaremos com as duas últimas. Tomando a última equação e substituindo-a na penúltima congruência, obtemos

8 + 19n3 ≡ 4 (mod 15); que equivale a 19n3 ≡ −4 (mod 15).

Como 19 ≡ 4 (mod 15), isto nos dá

4n3 ≡ −4 (mod 15).

Como 4 é inversível módulo 15 pelo teorema 3, podemos cancelá-lo, de modo que

n3 ≡ −1 ≡ 14 (mod 15).

Assim, n3 = 14+15n4, para algum inteiro positivo n4. Mas, segundo a terceira equação, x = 8 + 19n3. Combinando estas duas expressões

x = 8 + 19(14 + 15n4) = 274 + 285n4.

O que isto representa? Certamente não a solução do problema, já que sequer usamos as condições impostas pelo primeiro satélite. Entretanto, como é fácil verificar usando congruências,

x = 274 + 285n4

nos dá uma solução das duas últimas equações. Isto significa que esta família de soluções deve corresponder aos tempos nos quais os satélites 2 e 3 passam juntos sobre o Rio.

E quanto ao satélite 1? Para incluir na solução a informação referente ao primeiro satélite, basta encontrar as soluções da forma x = 274 + 285n4 (isto é, as soluções comuns aos satélites 2 e 3) que, além disso, satisfazem a congruência x ≡ 1 (mod 13), relativa ao primeiro satélite. Efetuando a substituição,

274 + 285n4 ≡ 1 (mod 13);

que depois da redução módulo 13 nos dá

1 + 12n4 ≡ 1 (mod 13).

Logo 12n4 ≡ 0 (mod 13) e, como 12 é inversível módulo 13, concluí- mos que n4 = 13n5. Desta forma, a solução final será

x = 274 + 285n4 = 274 + 285(13n5) = 274 + 3705n5,

como é fácil verificar substituindo esta fórmula para x nas congruências (1.1.1).

Resta-nos explicitar o que esta solução nos diz sobre os satélites. Em primeiro lugar, como é fácil verificar, 274 é o menor inteiro positivo que satisfaz as congruências (1.1.1). Portanto, os satélites passam juntos sobre o céu do Rio pela primeira vez 274 horas depois da meia noite de hoje. Isto equivale a 11 dias e 10 horas. Mas isto não é tudo. Afinal, não importa qual seja o valor de n5, a fórmula 274 + 3 705n5 nos dá uma solução do problema. Portanto, depois de passar juntos uma vez sobre o Rio 274 horas depois da zero hora de hoje, os satélites passarão juntos novamente a cada 3 705 horas; isto é, a cada 154 dias e 9 horas.

Na próxima seção faremos uma análise detalhada do método acima. Observe que nossa estratégia consistiu em dividir a solução do sistema (1.1.1) de 3 equações em duas etapas. Primeiro achamos uma solução comum às duas últimas congruências, que foi x = 274 + 285n4. Em seguida, buscamos as soluções comuns às duas últimas congruências que também satisfazem à primeira. Como x = 274 + 285n4 corresponde à congruência,

x ≡ 274 (mod 285),

substituí-la na primeira congruência equivale a resolver o sistema

x ≡ 1 (mod 13),

                                                                        x ≡ 274 (mod 285).

Uma outra maneira de expressar isto consiste em dizer que a solução de um sistema de muitas equações é obtida através da solução de vários sistemas de duas equações cada. Por isso, na seção 1.2 é su- ficiente analisar o algoritmo correspondente à solução de um sistema de duas equações.

1.2 O Teorema Chinês do Resto

O procedimento de substituição que utilizamos nas seções anteriores para resolver sistemas de congruências é conhecido como algoritmo chinês do resto, porque um dos primeiros lugares em que aparece é o livro Manual de aritmética do mestre Sun, escrito entre 287 d.C. e 473 d.C. Entretanto, o mesmo resultado é mencionado na Aritmética de Nicômaco de Gerasa, escrita por volta de 100 d.C. O teorema desta seção apenas sistematiza o resultado final do método utilizado nos problemas das seções anteriores.

Considere o sistema

 x ≡ a (mod m),                                            (1.2.1)

x ≡ b (mod n),

onde m e n são inteiros positivos distintos e digamos que o número inteiro x0 é uma solução desta congruência. Isto significa que x0 satisfaz a ambas as congruências:

x0 ≡ a (mod m),

 x0 ≡ b (mod n).

Como os módulos são diferentes, só podemos combinar as duas congruências se convertermos uma delas em uma igualdade de inteiros. Fazendo isto com a primeira equação, verificamos que

x0 = a + m · k, onde k é um inteiro qualquer, (1.2.2)

de forma que podemos concluir que

 a + mk ≡ b (mod n)

ou ainda

 mk ≡ (b − a) (mod n). (1.2.3)

Supondo que m e n sejam primos entre si, concluímos pelo teorema 3 que m é inversível módulo n. Digamos que m′ é o inverso de m módulo n. Multiplicando (1.2.3) por m′ , obtemos k ≡ m′ (b − a) (mod n).

Em outras palavras,

 k = m′ (b − a) + n · t para algum inteiro t.

Substituindo esta expressão para k em (1.2.2), vemos que

x0 = a + m(m′ (b − a) + n · t).

Resumindo, provamos que se x0 é uma solução de (1.2.1), então

x0 = a + m · (m′ · (b − a) + n · t). (1.2.4)

Mas é fácil ver que, qualquer que seja o inteiro t, uma expressão da forma a + m(m′ (b − a) + n · t) tem que ser solução do sistema (1.2.1). Para começo de conversa, a+m(m′ (b−a)+n·t) é claramente congruente a a módulo m. Por outro lado,

a + m · (m′ · (b − a) + n · t) ≡ a + m · m′ · (b − a) (mod n).

Como, mm′ ≡ 1 (mod n) por construção, então

a + m · (m′ · (b − a) + n · t) ≡ a + 1 · (b − a) ≡ b (mod n);

comprovando que a+ m ·(m′ ·(b−a)+n ·t) é mesmo uma solução do sistema (1.2.1). Podemos resumir o que fizemos no seguinte teorema.

Teorema Chinês do Resto.

 Sejam m e n inteiros positivos primos entre si. Se a e b são inteiros quaisquer, então o sistema

x ≡ a (mod m),

x ≡ b (mod n),

sempre tem solução e qualquer uma de suas soluções pode ser escrita na forma

a + m · (m′ · (b − a) + n · t),

onde t é um inteiro qualquer e m′ é o inverso de m módulo n.

Cuidado para não se confundir e achar que mm′ = 1, já que m e m′ são inversos um do outro. De fato eles são inversos, mas somente módulo n, de modo que a relação correta é mm′ ≡ 1 (mod n); que não simplifica a fórmula de nenhuma maneira significativa.

Quando os Módulos Não são Primos Entre Si

Apesar de termos obtido uma fórmula exata para a solução de sistemas de duas congruências, isto foi feito ao preço de uma hipótese bastante forte, a de que os módulos são primos entre si. Será que a fórmula continua verdadeira mesmo se esta hipótese não se verifica? Se você reler o argumento usado para provar a fórmula verá que precisamos que os módulos fossem primos entre si em apenas um ponto: para inverter m na congruência mk ≡ (b−a) (mod n) e assim determinar o valor de k. Isto significa que a estratégia usada acima não funcionaria se m e n não fossem primos entre si. Mas será que não há outra estratégia possível neste caso? A resposta é sim... e não. Vejamos por quê?

 Para isto analisaremos dois exemplos muito semelhantes.

O primeiro deles é

x ≡ 3 (mod 4),

 x ≡ 1 (mod 6),

e o segundo é

x ≡ 2 (mod 4),

 x ≡ 1 (mod 6).

Note que a única diferença entre eles está no coeficiente à direita da primeira congruência que, no primeiro exemplo é 3 e no segundo é 2. Procederemos exatamente como antes. Portanto, começamos por tirar o valor de x da segunda congruência, que nos dá

x = 1 + 6y para algum inteiro y. (1.2.5)

Substituindo isto na primeira, obtemos no primeiro exemplo

6y ≡ 2 (mod 4);        (1.2.6)

e no segundo

 6y ≡ 1 (mod 4).        (1.2.7)

Chegados a este ponto, não podemos prosseguir, porque 6 e 4 têm 2

como fator comum, de modo que 6 não é inversível módulo 4. Contudo, convertendo (1.2.6) para uma igualdade de inteiros, vemos que

 6y = 2 + 4z, para algum inteiro z.

Acontece que 2 divide cada uma das parcelas desta equação. Efetuando a divisão, obtemos

 3y = 1 + 2z.

Convertendo esta igualdade em uma congruência, ficamos com

3y ≡ 1 (mod 2);

que, como 3 ≡ 1 (mod 2), nos dá

y ≡ 1 (mod 2);

isto é

 y = 1 + 2t para algum inteiro t.

Substituindo em (1.2.5),

 x = 1 + 6(1 + 2t) = 7 + 12t,

que é a solução do sistema, como podemos facilmente verificar por substituição. Passando agora ao outro sistema, precisamos resolver a congruência (1.2.7). Convertendo-a em uma igualdade de inteiros, temos

6y = 1 + 4z, para algum inteiro z.

Contudo, desta vez o divisor comum dos três coeficientes da equação é 1. Rearrumando a equação anterior, obtemos

 6y − 4z = 1

que, como 2 divide 6 e 4, pode ser reescrita na forma

 2(3y − 2z) = 1.        (1.2.8)

Entretanto, se existissem números inteiros y e z que satisfizessem esta equação, teríamos que 1 é múltiplo de 2; o que é evidentemente falso. Mas (1.2.8) é consequência de (1.2.7), de modo que esta última também não pode ter solução! Resumindo, estes exemplos nos mostram que, quando os módulos não são primos entre si, o sistema pode ou não ter solução, dependendo dos coeficientes constantes que aparecem nas congruências. Será que podemos prever isto só de olhar para os coeficientes? A resposta é sim e é enunciada abaixo. Provar que está correta fica como desafio para você.

Desafio 4. Considere o sistema de congruências

x ≡ a (mod m),

 x ≡ b (mod n).

Suponha que o máximo divisor comum entre m e n é d. Aplique o procedimento de substituição do algoritmo chinês a este sistema para mostrar que:

(a)    se d divide b − a então o sistema tem solução;

(b)   se d “não” divide b − a então o sistema “não” tem solução.

Exemplo[editar | editar código-fonte]

Resolver as seguintes congruências (encontrar todas as soluções ou justificar que não existem):

a)      5x ≡ 3 mod 11;

R-  (5, 11) = 1 e portanto existe solução única; como 9 × 5 ≡ 1 mod 11  concluímos que a solução é x ≡ 9 × 3 ≡ 5 mod 11.

b) 12x ≡ 2 mod 33;

R - Neste caso (12, 33) = 3 que não divide 2 pelo que não há solução

c) 9x ≡ 21 mod 12

R - (9, 12) = 3 que divide 21 e portanto sabemos que existem 3 soluções nãoo congruentes entre si; podemos encontrar uma solução notando que

21 = 7 × 3 = 7(12 − 9) ≡ −7 × 9 mod 12

pelo que x0 ≡ −7 ≡ 5 mod 12 é solução; as outras podem obter-se somando múltiplos k(12/3) com 1 ≤ k < 3, ou seja

x1 ≡ x0 + 4 ≡ 9 mod 12; x2 ≡ x1 + 4 ≡ 1 mod 12

Nota: a solução x2 ≡ 1 é obvia se notarmos primeiro que 21 ≡ 9 mod 12.

Outro método de resolução passa por resolver primeiro a congruência 3x ≡ 7 mod 4 (dividindo tudo por 3) que tem a solução x ≡ 1 mod 4, e usar o facto de que um inteiro x satisfaz a congruência inicial 9x ≡ 21 mod 12 se e só se satisfaz está última; portanto as soluções da congruência inicial são as classes de congruência mod 12 questão contidas na classe 1 mod 4, ou seja 1, 5, 9 mod 12.

d)Digamos, que 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?

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

x ≡ 3 (mod.5)

x ≡ 3 (mod.6)

x ≡ 1 (mod.7)

x ≡ 0 (mod.11)

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:

a1 = 3 , a2 = 3 , a3 = 1 , a4 = 0

m1 =5 m2=6 m3=7 m4=11

M = 5.6.7.11 = 2310

M1 = 2310/5 = 462 ; M2 = 2310/6 = 385 ; M3 = 2310/7 = 330 ; M4 = 2310/11 =210

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

y1 é tal que 462.y1 ≡ 1 (mod.5)

Mas 462 deixa resto 2 quando dividido por 5, isto quer dizer que 462 ≡ 2(mod.5) , substituindo acima temos que

2.y1 ≡ 1 (mod.5)

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

Então , y1 ≡ 3 (mod.5)

Repetindo o processo, temos

y2≡ 1 (mod.6)

y3≡ 1 (mod.7)

y4 ≡ 1 (mod.11)

Pronto, agora basta jogar tudo na fórmula:

x ≡ 3.462.3 + 3.385.1 + 1.330.1 + 0.210.1 (mod.2310)

x ≡ 4158 + 1155 + 330 (mod.2310)

x ≡ 5643 (mod. 2310)

Portanto

x ≡ 1023 (mod. 2310) que é equivalente a x ≡ 1023 + 2310q  para todo q natural.

Mas queremos x maior que 0 e menor que 1200, o que implica que x = 1023

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

e)x ≡ 3 (mod.5)

x ≡ 5 (mod.13)

x ≡ 7 (mod.29)

x ≡ 1 (mod.41)

X = 3.13.29.41.x1 + 5.5.29.41.x2 + 7.5.13.41.x3 + 1.5.13.29.x4

x1.13.29.41≡1(mod.5) → x1.(-2)(-1)(1)≡x1.2≡1(mod.5)

x1≡3(mod.5)

x2.5.29.41≡1(mod.13) → x2.5.3.2≡1(mod.13)→ x2.4≡1(mod.13)

x2≡10(mod. 13)

x3.5.13.41≡1(mod.29) →x3.5.13.17≡1(mod.29)&rarr x3.3≡1(mod.29)

x3≡-10(mod.29)

x4.5.13.29≡1(mod.41) →x4.5.13.(-12) ≡1(mod.41)→x4.(-1) ≡1(mod.41)

x4≡-1(mod.41)

X=3.13.29.41.3 + 5.5.29.41.10 + 7.5.13.41.(-10) + 1.5.13.29.(-1)

X=139113 + 297250 – 186550 -1885

X=247928

x≡X≡247928(mod.5.13.29.41) → x≡16073(mod.77285)

Ligações externas[editar | editar código-fonte]

Referências Bibliográficas[editar | editar código-fonte]