Fórum PiR2
Gostaria de reagir a esta mensagem? Crie uma conta em poucos cliques ou inicie sessão para continuar.

Teoria dos Números - Congruência: uma abordagem objetiva

+8
Agente Esteves
Dinheirow
willie123
luiseduardo
boris benjamim de paula
Jose Carlos
Adam Zunoeta
Euclides
12 participantes

Página 1 de 2 1, 2  Seguinte

Ir para baixo

Teoria dos Números - Congruência: uma abordagem objetiva Empty Teoria dos Números - Congruência: uma abordagem objetiva

Mensagem por Euclides Qui 02 Dez 2010, 22:30



Última edição por Euclides em Ter 26 Dez 2017, 23:09, editado 1 vez(es)

____________________________________________
In memoriam - Euclides faleceu na madrugada do dia 3 de Abril de 2018.
assinatura 1
Lembre-se de que os vestibulares têm provas de Português também! Habitue-se a escrever corretamente em qualquer circunstância!

O Universo das coisas que eu não sei é incomensuravelmente maior do que o pacotinho de coisas que eu penso que sei.
Euclides
Euclides
Fundador
 Fundador

Mensagens : 32508
Data de inscrição : 07/07/2009
Idade : 71
Localização : São Paulo - SP

Ir para o topo Ir para baixo

Teoria dos Números - Congruência: uma abordagem objetiva Empty Re: Teoria dos Números - Congruência: uma abordagem objetiva

Mensagem por Adam Zunoeta Qui 02 Dez 2010, 23:18

Muito bom o material vlw Euclides, vai ajudar bastante.
Very Happy
Adam Zunoeta
Adam Zunoeta
Monitor
Monitor

Mensagens : 4223
Data de inscrição : 24/08/2010
Idade : 32
Localização : Cuiabá

Ir para o topo Ir para baixo

Teoria dos Números - Congruência: uma abordagem objetiva Empty Re: Teoria dos Números - Congruência: uma abordagem objetiva

Mensagem por Jose Carlos Seg 06 Dez 2010, 16:41

Olá amigo, muito legal....


Um abraço.
Jose Carlos
Jose Carlos
Grande Mestre
Grande Mestre

Mensagens : 5551
Data de inscrição : 08/07/2009
Idade : 71
Localização : Niterói - RJ

Ir para o topo Ir para baixo

Teoria dos Números - Congruência: uma abordagem objetiva Empty resposta

Mensagem por boris benjamim de paula Seg 06 Dez 2010, 20:29

muito bom , vai me ajudar muito com polinomios.
boris benjamim de paula
boris benjamim de paula
Grupo
Velhos amigos do Fórum

Grupo Velhos amigos do Fórum

Mensagens : 505
Data de inscrição : 18/01/2010
Idade : 31
Localização : natal

Ir para o topo Ir para baixo

Teoria dos Números - Congruência: uma abordagem objetiva Empty Re: Teoria dos Números - Congruência: uma abordagem objetiva

Mensagem por luiseduardo Qua 20 Jul 2011, 01:34

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: https://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:

Teoria dos Números - Congruência: uma abordagem objetiva 571e04d17db659d501bf3c20e7dbc7f2


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

luiseduardo
luiseduardo
Membro de Honra
 Membro de Honra

Mensagens : 2530
Data de inscrição : 08/07/2009
Idade : 26
Localização : Fortaleza-CE

https://www.lcm.com.br/site/#/livros/detalhesLivro/simetria-de-c

Ir para o topo Ir para baixo

Teoria dos Números - Congruência: uma abordagem objetiva Empty Re: Teoria dos Números - Congruência: uma abordagem objetiva

Mensagem por willie123 Ter 12 Jun 2012, 09:38

Very Happy
willie123
willie123
iniciante

Mensagens : 5
Data de inscrição : 12/06/2012
Idade : 36
Localização : brazil

Ir para o topo Ir para baixo

Teoria dos Números - Congruência: uma abordagem objetiva Empty Re: Teoria dos Números - Congruência: uma abordagem objetiva

Mensagem por Dinheirow Sex 13 Jul 2012, 21:30

Very Happy ²
Dinheirow
Dinheirow
Jedi
Jedi

Mensagens : 263
Data de inscrição : 12/06/2012
Idade : 26
Localização : Brasil

Ir para o topo Ir para baixo

Teoria dos Números - Congruência: uma abordagem objetiva Empty Re: Teoria dos Números - Congruência: uma abordagem objetiva

Mensagem por willie123 Ter 14 Ago 2012, 10:50

onde que se pega o gabarito?
willie123
willie123
iniciante

Mensagens : 5
Data de inscrição : 12/06/2012
Idade : 36
Localização : brazil

Ir para o topo Ir para baixo

Teoria dos Números - Congruência: uma abordagem objetiva Empty Re: Teoria dos Números - Congruência: uma abordagem objetiva

Mensagem por Agente Esteves Ter 14 Ago 2012, 11:01

Na minha faculdade eu tenho aulas sobre isso e é de longe o melhor tema que eu estudei nesse período. Muito bom o material, Euclides. =]
Agente Esteves
Agente Esteves
Grupo
Velhos amigos do Fórum

Grupo Velhos amigos do Fórum

Mensagens : 1267
Data de inscrição : 09/11/2010
Idade : 27
Localização : Rio de Janeiro - RJ

Ir para o topo Ir para baixo

Teoria dos Números - Congruência: uma abordagem objetiva Empty Re: Teoria dos Números - Congruência: uma abordagem objetiva

Mensagem por Carlos Fernando Dom 21 Abr 2013, 20:31

Muito obrigado pelo material ajudou muito tenho prova, daqui uns dias e essa apostila esta bem mais explicado que o livro que o professor indicou

Carlos Fernando
iniciante

Mensagens : 2
Data de inscrição : 21/04/2013
Idade : 31
Localização : Nova Andradina

Ir para o topo Ir para baixo

Teoria dos Números - Congruência: uma abordagem objetiva Empty Re: Teoria dos Números - Congruência: uma abordagem objetiva

Mensagem por Conteúdo patrocinado


Conteúdo patrocinado


Ir para o topo Ir para baixo

Página 1 de 2 1, 2  Seguinte

Ir para o topo


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