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

Muito bom o material vlw Euclides, vai ajudar bastante.

Olá amigo, muito legal....


Um abraço.

muito bom , vai me ajudar muito com polinomios.

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:

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:

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

²

onde que se pega o gabarito?

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. =]

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