Teorema De Bezout E Equacoes Diofantinas 5e4u6q

Fundamentos da álgebra Profª. Ms Renata Siano Gonçalves 1ºano de Matemática Campus –Osasco

Teorema de Bézout Sejam a, b inteiros e d = mdc ( a, b ). Então, existem inteiros r e s tais que d = ra + sb. Podemos encontrar um par de r e s encontrando o mdc (a, b) por meio das divisões sucessivas. Sejam a, b inteiros, b ≠ 0, e sejam q, r o quociente e o resto da divisão de a por b, respectivamente. Então, D(a, b) = D (b, r); temos também que mdc( a, b) =mdc( b, r) Segue do Lema acima que o problema de achar o mdc( a, b) reduz- se a achar o mdc ( b, r). Naturalmente, pode-se repetir esse processo fazendo divisões sucessivas. Exemplo: Vamos calcular o mdc ( 1 128 , 336) 1 128 120

3 336 96

2 120 24

1 96 0

4 24

Logo, mdc ( 1128 , 336) = 24. Esse processo também permite determinar inteiros r e s nas condições do Teorema de Bézout. A primeira divisão temos: r1 = a − q1b Isto é, r1 foi escrito como uma combinação linear de a e b. Substituindo do r1 pelo seu valor na segunda, temos: b = (a − q1b)q 2 + r2 ; logo, r2 = −q 2 a + (1 + q1 q 2 )b . Novamente, pudemos escrever r2 como combinação linear de a e b . Na igualdade seguinte poderemos substituir r1 e r2 pelas expressões achadas e escrever r3 em função de a e b. Reiterando o processo, obteremos finalmente uma expressão para rn como combinação linear de a e b.

Escrevendo explicitamente as divisões de a = 1 128 e b = 336 temos: (1) (2) (3) (4)

1 128 = 3. 336 + 120 336 = 2. 120 + 96. 120 = 1. 96 + 24. 96 = 4.24

Em (1) Isolando o resto, temos : 120 = 1 128 – 3. 336 Substituindo em (2) temos: 336 = 2. ( 1 128 – 3. 336) + 96 Isolando 96, temos: 96 = 336 – 2( 1128 – 3.336) 96= 336 – 2.1128 + 6. 336 96 = - 2. 1128 + 7 . 336 Finalmente, em (3) obteremos 120 = 1. 96 +24 1 128 – 3. 336 = 1. ( -2.1128 + 7. 336) +24 Isolando 24 que é o mdc (a, b) , temos: 24 = 1 128 – 3. 336 + 2. 1128 - 7. 336 24 = 3 . 1128 – 10. 336 Assim, um par de inteiros r , s nas condições do Teorema de Bézout é dado por r = 3 e s = -10 Exercícios 1) Usar o algoritmo de Euclides ,(divisões sucessivas) para obter números r e s satisfazendo: a) b) c)

mdc ( 56, 72 ) = 56 r + 72s mdc ( 24, 138) = 24r + 138s mdc(119, 272) = 119r + 272s

2) Determinar um múltiplo de 19 e um múltiplo de 17 cuja diferença seja 5.

Fundamentos da álgebra Profª. Ms Renata Siano Gonçalves 1ºano de Matemática Campus –Osasco

Equações Diofantinas lineares Consideremos equações diofantinas da forma aX + bY = c , em que a e b não são nulos. Procuraremos soluções inteiras, isto é, pares de números x, y Є Z tais que ax + by = c. Diophanto de Alexandria( 250 d.C) foi o primeiro a considerar problemas que envolvam equações indeterminadas que eventualmente item infinitas soluções. Esse tipo de equação associa-se tradicionalmente ao seu nome. Sabemos que muitos problemas da vida diária item apenas soluções inteiras. Suponhamos, por exemplo, que se quer adquirir um determinado líquido que é vendido em recipiente de 7 litros ou de 15 litros e se deseja fazer uma compra de 125 litros, chamando de x e y o número de recipientes de 15 litros e 7 litros, respectivamente, a resolução do problema acima nos leva à equação diofantina: 15x +7y = 125 Sabe-se que uma equação do tipo aX + bY = c , em que se item valores reais para as variáveis X e Y , representa uma reta no plano cartesiano. Algumas equações diofantinas nunca têm solução. Por exemplo, na equação 4x + 6y = 5, para qualquer par de x e y , o primeiro membro é um par, enquanto o segundo é ímpar. Portanto, essa equação não têm solução. Começaremos o estudo procurando condições para a existência de soluções. Sejam a, b e c inteiros e d = mdc( a , b ). A equação diofantina aX +bY = c tem solução se e somente se d /c . Teorema Sejam a , b e c inteiros tais que d = mdc ( a, b ) divide c. Escrevendo d da forma c c d = ra + sb, com r , s Є Z, temos que Xo = r. , Yo= s. é uma solução da equação d d aX + bY = c . Toda outra solução é da forma,

c a c b + t Y = s. - t , com t Є R. d d d d Ou podemos escrever; b a X = Xo + t Y = Yo - t d d E, reciprocamente, para todo t Є Z os valores x e y dados pelas fórmulas acima são soluções da equação. X= r.

Exemplo: 1)

Vamos determinar soluções de 56x + 72y =40

C.E ( condição de existência) Temos que mdc(56,72) = 8. Como 8/40 , a equação tem, de fato, soluções. Calculando r e s ( usando o algoritmo de Euclides ) tais que r 56 + s 72 = 8 , temos: 72 16

1 56 8

(1) (2) (3)

3 16 0

2 8

72= 1. 56 + 16 56 = 3. 16 + 8 16 = 2. 8

Isolando o 1º resto ( 16) temos: 16 = 72 – 1. 56 Substituindo em (2) temos: 56 = 3. ( 72 – 1. 56) + 8 Logo, 56 = 3. 72 - 3. 56 + 8 Isolando o mdc que é o 8 , temos: 8 = 56 - 3. 72 + 3. 56 8 = 4. 56 - 3.72

Pelo teorema de Bézout ar +bs = mdc(a,b) 56.4 + 72(-3) = 8 A equação dada é 56 x + 72 y = 40 Xo = r.

c c , Yo= s. é uma solução da equação d d

Podemos dizer que uma das soluções dessa equação é Xo = 4.

40 = 20 8

Yo = (-3).

40 = -15 8

( 20, -15)

Agora vamos obter a equação geral que podemos encontrar outras soluções: Calculando

56 72 =7 e =9 8 8

b t d 72 X = 20 + t 8 X = Xo +

S = { X = 20 + 9t

a t d 56 Y = -15 t 8

Y = Yo -

e Y = - 15 – 7t , t Є Z }

Exercícios: 1)Resolver as equações diofantinas: a) b) c) d) e) f) g)

2x + 3y =9 3x + 5y = 47 8x + 7y =3 47x +29y = 999 3x + 4y = 20 5x - 2y = 2 18x - 20 y = - 8

Bibliografia: Números: Uma Introdução à Matemática César Polcino Milies e Sônia Pitta Coelho 3.ed. – São Paulo:editora da Universidade de São Paulo, 2003