Teoria dos Números aula 5 conteudo on line

Prévia do material em texto

Teoria dos Números
Aula 4: Congruência
Inteiros congruentes
Sejam a e b dois inteiros quaisquer e seja m um inteiro positivo fixo. Diz-se que a é congruente a b módulo m se e somente se m divide a diferença a-b.
De outra forma: a é congruente a ≡ b módulo m se e somente se existe um inteiro k tal que a- b =km.
ab (mód.m) indica-se que a é congruente a b módulo m. Portanto, simbolicamente:
ab (mód.m) ↔ m|(a-b)
Ou seja:
ab (mód.m) K  Z | a-b = km
Exemplos:
12  3 (mód. 3) , pois 3|(12-3)
2513 (mód. 6) , pois 6|(25-13)
-15-63 (mód. 8) , pois 8|(-15+63)
Se a não divide a diferença a-b, então diz-se que a é incongruente a ≡ b módulo m, o que se indica pela notação:
ab (mód.m)
 
Observações:
Caracterização de inteiros congruentes
Teorema: Dois inteiros a e b são congruentes módulo m se e somente se a e b deixam o mesmo resto quando divididos por m.
 Exemplos: 
Mostrar que 32≡ 23 (mód.3).
Solução:
Devemos mostrar que 32 e 23, quando divididos por 3, deixam o mesmo resto. De fato:
32 dividido por 3 deixa resto 2 e 23 dividido por 3 também deixa resto 2.
Teorema: Dois inteiros a e b são congruentes módulo m se e somente se a e b deixam o mesmo resto quando divididos por m.
Exemplos: 
Mostrar que os inteiros -46 e 24 deixam o mesmo resto quando divididos por 7.
Solução:
-46≡24(mód.7).pois 7|(-46-24)
Congruência módulo m
Teorema: Seja m um inteiro fixo e sejam a, b e c inteiros quaisquer.
a ≡ a (mód.m)
Se a ≡ b (mód.m) , então b (mód.m)
Se a ≡ b (mód.m) e se b ≡ c (mód.m) , então ac (mód.m)
##exercício resolvido aula 4 – pasta##
Classes residuais
Agora vamos estudar o conceito de classes residuais.
Definição:
Chama-se classe residual módulo m (m >0) de um inteiro a o conjunto de todos os inteiros que são congruentes a a módulo m. Em outras palavras, o conjunto de todos os inteiros que, divididos por m, deixam resto a.
Vamos dar exemplos de algumas classes residuais:
Operações com congruências
Se a ≡ b (mód .m) e se c ≡ d ( mód. m), então:
1) a+c ≡ b + d (mód.m)
2) a-c ≡b-d (mód.m)
3) ac≡ bd (mód.m)
Demonstração:
 
1) Se a ≡ b ( mód.m), então a = b + mk   (I)
    Se c≡d (mód.m), então c = d + m h  (II)
Somando (I) e (II), temos:
a+c = b+d+mk+mh
a+c = b+d +(K+h)m, daí:
a+c ≡b+d (mód.m)
2 ) Se a≡b (mód.m), então a = b +m K (I)
    Se c ≡d (mód.m), então c = d + mh (II)
 
Fazendo (I)-(II), temos:
a - c = b+mk –d-mh
a - c =(b-d)+(k-h)m, daí:
a - c ≡(b-d) (mód.m)
3) ac=(b+mk)(d+mh) = (bd+bmh+dmk+mmhk)
    ac = bd+(bh+dk+mnk) m, daí:
    ac≡ bd (mód.m)
1) 10-5≡2+3 (mód.4)
    5 ≡5(mód.4)
    10-(-5)≡2-3 (mód.4)
    15≡-1 (mód.4)
   -50≡6(mód.4)
2) 11≡ -2 (mód.13)
     -5≡21 (mód.13)
     6≡19 (mód.13)
     11-(-5)≡-2-21(mód.13)
