Edit page

MDC e Eq. Diofantinas

Máximo divisor comum

Definição: dados dois números aa e bb inteiros, diz-se que o número dN1d \in \N_1 é máximo divisor comum de aa e bb, e escreve-se ab=da \frown b = d, se:

a) dad | a (dd divide aa) e dbd|b;

b) Para todo o dN1d' \in \N_1 tal que dad'|a e dbd'|b tem-se que ddd'|d.

Tem-se a seguinte propriedade:

ab=(a)b=a(b)=(a)(b)a \frown b = (-a) \frown b =a \frown (-b) = (-a)\frown(-b)

Teorema da unicidade:

Se existir o máximo divisor de aa e de bb, então este é único.

Prova

dd é M.D.C. de aa e bb. Vem então:

a) dad|a e dbd|b;

b) dN1((da\forall_{d'' \in \N_1}((d''|a e db)    ddd''|b) \implies d''|d

Suponha-se a existência de dd' e que este também é M.D.C. de aa e bb. Então:

c) dad'|a e dbd'|b;

d) dN1((da\forall_{d'' \in \N_1}((d''|a e db)    ddd''|b) \implies d''|d'

A partir das proposições a) e d) retira-se que ddd|d'. A partir das proposições c) e b) retira-se que ddd'|d. Assim, pela antissimetria da divisão, vem que d=dd=d'.

Teorema da base da recorrência:

Se o inteiro aa divide o inteiro bb, então ab=aa \frown b = a.

Por exemplo, 1224    1224=1212|24 \implies 12 \frown 24 = 12.

Prova

Como se tem que aaa|a e aba|b, tem-se pela proposição vista no início que ab=aa \frown b = a.

Teorema do resto da divisão:

Se r1r_1 é o resto da divisão de aa por bb, então aba\frown b existe e coincide com br1b \frown r_1.

Por exemplo, 466=7+23    466=462\frac{46}{6} = 7 + \frac{2}{3} \implies 46 \frown 6 = 46 \frown 2.

Prova

Tem-se a=bq1+r1a = bq_1 + r_1 onde q1q_1 é o quociente entre aa e bb e r1r_1 o resto da sua divisão inteira.

  1. Repare-se que se dad|a e dbd|b, então dr1d|r_1:
a=bq1+r1dk=dkq1+r1r1=d(kkq1)a = bq_1+r_1 \Leftrightarrow dk=dk'q_1+r_1 \Leftrightarrow r_1=d(k-k'q_1)
  1. Por um raciocínio análogo, se dbd|b e dr1d|r_1, então dad|a.

A partir destas duas proposições, vem:

1    divisores(a,b)divisores(b,r1);2    divisores(b,r1)divisores(a,b);1\implies \text{divisores(}a,b)\subseteq \text{divisores(}b,r_1); \\ 2\implies \text{divisores(}b, r_1)\subseteq \text{divisores(}a, b);

E a proposição inicial está provada.

Algoritmo de Euclides

Se aa e bb são inteiros não simultaneamente nulos, então existe aba \frown b.

Prova

Tome-se b=r0b = r_0.

Vem:

a=r0q1+r1r1<r0r0=r1q2+r2r2<r1r1=r2q3+r3r3<r2r2=r3q4+r4r4<r3rn=rn1qn+rnrn<rn1a = r_0q_1+r_1 \qquad r_1 < r_0 \\ r_0=r_1q_2+r_2 \qquad r_2 < r_1 \\ r_1=r_2q_3+r_3 \qquad r_3 < r_2 \\ r_2=r_3q_4+r_4 \qquad r_4 < r_3 \\ \vdots\\ r_n=r_{n-1}q_n+r_n \qquad r_n < r_{n-1} \\

Onde rn<rn1<rn2<...<r0=br_n<r_{n-1}<r_{n-2}<...<r_0=b. Dada esta inequação:

rn=rn1qn+0ernrn1=rnr_n=r_{n-1}q_n+0\quad\text{e}\quad r_n \frown r_{n-1}=r_n

pois rnr_n é divisível por rn1r_{n-1}.

Tabela para MDC

