Resumo - Congruência

Ir em baixo

Resumo - Congruência

Mensagem por Luís Eduardo em Seg Ago 15, 2011 9:36 pm



Última edição por Admin em Seg Ago 15, 2011 9:38 pm, editado 1 vez(es)
avatar
Luís Eduardo
Admin
Admin

Mensagens : 288
Data de inscrição : 09/08/2011

Ver perfil do usuário http://momentum21.forumeiros.com

Voltar ao Topo Ir em baixo

Re: Resumo - Congruência

Mensagem por Luís Eduardo em Seg Ago 15, 2011 9:37 pm

Olá pessoal,
Só queria complementar com alguns teoremas que podem ajudar também:

Teorema de Wilson

Se p é um primo, então (p - 1)! ≡ -1 (mod p)


Exemplo de aplicação: http://pir2.forumeiros.com/t15617-resto-da-divisao

Pequeno Teorema de Fermat

Seja p primo. Se p não divide a, então, a^(p - 1) ≡ 1 (mod p)

Esse teorema é de longe um dos mais importantes, mas não é preciso entrar em detalhes já que ele foi devidamente explicado no material do rumo ao ita.

OBS: Não se esqueça que: Se p é um primo e a é um inteiro positivo, então a^p ≡ a (mod p)


Teorema de Euler
Se n é um inteiro positivo e a um inteiro com (a,n) = 1, então:




Quando eu li pela primeira vez essa definição eu não entendi muita coisa, mas depois pesquisei mais e entendi melhor. Tentarei explicar de forma simples para todos que nunca tiveram contato com isso possam entender.

Isso é como se fosse uma generalização para isso: a^p ≡ a (mod p ).

Aquele símbolo no expoente é função totiente ou função phi ( φ ).

φ( n ) representa a quantidade de números primos anteriores ao número inteiro e positivo n.
Exemplo: φ( 8 ) = 4, uma vez que 1, 3, 5 e 7 são co-primos de 8.

Assim, a^(φ( 8 )) ≡ 1 (mod 8 )
a^4 ≡ 1 (mod 8 )

Se a = 3, 3^4 ≡ 1 (mod 8 )



Teorema de Resto Chinês
Esse é um dos teoremas que eu considero mais útil.

Se (ai, mi) = 1, (mi, mj) = 1 para i # j e ci inteiro, então o sistema

a1x ≡ c1 (mod m1)
a2x ≡ c2 (mod m2)
...
arx ≡ cr

possui solução e "a" solução é única módulo "m", onde m = m1.m2...mr

Eu não sou a melhor pessoa para explicar esse teorema, pois acredito que uma boa lida pela internet pode ser melhor para saber mais a respeito da teoria e a demonstração.
Entretanto, eu posso tentar mostrar como o wikipédia explica:

x ≡ a1 (mod.m1)
x ≡ a2 (mod.m2)
x ≡ a3 (mod.m3)

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

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)

Isso aí ajuda para entender o que é o teorema, mas vamos à prática ?


Resolver o sistema de congruências abaixo:

x ≡ 1 (mod 5)
x ≡ 2 (mod 7)
x ≡ 3 (mod 11)

Resolução:

m1 = 5
m2 = 7
m3 = 11

m = 5.7.11

M1 = m/m1 = 7.11
M2 = m/m2 = 5.11
M3 = m/m3 = 5.7

Agora vamos tentar achar o "xa":

Ma.xa≡1(mod ma)
M1.x1 ≡1(mod m1)
7.11.x1 ≡1(mod 5)
22.x1 ≡1(mod 5)

22 = 4*5 + 2

2.x1 ≡1(mod 5)

Logo, x1 = 3, pois 3.2 = 6, e 6 - 1 é divisível por 5.

M2.x2 ≡1(mod m2)
5.11.x2 ≡1(mod 7)
x2 = 6

M3.x3 ≡1(mod m3)
5.7.x3≡1(mod 11)
x3 = 6


Agora é fica fácil:

x ≡ X (mod.m) m=m1m2m3...m(n-1) m(n)

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


X = 1.7.11.3 + 2.5.11.6 + 3.5.7.6
X = 366

x ≡ 366 (mod 385)


Logo,

366 é o número que divido por 5 deixa resto 1, dividido por 7 deixa resto 2, dividido por 3 deixa resto 11 ao mesmo tempo.

Como exercício deixo:

Resolva o seguinte sistema:

x ≡ 1 (mod 2)
x ≡ 2 (mod 3)
x ≡ 5 (mod 7)

Se não me engano a resposta para esse
gab:
Spoiler:
x ≡ 257 (mod 42)
Então, x ≡ 5 (mod 42)



Pois é, galera.
É isso. Esses teoremas poderão ser úteis em diversas questões, até aquelas aparentemente simples.
Além de resolverem diversas questões.

As demonstrações eu deixo para que o amigo pesquise ou tente sozinho. Não se esqueçam de ler a respeito desses teoremas da internet. O wikipédia não é lá dos mais confiáveis, mas pode ser um local para compreender melhor esse assunto.

Não pense que vc nunca vai precisar deles, pois sempre aparece uma questão complicada que poderia facilmente ser resolvida pelos teoremas que aprendemos (principalmente a do resto chinês e de fermat).

Bons estudos,
Qualquer dúvida, sugestão, correção, complemento, crítica, dentre outros podem ficar livres para me mandar mensagens por MP.


Referências:

SANTOS, José Plínio de Oliveira, Introdução à Teoria dos Números, IMPA, Rio de Janeiro, 2010.
http://pt.wikipedia.org/wiki/Função_totiente_de_Euler
http://pt.wikipedia.org/wiki/Teorema_chinês_do_resto
http://pt.wikipedia.org/wiki/Teorema_de_Euler

avatar
Luís Eduardo
Admin
Admin

Mensagens : 288
Data de inscrição : 09/08/2011

Ver perfil do usuário http://momentum21.forumeiros.com

Voltar ao Topo Ir em baixo

Voltar ao Topo

- Tópicos similares

 
Permissão deste fórum:
Você não pode responder aos tópicos neste fórum