16≡-23 (mód.13)
-55≡-42(mód.13)
Operações com congruências – mudança de módulo
Veremos alguns teoremas envolvendo mudança de módulo numa congruência.
Teorema: Se a ≡ b (mód.m) e se n|m, sendo m um inteiro positivo, então a≡b (mód.n).
Demonstração: 
Se a ≡ b (mód.m), então a-b = hm, onde h é um inteiro qualquer.
Se n|m, então m =nj, onde j é um inteiro positivo qualquer. Logo:
a-b=(hj)n e a≡   (mód.n).
Exemplos:
20≡ 12 (mód.8) e 4 |8, então 20≡12 (mód.4).
18≡ 8 (mód.10) e 5 |10, então 18≡8 (mód.5).
-15≡ -3 (mód.4)  e 2| 4, então -15≡-3 (mód. 2).
Teorema: Se a ≡ b (mód.m) e se c é um inteiro positivo, então ac≡ bc (mód.mc).
Se a≡b (mód.m), então a-b= hm, onde h é um inteiro qualquer. Multiplicando a equação por c, encontramos: ac –bc =h(cm), então ac≡bc(mód.mc).
Exemplos:
12≡ -4 (mod.8) e c= 3, então 36≡-12 (mód.24)
20≡ 4 (mód.4) e c = 10, então 200≡40 (mód.40).
Teorema: 
Se a ≡b (mód.m) e se a,b e m são todos divisíveis pelo inteiro positivo d, então:
Demonstração:
Com efeito, se a≡b (mód.m) ,então:
a-b =hm, com h inteiro qualquer. Dividindo toda a equação por d, temos:
 Daí:
Exemplos:
32≡8 (mód. 12)  e como 32, 8 e 12 são todos divisíveis por 4, temos:
8≡ 2 (mód.3).
40≡4 (mód.12) e como 40, 4 e 12 são todos divisíveis por 4, temos:
10≡1 (mód.3).
Teoria dos Números 
Aula 5: Equações e Sistemas de equações Diofantinas
Equações e Sistemas de equações diofantinas lineares
A forma da equação diofantina linear com duas incógnitas x e y é: ax+by = c, onde a, b e c são inteiros dados, sendo ab≠0.
Exemplos:
1) 2x+3y = 5
2) 3x+6y = 10
3) 5x+2y = -4
Consideremos a equação diofantina linear 2x+3y = 5. Podemos observar sem muita dificuldade que os valores x = 1 e y = 1 satisfazem à equação. Basta para isso substituirmos na equação; vejamos:
2 (1) + 3 (1) = 5
2 + 3 = 5
5 = 5
Incógnitas
Encontramos uma sentença verdadeira, portanto o par fornecido é uma solução da equação diofantina linear 3x -4y = -15.
Existem equações diofantinas lineares com duas incógnitas que não têm solução. Vejamos um exemplo:
A equação 2x +4y = 13 não tem solução. Basta observarmos que o valor de x está sendo multiplicado por 2, e portanto, é um número par. O valor de y está sendo multiplicado por 4, portanto o resultado é também um número par. A soma de dois números pares obrigatoriamente é um número par, sendo impossível encontrarmos como resposta 13. Logo, a equação não apresenta solução.
Em geral, a equação diofantina linear ax + by = c não tem solução todas as vezes que d =mdc (a,b) não divide c. Em outras palavras, a equação diofantina linear tem solução se e somente se d divide c, sendo d = mdc (a,b). 
Vejamos os exemplos:
A equação linear 2x + 3y = 6 tem solução inteira?
mdc (2,3) = 1 e 1 divide 6, portanto a equação apresenta solução.
A equação linear 2x +6y = 23 tem solução inteira?
mdc (2,6) = 2 e 2 não divide 23, portanto a equação não apresenta solução inteira.
Teorema
Solução Particular
Devemos atentar para o fato de a solução geral ser obtida a partir de uma solução chamada solução particular. Por exemplo:
Determinar todas as soluções inteiras da equação 2x +5 y =10.
Seja d= mdc (2,5) = 1, que divide 10, logo a equação apresenta solução.
Mais exemplos
Vamos observar que, para cada valor que escolhemos para t, obtemos uma nova solução para a equação.
Vamos escolher, por exemplo, t = 2. Substituindo, obteremos:
x= 5 (2) =10
y =2-2(2)=2-4=-2
Portanto x =10 e y =-2 é uma nova solução para a equação dada.
Vamos a um novo exemplo:
4x+2y =12
x=2+(2/2)t, y = 2-(4/2)t
... Aonde t é um inteiro qualquer.
x =2+t, y = 2-2t
... É a solução da equação.
Não é demais lembrarmos que, para cada valor inteiro de t escolhido, obteremos uma solução da equação dada. Por exemplo, fazendo t = -1, encontramos:
X = 2 -1 = 1 e y = 2 -2 (-1)
X = 1, y = 4
Obs.: Uma solução particular da equação diofantina linear pode ser obtida por tentativas ou pelo algoritmo de Euclides. Vamos a mais um exemplo:
Determinar todas as soluções da equação diofantina linear
172 x + 20 y =1000.
Determinemos, inicialmente, o mdc(172,20) pelo processo das divisões sucessivas (Algoritmo de Euclides):
172 =20.8+12
20 =12.1+8
12=8.1+4
8=4.2
Portanto, o mdc (172,20) = 4 e como 4/1000, segue-se que a equação tem solução.
Devemos expressar o inteiro 4 como combinação linear de 172 e 20. Para tal, devemos eliminar sucessivamente os restos 8 e 12 entre as três primeiras igualdades anteriores, da seguinte forma:
4=12-8=12-(20-12)=2.12-20=2(172-20.8)-20=172.2+20(-17)
Isto é:
4 =172.2+20 (-17)
Multiplicando ambos os membros desta igualdade por 1000/4 =250, obtemos:
1000=172.500+20(-4250)
Portanto, o par de inteiros x0 =500, y0 =-4250 é uma solução particular da equação proposta, e todas as outras soluções são dadas pelas fórmulas:
Teoria dos Números
Aula 6: Equações e Sistemas de equações Diofantinas
 
