Slide - Aula 10 Equações Diofantinas Lineares - Matemática Discreta 2021-2

Matematica Discreta — Aula 10 — r= Equacoes Diofantinas lineares, MMC Jamil Abreu UFLA/ICET/DMM Lavras/MG Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 10 1/21 Vamos tratar na primeira parte desta aula de resolver equa¸c˜oes lineares da forma ax + by = c. (∗) Aqui, a, b e c s˜ao inteiros e as solu¸c˜oes x e y devem tamb´em ser inteiras. H´a um esquema para se determinar infinitas solu¸c˜oes dado que uma exista. Vejamos um exemplo concreto. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 10 2 / 21 Exemplo Determinar as solu¸c˜oes inteiras da equa¸c˜ao 5x + 22y = 18. (⋆) Resolvendo para x temos x = 18 − 22y 5 . (⋆a) Como x deve ser inteiro, tamb´em (18−22y)/5 deve ser inteiro. Reescreva 18 − 22y 5 = (15 − 20y) + (3 − 2y) 5 = 3 − 4y + 3 − 2y 5 . Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 10 3 / 21 Continua¸c˜ao Como 3 − 4y deve ser inteiro (pois y deve ser inteiro), tamb´em 3 − 2y 5 = z deve ser inteiro; disto, temos uma nova equa¸c˜ao linear, 2y + 5z = 3, cuja vantagem ´e ter coeficientes menores. Agora, repetimos o procedimento resolvendo para a vari´avel de menor coeficiente: y = 3 − 5z 2 (⋆b) = 1 − 2z + 1 − z 2 . Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 10 4 / 21 Continua¸c˜ao Como 1 − 2z deve ser inteiro (pois z deve ser inteiro), tamb´em 1 − z 2 = t deve ser inteiro; assim, temos 2t + z = 1, ou z = 1 − 2t. Agora, este z ´e sempre inteiro para todo inteiro t. Substituindo de volta em (⋆b) e (⋆a) temos (⋆c)      y = 3 − 5 · (1 − 2t) 2 = −1 + 5t, x = 18 − 22 · (−1 + 5t) 5 = 8 − 22t. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 10 5 / 21 Continua¸c˜ao Resumindo, qualquer solu¸c˜ao (x, y) de (⋆) deve ser da forma (⋆c) para algum inteiro t. Reciprocamente, substituindo x e y da forma (⋆c) (para t um inteiro qualquer) em (⋆), vemos que tais x e y s˜ao solu¸c˜oes. Portanto, (⋆c) ´e a solu¸c˜ao geral de (⋆). Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 10 6 / 21 Certamente, a mesma ideia poderia ser trabalhada no caso geral. Entretanto, adotaremos outra abordagem, usando as ferramentas j´a desenvolvidas at´e aqui (leia-se: MDC). Primeiro, note que o lado esquerdo da equa¸c˜ao (∗), a saber, a express˜ao ax + by, ´e sempre divis´ıvel por d = (a, b), o MDC de a e b. Logo, uma condi¸c˜ao necess´aria para que (∗) tenha solu¸c˜ao ´e que d|c. Por outro lado, supondo esta condi¸c˜ao seja satisfeita, dividamos (∗) por d, da´ı obtendo uma equa¸c˜ao equivalente, a′x + b′y = c′, (∗∗) onde, agora, (a′, b′) = 1.(1) (1) Veja a propriedade (c) na Aula 09. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 10 7 / 21 Pela propriedade (d) da Aula 09, existem inteiros x′ 0 e y′ 0 tais que a′x′ 0 + b′y′ 0 = 1. Logo, a′(c′x′ 0) + b′(c′y′ 0) = c′, ou seja, x0 = c′x′ 0 e y0 = c′y′ 0 s˜ao solu¸c˜oes de (∗∗). Agora, suponha que (x1, y1) seja uma solu¸c˜ao qualquer de (∗∗). Assim, temos a′x0 + b′y0 = c′ a′x1 + b′y1 = c′. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 10 8 / 21 Subtraimos, obtemos a’(xo — x1) = b'(yv1 — yo). Logo, a divide b'(y; — yo); como (a’, b’) = 1, devemos ter a’|(y1 — yo). Analogamente, b’|(xo — x1). Como (yi — yo) + a! = (x0 — x1) + BD’, deve existir t tal que Xo — Xi = —b't e yo-vM = at ou (t) a0 OF yi =yo- at. Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 10 9/21 Reciprocamente, se x1 e y1 est˜ao relacionados a x0 e y0 por (†) ent˜ao a′x1 + b′y1 = a′(x0 + b′t) + b′(y0 − a′t) = a′x0 + b′y0 = c′, portanto (x1, y1) ´e solu¸c˜ao de (∗∗). Resumindo, temos o seguinte teorema. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 10 10 / 21 Teorema Uma condi¸c˜ao necess´aria e suficiente para que a equa¸c˜ao ax + by = c tenha solu¸c˜oes inteiras x e y ´e que d|c, onde d = (a, b). Se existe uma solu¸c˜ao (x0, y0) ent˜ao existem infinitas solu¸c˜oes (x, y), as quais s˜ao da forma x = x0 + b d t, y = y0 − a d t, onde t denota inteiros arbitr´arios. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 10 11 / 21 H´a problemas concretos que levam a equa¸c˜oes Diofantinas lineares cujas solu¸c˜oes devem ser positivas, devido `a pr´opria natureza do problema em quest˜ao. Suponha que a equa¸c˜ao ax + by = c tenha solu¸c˜oes inteiras x0 e y0. Pelo teorema anterior, haver´a solu¸c˜oes positivas se existe um inteiro t tal que x0 + b d t > 0 e y0 − a d t > 0. (‡) Logo, bt > −x0d e at < y0d. H´a duas situa¸c˜oes a se considerar: Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 10 12 / 21 1 ae b tém sinais contrarios: Por exemplo, se a < 0 < b entao xod d t>— eg ta OO. b a Se, porém, b < 0 < a entdo xod d t< ee tc MO b a Portanto, nessa situa¢do (i.e., ab < 0), todos os inteiros t maiores do que um certo numero (se a < 0 < b) ou menores do que um certo numero (se b <0 < a) cumprem (). Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 10 13/21 ms ae b tém mesmo sinal: Por exemplo, se a > 0 e b > 0 entao xod od mec t< ™. b a Se, porém, a< 0e5b< 0 entao xod od 7 st > OE b a Nessa situa¢do (i.e., ab > 0), os inteiros t que cumprem (t) — portanto, que correspondem a solucdes positivas — sao aqueles nos intervalos acima (conforme sejam a e b ambos positivos ou ambos negativos). Jamil Abreu (UFLA/ICET/DMMLavras/MC Matematica Discreta — Aula 10 14/21 Exemplo Uma empresa encomenda de seu fornecedor uma quantidade de mercadorias avaliada ao todo em R$2.490,00. Esta encomenda compreende dois tipos de produto, um que custa R$29,00 a unidade e outro que custa R$33,00 a unidade. Quantos itens de cada mercadoria podem ter sido encomendados? Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 10 15 / 21 Solu¸c˜ao Se h´a x itens do primeiro produto e y itens do segundo, ent˜ao a situa¸c˜ao posta nos leva `a equa¸c˜ao Diofantina linear 29x + 33y = 2490. Primeiro, devemos achar o MDC de 29 e 33 (obviamente, ´e 1). Pelo algoritmo da divis˜ao, 33 = 29 · 1 + 4, 29 = 7 · 4 + 1. Logo, (33, 29) = 1; al´em disso, 1 = 29 − 7 · 4 = 29 − 7 · (33 − 29) = 29 · 8 − 33 · 7. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 10 16 / 21 Continua¸c˜ao Agora, ´e conveniente que voltemos ao exposto no Slide 8. Aqui, como (33, 29) = 1, n˜ao precisamos dividir a equa¸c˜ao pelo MDC pois as Eqs. (∗) e (∗∗) j´a s˜ao idˆenticas: a = a′ = 29 e b = b′ = 33. Pelo que fizemos acima, temos x′ 0 = 8 e y′ 0 = −7. Aqui, c′ = 2490; pela informa¸c˜ao em destaque no Slide 8, temos a solu¸c˜ao particular, x0 = c′x′ 0 = 2490 · 8 e y0 = c′y′ 0 = 2490 · (−7) Pelo teorema, a solu¸c˜ao geral ´e x = 2490 · 8 + 33t, y = −2490 · 7 − 29t. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 10 17 / 21 Solu¸c˜oes positivas correspondem a valores de t tais que −2490 · 8 33 < t < −2490 · 7 29 ou seja, −603,6 · · · < t < −601,03 . . . , isto ´e, t = −603 ou t = −602. Isto nos d´a as solu¸c˜oes x = 21 e y = 57, ou x = 54 e y = 28. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 10 18 / 21 Nesta segunda parte da aula, discutiremos o conceito de MMC — o menor m´ultiplo comum. Juntamente com o conte´udo da Aula 09, isto encerra o que poder´ıamos chamar de “consequˆencias do algoritmo da divis˜ao”. O MMC ´e introduzido no pr´oximo teorema. Teorema O n´umero ⟨a, b⟩ = |ab| (a, b) tem as seguintes propriedades: (i) ⟨a, b⟩ ⩾ 0; (ii) a|⟨a, b⟩ e b|⟨a, b⟩; (iii) se a|m e b|m ent˜ao ⟨a, b⟩|m. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 10 19 / 21 Demonstra¸c˜ao (i) ´Obvio. (ii) Como (a, b)|b, podemos escrever ⟨a, b⟩ = |a| · |b| (a, b), sendo este um produto de inteiros; logo, a|⟨a, b⟩. Analogamente, ⟨a, b⟩ = |b| · |a| (a, b), logo b|⟨a, b⟩. Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 10 20 / 21 Continua¸c˜ao (iii) Existem inteiros r e s tais que m = ra = sb. Seja d = (a, b). Logo, a = a1d e b = b1d para certos inteiros a1 e b1. Note que (a1, b1) = 1. (Por quˆe?) Consequentemente, m = ra1d = sb1d, em particular, ra1 = sb1. Assim, a1|sb1, mas (a1, b1) = 1, logo a1|s, portanto s = a1t para algum inteiro t. Resulta que m = sb = a1tb = t(a1d)b d = t · ab d = t · ⟨a, b⟩. QED Jamil Abreu (UFLA/ICET/DMMLavras/MG) Matem´atica Discreta – Aula 10 21 / 21