Primeiro passo é ver quantas vezes 198 cabe em 252 — 1 vez. Segundo passo é calcular o resto dessa divisão — 54. Depois, repete-se o procedimento mas desta vez com 198 e 54, e assim sucessivamente, até obtermos um resto zero. Neste caso, 18 seria o M.D.C. entre 252 e 198.

Como escrever o máximo divisor comum em fatores de 252 e 198?

Tabela

Ao invés de desenharmos a tabela na horizontal, é mais prático desenhá-la na vertical pois permite-nos obter ao mesmo tempo os coeficientes de Bézout — ou seja, os valores que satisfazem a seguinte equação:

ai=252x+198ya_i=252x+198y

Como a construir? Imaginemos que queremos o coeficiente circulado a azul. Para obtermos este coeficiente, basta pegar no que vem duas linhas acima, ou seja o laranja, e subtrai-se ao produto entre o quociente na linha de cima — qiq_i — e o valor de xi/yix_i/y_i também na linha acima. Neste caso, tem-se 1(10)=11 -(1\cdot 0)=1. Como resultado, após descobrir que 18 é o M.D.C entre 252 e 198, vem:

18=4252+(5)19818 = 4\cdot252+(-5)\cdot198

Teorema 4

Para todo a,bZa,b \in \Z não simultaneamente nulos, para todo mN1m \in \N_1, tem-se:

(m×a)(m×b)=m×(ab)(m \times a) \frown (m \times b) = m \times (a \frown b)

Números primos entre si

Dois números a,bZa,b \in \Z dizem-se primos entre si, se e só se ab=1a \frown b = 1. Esta relação pode ser representada por:

aba \bot b

Teorema 5

Se ab=da \frown b = d, então ad\frac a d e bd\frac b d são primos entre si.

Demonstração

Com d=abd = a \frown b, a=kada = k_ad e b=kbdb = k_bd

kadkbd=dk_ad \frown k_bd = d\\

Pelo Teorema 4,

d×(kakb)=dkakb=1adbd=1\cancel{d} \times (k_a \frown k_b) = \cancel{d}\\ k_a \frown k_b = 1\\ \frac a d \frown \frac b d =1\\

QED


Equações Diofantinas Lineares

"Todo o programa de computador pode ser escrito com equações diofantinas."

- Prof. José Félix

Teorema 6

Este Teorema é muito útil para as provas seguintes, não só sobre Eq. Diofantinas, mas também para quando falarmos de Congruências.

Se pN1p \in \N_1 divide a×ba \times b (a,bZa,b \in \Z), e pp é primo com bb, então pp divide aa (pap|a).

Demonstração
pb=1p \frown b = 1

Pelo Teorema 4,

paab=ap(pa)p(ab)    papa \frown ab = a\\ p|(pa) \wedge p|(ab) \implies p|a

QED

Resolução de Eq. Diofantinas

Teorema 7

Uma equação diofantina dada por:

ax+by=cax + by = c

Tem solução, se e só se dcd|c, onde d=abd = a \frown b.

Demonstração
  1. Condição Necessária

Assumindo que ax+by=cax+by=c tem solução.
Como d=abd = a \frown b, aa e bb podem ser escritos na forma:

a=kadb=kbd,ka,kbZa = k_ad \quad b=k_bd, \qquad k_a,k_b \in \Z

Substituindo na equação ax+by=cax + by = c,

kadx+kbdy=cd(kax+kby)=ck_adx + k_bdy = c\\ d(k_ax + k_by) = c

Se a equação original tem solução, podemos concluir que dcd|c

  1. Condição suficiente

Por outro lado, se dcd|c, então existe kk, tal que c=kdc = kd.
Sabe-se que existem x0,y0Zx_0,y_0 \in \Z, tais que ax0+by0=dax_0+by_0=d, uma vez que d=abd= a\frown b
Deste modo,

kax0+kby0=kd=ckax_0 + kby_0 = kd = c

Podemos então concluir que kx0kx_0 e ky0ky_0 são soluções da equação ax+by=cax+by=c.

QED


Teorema 8

Se (x0,y0)(x_0,y_0) é uma solução particular de uma equação diofantina ax+by=cax + by = c, então, o conjunto das soluções é dado por:

{x=x0+bdty=y0adt\left\{ \begin{aligned} x = x_0 + \frac b d t\\ y = y_0 - \frac a d t \end{aligned} \right.
Demonstração

Queremos encontrar um par (x,y)(x,y) tal que ax+by=cax+by=c, e sabemos que ax0+by0=cax_0+by_0=c.
Se esse par existir, ax+by=ax0+by0ax+by=ax_0+by_0.
Seja d=abd = a \frown b:

ax+by=ax0+by0a(xx0)=b(y0y)ad(xx0)=bd(y0y)ax+by=ax_0+by_0\\ a(x-x_0)=b(y_0-y)\\ \frac a d (x-x_0)=\frac b d (y_0-y)

Como adbd\frac a d \nmid \frac b d e bdad\frac b d \nmid \frac a d, uma vez que são primos entre si, tal como vimos no Teorema 5. Para existir solução, é preciso que bd(xx0)\frac b d | (x-x_0), pelo Teorema 6. Se isto se verificar, então existe um tZt \in \Z, tal que:

xx0=bdtx-x_0 = \frac b d t

logo,

x=x0+bdtx = x_0 + \frac b d t

substituindo pelo que tínhamos,

adbdt=bd(y0y)y=y0adt\frac a d \cdot \frac b d t=\frac b d (y_0-y) \\ y = y_0 - \frac a d t

QED

Exemplo

Seja dd e mm o dia e mês, respetivamente, de uma dada data e c=31d+12mc = 31d + 12m.
Se soubermos cc conseguimos chegar a mm e dd, resolvendo a equação diofantina.

No entanto, neste exemplo precisamos primeiro da data para chegar a cc. Depois iremos verificar se conseguíamos chegar à data escolhida, somente a partir de cc.

Com d=29d=29 e m=2m=2 (29 de fevereiro),

c=31(29)+12(2)=923c = 31(29) + 12(2) = 923

Vamos agora tentar chegar a dd e mm, apenas a partir de cc.

  1. Algoritmo de Euclides (estendido)
iaiqidimi031101122012711235113422255125136031(5)+12(13)=131((5)923)+12(13923)=192331(4615)+12(11999)=923\begin{array}{c|c|c|c|} i & a_i & q_i & d_i & m_i\\ \hline 0 & 31 & & 1 & 0\\ 1 & 12 & 2 & 0 & 1\\ 2 & 7 & 1 & 1 & -2\\ 3 & 5 & 1 & -1 & 3\\ 4 & 2 & 2 & 2 & -5\\ 5 & 1 & 2 & -5 & 13\\ 6 & 0 \end{array}\\ 31(-5) + 12(13) = 1\\ 31((-5)\cdot 923) + 12(13\cdot 923) = 1\cdot 923\\ 31(-4615) + 12(11999) = 923
  1. Calcular a solução desejada.

Sendo (m,d)(m,d) o mês e dia,

{d=4615+121tm=11999311t1d311m12 14615+12t31461612t464611543(384.67)t23236(387.2)Como tZ,t=385t=386t=387\begin{cases} d = -4615 + \frac{12}{1} t\\ m = 11999 - \frac{31}{1} t \end{cases}\\ 1\leq d\leq 31\quad \wedge \quad1 \leq m\leq 12\\~\\ 1 \leq -4615 + 12t\leq 31\\ 4616 \leq 12t\leq 4646\\ \frac{1154}3 (\approx 384.67) \leq t\leq \frac{2323}{6} (\approx 387.2)\\ \text{Como } t \in \Z,\quad t =385 \vee t=386 \vee t=387

Agora verificamos para que valor de tt é que 1m121 \leq m \leq 12

  • t=385t =385
m=1199931(385)=64m = 11999 - 31(385) = 64
  • t=386t = 386
m=1199931(386)=33m = 11999 - 31(386) = 33 \quad
  • t=387t=387
m=1199931(387)=2m = 11999-31(387) = 2 \quad \checkmark

Por fim,

{d=4615+12(387)m=1199931(387){d=29m=2\begin{cases} d = -4615 + 12(387) \\ m = 11999 - 31(387) \end{cases}\\ \begin{cases} d = 29\\ m = 2 \end{cases}\\

A data obtida foi 29 de fevereiro, tal como esperado.