Condição de existência de solução
A congruência linear ax   b (mód.m) tem solução se e somente se d divide b (d/b), sendo d=mdc(a,m).
Exemplos:
4x ≡ 2(mód.3)
d = 1 = mdc(4,3) e 1 divide 3, portanto a congruência linear apresenta solução.
12x ≡ 8 (mód.4)
d = 4 = mdc(12,4) e 4 divide 8, portanto a congruência linear apresenta solução.
12x ≡ 8 (mód.3)
d = 3 = mdc(12,3), mas 3 nãodivide 8, portanto a congruência não apresenta solução.
Exercícios resolvidos
Do teorema anterior, podemos concluir que, se o mdc(a,m)=1, então a congruência linear ax   b(mód.m) tem uma única solução módulo m.
Exemplo 1:
Resolver a congruência linear: 6x ≡ 10 (mód.8)
Exemplo 2:
Resolver a congruência linear: 21x ≡ 15 (mód.39)
Exemplo 3:
Resolver a congruência linear: 3x ≡ 6 (mod.18)
Exemplo 4:
Resolver a congruência linear: 14x ≡ 36 (mod.48)
Exemplo 5:
Resolver a congruência linear: 64x ≡ 16 (mod.84)
Resolução de equações diofantinas lineares por congruências
Resolver por congruências a equação diofantina linear 48x+7y =17.
Resolver por congruências a equação diofantina linear 48x+7y =17.
Resolver por congruências a equação diofantina linear: 9x+16y =35.
Resolver por congruência a equação diofantina linear: 7x + 6y = 9.
Inverso de um inteiro
Definição: Seja a um inteiro, chama-se inverso de a módulo m, caso exista um inteiro a* tal que a.a* ≡ 1(mód.m).
Exemplos:
Qual o inverso de 5 módulo 6?
• 5x ≡ 1(mód.6)
• 5.5 ≡ 1(mód.6)
Portanto, o inverso de 5 módulo 6 é o próprio 5.
Qual o inverso de 4 módulo 12?
• 4x ≡ 1(mód.12)
O mdc (4,12) = 4, mas 4 não divide 1, portanto a congruência linear não tem solução. Logo, 4 não tem inverso módulo 12.
Sistemas de congruências lineares
Um sistema de duas ou mais congruências lineares não necessariamente tem solução, mesmo que cada congruência linear que forma o sistema tenha solução isoladamente. 
Vamos resolver o sistema de congruências lineares:
x ≡ 1(mód.2) e x ≡ 1(mód.3)
Se x ≡ 1(mód.2), então x = 2 a +1, logo:
2a + 1 ≡ 1 (mód.3)
2a ≡ 0 (mód.3)
a ≡ 0 (mód.3), daí: a = 3b
x = 2(3b) + 1
x = 6b + 1
x ≡ 1(mód.6)
Outro exemplo:
x ≡ 5(mód.12), x (mód.19) 
x ≡ 5(mód.12)
x = 5 + 12a, substituindo na outra congruência, temos:
 
5 + 12a 7(mód.19)
12a ≡ 2(mód.19)
6a ≡ 1(mód.19)
6a - 18(mód.19)
a - 3(mód.19)
a ≡ 16(mód.19)
a = 16 + 19b
 
x = 5 + 12a
x = 5 + 12(16 + 19b)
x= 5 + 192 + 228b
x = 197+228b
x ≡ (mód.228)
Teoria dos Números 
Aula 7: