• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

PuPax

Resolução de Congruências

14 mensagens neste tópico

Boa noite pessoal,

Estou com uma dúvida na resolução de congruências lineares e se alguém pudesse dar uma ajudinha agradecia. =)

Ex.:

10x = 5 (mod 27)

1º Encontrar o mdc(10,27):

    27 = 10*2+7

    10 = 7*1+3

    7  = 3*2+1, logo o mdc(10,27)=1

2º Encontrar os valores de s e t onde, 1 = 10s+27t

    E para isto teremos de usar o Algoritmo de Euclides Estendido, o qual não consigo apanhar por nada!

Ex2.:

E no caso do mdc(a,:) != 1. Como se procede?

Cumprimentos,

David Miranda.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

2º Encontrar os valores de s e t onde, 1 = 10s+27t

para resolveres isto podes usar as divisoes sucessivas que usas-te para encontar o mdc.

Mas para resolver cogruencias lineares resolve-se, neste caso, a equaçao diofantina 10x+27y=5

Existem metodos pa resolver isto, o mais simples é usares as divisoes sucessivas que falei, ou seja:

1 = 10 *(-8) + 27*3

multiplicas tudo por 5:

5 = 10 * -8 *5 + 27 * 3 *5

e ja tens a soluçao do x

PS: Penso que nao me enganei :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Mas como é que consegues dizer logo que os valores sao aqueles? Não percebi...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A equação que tens que resolver, para a equação

ax=b (mod n)

é

mdc(a,n)=a r + n s

Para resolver essa equação, vais ter que aprender o Algoritmo de Euclides Estendido.

De notar que do lado esquerdo da equação não tens necessariamente 1. Isto responde à tua segunda questão.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu ai fiz um trukezito matematico que nao é muito simples de explicar...

eu fiz as divisoes sucessivas pa encontrar o mdc,obtive mais o menos o que fizeste em cima

27/10 que deu resto 7

depois 10/7 resto 3

7/3 resto 1

e 3/1 resto 0 (r = 0 termina)

portanto aqui sei que:

1= 7-(3*2) (=) (aqui obsrvas as divisoes e inverter o processo de divisao ou seja sabs aquele 3 = 10-7*1 e substituis ) 1 = 7-(10-7*1)*2) (=) (assim sucessivamente até) 1=3*27 +10*(-8). O importante é procurar manter sempre o 27 e 10 intacttos, ou seja, sem opera-los para os teres no fim

O ultimo é trivial apenas tem de mutilplicar por 5, nos casos em que nao é 1, tens que garantir mdc | b, sendo o b ax = b (mod n), se dividir so tens de encontrar o z tal q b=mdc*z. Este z é o que vais multiplicar (quando que multipliquei por 5).

Pa é o melhor q te consigo explicar  :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Mas tipo... quando substituis isto 1 = 7-(10-7*1)*2) só podes fazer operações com alguns numeros para chegares aquilo... Não?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Quais valores sao?

Atao baseando-nos no que o Rui disse o que queres resolver é

ax=b (mod n) é mdc(a,n)=a r + n s

Ou seja logo que tenhas o a e o n nas equaçoes ao aplicar o algoritmo tens de os preservar.

Em concreto nesse caso 1 = 7-(10-7*1)*2 tens de preservar o 10, resultando 1= 7-2*10 +2*7 (=) 1 = -2*10 +3*7

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Já apanhei...

Agora quando o mdc(a,:) é diferente de 1 como resolvo?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

(...) nos casos em que nao é 1, tens que garantir mdc | b, sendo o b ax = b (mod n), se dividir so tens de encontrar o z tal q b=mdc*z. Este z é o que vais multiplicar (quando que multipliquei por 5).

(...)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora