Lista 4 DIOFANTINAS T FERMAT

Prévia do material em texto

EQUAÇÕES DIOFANTINAS LINEARES.
São equações da forma 
Exemplos: 
1) temos com solução ou ou 
 Logo os pares 4 e 6; -6 e 6; e 10e-2 são soluções da equação.
2) não tem solução porque é um número par enquanto 7 é impar.
8.1 CONDIÇÃO DE EXISTÊNCIA DE SOLUÇÃO DE EQ. DIOFANTINAS
TEOREMA: A equação Diofantina linear , tem solução se e somente se d divide c, sendo d = mdc(a,b)
Demonstração.
TEOREMA. Se o par é uma solução particular da equação, então todas as outras soluções desta equação são dadas por: 
Aplicações:
1)Determinar todas as soluções da equação Diofantina:
O mdc(172,20) pelo algoritmo de Euclides :
172 = 20. 8 + 12
20 =12.1 + 8
12 = 8.1 + 4
8 = 4.2
Portanto mdc(172,20) = 4 e como 4|1000 , segue-se que a equação tem solução.
Das igualdades acima vamos expressar 4 como uma combinação linear de de 172 e 20. Então vamos eliminar os restos 8 e 12 do seguinte modo:
4 = 12 – 8.1 = 12 – (20 – 1.12).1 = 12 – 20 + 1.12 = 2.12 – 20 = 2(172 – 20.8) – 20 =
2.172 – 16.20 – 20 = 2.172 – 17.20 = 172(2) + 20(-17)
172(2) + 20(-17) = 4 Multiplicando esta equação por 250 obtemos 172(500)+20(-4250)=1000
Portanto o par é uma solução particular da equação proposta.
Todas as outras soluções são:
x = 500 + (20/4).t = 500 + 5t e y = -4250 - (172/4).t = -4250 – 43t
1)Determinar todas as soluções inteiras e positivas da equação Diofantina:
O mdc(18,5) pelo algoritmo de Euclides :
18 = 5.3 + 3
5 = 3.1 + 2
3 = 2.1 + 1
2 = 2.1
Portanto mdc(18,5) = 1 e como 1|48 , segue-se que a equação tem solução.
Das igualdades acima vamos expressar 1 como uma combinação linear de 18 e 5. Então vamos eliminar os restos 2 e 3 do seguinte modo:
1 = 3 – 2.1 = 3 – (5 – 1.3).1 = 3 – 5 + 1.3 = 2.3 – 5 = 2(18 – 5.3) – 5 = 2.18 – 6.5 – 5 =2.18 -7.5=
=18(2) + 5(-7) = 1 ( 48 ) 48 = 18(96) + 5( - 336)
Portanto o par é uma solução particular da equação proposta.
Todas as outras soluções são:
x = 96 + 5t e y = -336 - 18t 
A solução inteira e positiva será 96 + 5t > 0 e -336 - 18t > 0 t > -19 1/5 e t < -18 2/3
Logo t = - 19 e portanto x = 96 + 5(-19) =1 e y = -336 – 18(-19) = 6
CONDIÇÃO DE EXISTÊNCIA DE SOLUÇÃO DE PARA .
TEOREMA: A congruência linear tem solução se e somente se d|b sendo d o mdc(a,m). Isto porque esta é a condição de existência de solução da equação 
1) O mdc(a,m)=mdc(18,42)=6 e como 6|42 a equação tem solução. Por tentativas facilmente vê-se que . Por conseguinte as soluções mutuamente incongruente são: x = 4 + k.m = 4 + (42/6) t onde t= 1,2,3...5 x={4,11,18,25,32,39} 
2) O mdc(21,39) = 3 e como 3|15 a equação tem 3 solução mutuamente incongruente. A diofantina equivalente é Pelo algoritmo de Euclides : 39 = 21.1 + 18 21 = 18.1 + 3 18 = 6.3 3 = 21 – 18.1 = 21- (39 – 21.1).1 = 21 – 39 + 21.1 = =21.2 -39 3 = 21.2 - 3915 = 21.10 – 39.5 Logo e as 3 soluções mutuamente incongruente são x = 10 + (39/3) t = 10 + 13t x={10,23,36}
3) O mdc(11,317) = 1 e como 1|2 a equação tem 1 única solução. A diofantina equivalente é Pelo algoritmo de Euclides : 317 = 11.28 + 9 11 = 9.1 + 2 9 = 2.4 +1 2 = 1.2 1 = 9 - 2.4 = 9 - (11 – 9.1).4 = 9.5 – 11.4 = = (317 – 11.28).5 – 11.4 = 317.5 -11.144 2 = 11(-288) – 317(-10) Logo ou x = 29 é a única solução da congruência.
4) O mdc(35,14) = 7 e como 7/|5 a equação não tem solução. 
9.6 RESOLUÇÃO DE DIOFANTINAS POR CONGRUÊNCIA.
1) mdc(48,7) = 1 a equação tem solução. A diofantina dada é equivalente a congruência . Substituindo-se esse valor na eq. Dada obtemos: 48.4 +7 y = 17 y = - 25. Logo o par 4, 25 é uma solução particular e todas as outras soluções são : x = 4 + 7 t y = -25 – 48 t onde t é um inteiro arbitrário.
2) mdc(9,16) = 1 a equação tem solução. A diofantina dada é equivalente a congruência . Substituindo-se esse valor na eq. dada obtemos: 9x + 16(5+ 9t) = 35 x = - 5 – 16 t.
TEOREMA DE FERMAT
Se , então se p for primo.
Exemplo: p = 59 ( primo) 
Determine o resto da divisão de por 1997, sabendo que 1997 é primo. Solução: Pelo Teorema de Fermat . Logo o resto é 1997.
Qual é o resto de por 47. Solução: Por Fermat 
Demonstração do teorema de Fermat. Usaremos o princípio da Indução.
Válido para a = 1, pois 
Suponhamos que a premissa a = k que nos dá seja verdadeira.
Vamos provar a validade para a = k+1.
Queremos mostrar que Vejamos 
Como todos os termos são múltiplos de p exceto o primeiro e o último obtemos: . Mas da premissa .Então o que finaliza a demonstração.
12.1 COROLÁRIOS DO TEOREMA DE FERMAT.
1º Se p/| a , então 
2º O teorema de Fermat pode ser estendido para .
Exemplos: 
3) Verificar o teorema de Fermat com a = 3 e p = 7. Solução : . Agora verifique o corolário. o que confirma o corolário.
4) Mostrar que . Solução: Pelo teorema de Fermat 
13 TEOREMA DE WILSON.
Se p é primo então .
Exemplo: Verificar o Teorema de Wilson com p = 7.
Sabemos que ( 7- 1 )! + 1 = 6! +1 = 720 +1 = 721= 7.103 o que mostra que 
2) Mostrar que 11 é primo. Solução : Como ( 11 -1 )! +1 = 10! + 1= 1.2.3....10 + 1 = 3628801 = 11.329891 Logo 11 é primo.