Definição 14.1 Sejam \(a\) e \(b\) números inteiros não simultaneamente iguais a zero. Definimos o maior divisor comum de \(a\) e \(b\) como sendo o inteiro \(d\) que satisfaz as seguintes propriedades:
\(d\geq 0\);
\(d|a\) e \(d|b\);
se \(c\) é um inteiro tal que \(c|a\) e \(c|b\) então \(c|d\).
Não é imediatamente claro da definição que o maior divisor comum existe (isso será verificado depois). No entanto, o seguinte lema é válido
Lema 14.1 Se o maior divisor comum de dois números \(a,b\in\Z\) existir, então ele é único
Comprovação. Se \(d_1\) e \(d_2\) são ambos maiores divisores comuns de \(a\) e \(b\), então a definição implica que \(d_1|d_2\) e \(d_2|d_1\). Ora temos por um lema anterior que \(d_1=\pm d_2\), mas como \(d_1\) e \(d_2\) são não negativos, isso é possível apenas quando \(d_1=d_2\)
O maior divisor comum de \(a\) e \(b\) (quando existir) será denotado por \(\mdc ab\).
Lema 14.2 As seguintes afirmações são verdadeiras para \(a,b\in\Z\).
Se existe \(\mdc ab\), então existe \(\mdc ba\) e os dois são iguais.
Se existe \(\mdc ab\), então existe \(\mdc{\pm a}{\pm b}\) e todos são iguais.
Para todo \(a\neq 0\), existe \(\mdc a0\) e \(\mdc a0=|a|\).
Para todo \(a\neq 0\), existe \(\mdc aa\) e \(\mdc aa=|a|\).
Comprovação. Exercício
O \(\mdc 00\) não tá definido.
Se \(a\) e \(b\) são inteiros tais que \(\mdc ab=1\), então dizemos que \(a\) e \(b\) são primos entre si ou que eles são coprimos.
Lema 14.3 Sejam \(a,b,q\) números inteiros. Então existe \(\mdc ab\) se e somente se existe \(\mdc b{a+qb}\). Quando os dois MDCs existirem, então \[
\mdc ab=\mdc b{a+qb}.
\]
Comprovação. Assuma primeiro que existe \(d=\mdc ab\). Vamos provar que \(\mdc b{a+qb}=d\) verificando as propriedades 1.-3. na definição do MDC.
Como \(d=\mdc ab\), ele é não negativo, então propriedade 1. está OK para \(d\).
Como \(d\mid a\) e \(d\mid b\), temos que \(d\mid b\) e \(d\mid a+qb\). Ou seja, propriedade 2. está válida para \(d\).
Assuma que \(c\mid b\) e \(c\mid a+qb\). Então \(c\mid a+qb-qb=a\) e assim \(c\mid a\). Como \(d=\mdc ab\), obtemos que \(c\mid d\) e a propriedade 3. também está certa para \(d\).
Assim podemos concluir que \(d=\mdc b{a+qb}\). A outra direção quando a suposição é que existe \(\mdc b{a+qb}\) é análoga.
Corolário 14.1 Sejam \(a,b\in\Z\) com \(b\neq 0\) e escreve \(a=qb+r\) com \(0\leq r<|b|\) como no Teorema de Divisão de Euclides. Então existe \(\mdc ab\) se e somente se existe \(\mdc br\). Quando os dois MDCs existirem, eles são iguais
Comprovação. Segue do lema anterior
Exemplo 14.1 O lema anterior pode ser usado para determinar o MDC de dois números naturais do modo seguinte. Sejam, por exemplo, \(a=115\) e \(b=25\). Escreva \[
115=4\cdot 25+15
\] Logo \(\mdc {115}{25}\) e \(\mdc{25}{10}\) existem (ou não) simultaneamente e, se existirem, são iguais. Depois escreva \[
25=1\cdot 15+10.
\] Concluímos que \(\mdc{25}{10}\) e \(\mdc{10}{5}\) existem (ou não) simultaneamente e, se existirem, são iguais. Depois \[
15=1\cdot 10+5
\] e \[
10=2\cdot 5+0
\] que implica que \(\mdc{10}5\) e \(\mdc 50\) existem (ou não) simultaneamente e, se existirem, são iguais. Mas agora sabe-se que \(\mdc 50\) existe e \(\mdc 50=5\). Logo \[\begin{align*}
\mdc {115}{25}&=\mdc{25}{15}=\mdc{15}{10}=\mdc{10}{5}\\&=\mdc 50=5.
\end{align*}\] Esta conta segue essencialmente o Algoritmo de Euclides que será o conteúdo da matéria seguinte
14.2 O algoritmo de Euclides
Sejam \(a,b\in\N_0\) com \(b<a\). O resultado provado no final da página anterior sugere o seguinte processo recursivo para calcular o \(\mbox{mdc}(a,b)\):
Passo 1: Se \(b=0\), então \(\mdc ab=a\).
Passo 2: Se \(b \neq 0\) então use o Teorema de Divisão de Euclides para escrever \(a=qb+r\) com \(r\in\{0,\ldots,b-1\}\).
Passo 3:\(\mdc ab=\mdc br\).
O processo funciona, pois no Passo 3., os números \(b\) e \(r\) são menores que \(a\) e \(b\). Logo, mais cedo ou mais tarde, o processo vai chegar até uma situação quando \(b=0\) e neste caso o valor do \(\mdc ab\) será igual a \(a\) pelo Passo 1. Veja o exemplo na página anterior para uma computação detalhada seguindo este processo.
Este algoritmo pode ser implementado em Python com a seguinte função recursiva.
def MDC_recursivo( a, b ):if b ==0:return aelse:return MDC_recursivo( b, a % b )
Para melhor analisarmos o algoritmo, nós escrevemos o processo em uma maneira linear (não recursiva). O processo descrito abaixo é chamado Algoritmo de Euclides. Sejam \(a,b\) como acima. \[
\begin{align*}
r_{-1}&=a\\
r_0&=b\\
a=r_{-1}&=q_1b+r_1\quad 0<r_1<b\\
b=r_0&=q_2r_1+r_2\quad 0<r_2<r_1\\
r_1&=q_3r_2+r_3\quad 0<r_3<r_2\\
&\vdots\\
r_{i-1}&=q_{i+1}r_{i}+r_{i+1}\quad 0<r_{i+1}<r_{i}\\
r_{i}&=q_{i+2}r_{i+1}+r_{i+2}\quad 0<r_{i+2}<r_{i+1}\\
&\vdots\\
r_{d-2}&=q_{d}r_{d-1}+r_{d}\quad 0<r_{d}<r_{d-1}\\
r_{d-1}&=q_{d+1}r_d+0
\end{align*}
\]
A sequência dos restos calculados satisfaz as desigualdades \[
a>b>r_1>r_2>\cdots>r_i>\cdots>r_d>r_{d+1}=0.
\] Em outras palavras, a sequência dos restos é uma sequência decrescente de números positivos. Note que tal sequência sempre atinge o número zero em um número finitos de passos; ou seja, existe algum \(d\) tal que \(r_{d+1}=0\). Pelo raciocínio acima, obtemos que \[\begin{align*}
\mdc ab&=\mdc b{r_1}=\mdc{r_1}{r_2}=\cdots=\mdc{r_i}{r_{i+1}}=\cdots\\&=\mdc{r_{d-1}}{r_d}=\mdc{r_d}0=r_d.
\end{align*}\]
Isso justifica o seguinte resultado.
Lema 14.4 Se \(a,b\in \N_0\) tais que \(b\neq 0\), então o último resto não nulo \(r_d\) calculado pelo Algoritmo de Euclides é igual a \(\mdc ab\). O algoritmo termina depois de um número finito de passos.
Note que nos resultados acima, nós assumimos que \(a,b\) são números não negativos. No entanto, o procedimento pode ser usado mesmo quando \(a\) ou \(b\) (ou os dois) são negativos, pois neste caso, simplesmente podemos trocar o número negativo pelo seu simétrico (que vai ser positivo) pelo fato que \(\mdc ab=\mdc{\pm a}{\pm b}\).
Em particular nós finalmente conseguimos concluir o seguinte resultado sobre a existência do \(\mdc ab\).
Corolário 14.2 Se \(a,b\in\Z\) tais que \((a,b)\neq (0,0)\), então existe \(\mdc ab\).
O procedimento acima pode também ser implementado em Python com a seguinte função.
def MDC(a,b):while b !=0: a, b = b, a % b return a
Uma outra consequência do Algoritmo de Euclides é o seguinte resultado extremamente útil e bem conhecido.
Teorema 14.1 Sejam \(a,b\in\Z\) com \((a,b)\neq 0\). Então existem \(u,v\in\Z\) tais que \[
\mdc ab=ua+vb.
\] Em particular, se \(a\) e \(b\) são primos entre si, então existem \(u,v\in\Z\) tais que \[
1=ua+vb.
\]
Comprovação. Nós podemos assumir sem perda de generalidade que \(0<b<a\). Com esta suposição, podemos executar o algoritmo de Euclides para \(a\) e \(b\).
Afirmamos que, para todo \(i\geq 1\), o resto \(r_i\) pode ser escrito como \(u_ia+v_ib\) com coeficientes \(u_i,v_i\in\Z\). Verificaremos a afirmação por indução em \(i\). A afirmação está verdadeira para \(i=1\), pois \[
r_1=a-q_1b\quad\text{e assim}\quad u_1=1,\ v_1=-q_1.
\] Assuma que \(i\geq 1\) e, para \(j\leq i\) existem \(u_j,v_j\in \Z\) tais que \[
r_j=u_ja+v_jb.
\] Ora, segue da equação para \(r_{i-1}\) que \[\begin{align*}
r_{i+1}&=r_{i-1}-q_{i+1}r_{i}=u_{i-1}a+v_{i-1}b-q_{i+1}(u_{i}a+v_{i}b)\\&=
(u_{i-1}-q_{i+1}u_i)a+(v_{i-1}-q_{i+1}v_i)b.
\end{align*}\] Ou seja, podemos tomar \[
u_{i+1}=u_{i-1}-q_{i+1}u_i\quad\mbox{e}\quad v_{i+1}=v_{i-1}-q_{i+1}v_i.
\tag{14.1}\]
Agora, temos que \[
\mdc ab=r_d=u_da+v_db
\] e o teorema está válido com \(u=u_d\) e \(v=v_d\).
Note que a demonstração acima dá um algoritmo para calcular os coeficientes \(u,v\) e este algoritmo pode ser executado em paralelo com a computação do \(\mdc ab\). O algoritmo que calcula o \(\mdc ab\) junto com os coeficientes \(u,v\) tais que \[
\mdc ab=ua+vb
\] é geralmente chamado Algoritmo Estendido de Euclides. Analizando a demonstração do Teorema 14.1, a computação do \(\mdc ab\) e dos coeficientes \(u\) e \(v\) pode ser organizada em uma tabela. As linhas da tabela serão rotuladas por \(r\), \(q\), \(u\) e \(v\).
Coloque na primeira coluna da tabela o valor de \(a\) na linha \(r\), e os valores \(1\) e \(0\) nas linhas \(u\) e \(v\), respetivamente. Deixe a cela na linha \(q\) branca.
Coloque na segunda coluna da tabela o valor de \(b\) na linha \(r\), e os valores \(0\) e \(1\) nas linhas \(u\) e \(v\), respetivamente. Deixe a cela na linha \(q\) branca.
Assumindo que a tabela tem pelo menos 2 colunas preenchidas, faça as seguintes computações até obter \(0\) na linha \(r\). Denote por \(r_{-2}\) e \(r_{-1}\) os valores na linha \(r\) e na penúltima coluna e na última coluna já preenchida e defina \(u_{-2}\), \(u_{-1}\), \(v_{-2}\), \(v_{-1}\) de maneira análoga.
Usando o Teorema de Divisão de Euclides (Teorema 11.1), calcule o resto \(r\) e o quociente \(q\) de \(r_{-2}\) por \(r_{-1}\) e coloque o \(r\) e \(q\) nas linhas \(r\) e \(q\) da próxima coluna da tabela.
Calcule \(u=u_{-2}-qu_{-1}\) (o penúltimo valor de \(u\) menos \(q\) vezes o último) e \(v=v_{-2}-qv_{-1}\) (o penúltimo valor de \(v\) menos \(q\) vezes o último) e coloque estes valores nas linhas \(u\) e \(v\) na próxima coluna da tabela. Note que este passo está baseado na Equação 14.1
Quando o valor da linha \(r\) é igual a zero, o valor \(r\) da penúltima coluna é o \(\mdc ab\) o os valores na linhas \(u\) e \(v\) são tais que \[
\mdc ab = ua+vb.
\]
Exemplo 14.2 Vamos executar este procedimento simples com \(a=115\) e \(b=25\) repetindo o exemplo Exemplo 14.1.
r
115
25
15
10
5
0
q
4
1
1
2
u
1
0
1
-1
2
-5
v
0
1
-4
5
-9
23
Da tabela, obtemos que \[
\mdc {115}{25}=5=2\cdot 115-9\cdot 25.
\]
A seguinte é uma implementação simples do Algoritmo Estendido em Python.
def XMDC(a,b): prevu, u =1, 0; prevv, v =0, 1while b !=0: q = a//b u, prevu = prevu - q*u, u v, prevv = prevv - q*v, v a, b = b, a % breturn a, prevu, prevv
14.3 As propriedades do MDC
O último resultado na página do Algoritmo de Euclides implica várias propriedades importantes do MDC.
Lema 14.5 Sejam \(a,b,c\in\Z\setminus\{0\}\). As seguintes afirmações são verdadeiras.
Se \(c\mid ab\) e \(\mdc bc=1\), então \(c\mid a\).
Se \(\mdc ac=\mdc bc=1\), então \(\mdc {ab}c=1\).
Se \(\mdc ab=d\), então \(\mdc{a/d}{b/d}=1\).
Se \(a\mid c\) e \(b\mid c\), então \((ab/\mdc ab)\mid c\).
Se \(a\mid c\), \(b\mid c\) e \(\mdc ab=1\), então \(ab\mid c\).
Comprovação.
Como \(\mdc bc=1\), existem \(u,v\in\Z\) tais que \(ub+vc=1\). Multiplique esta igualdade por \(a\) para obter \[
a=uab+vac.
\] Como \(c\mid ab\), o lado direito da última equação é divisível por \(c\), e assim \(c\mid a\).
Seja \(d=\mdc{ab}c\). Como \(\mdc ac=1\), existem \(u,v\in\Z\) tais que \[
1=ua+vc.
\] Multiplique os dois lados desta igualdade por \(b\) e obtenha \[
b=uab+vbc.
\] Pela definição de \(d\), tem-se que \(d\mid c\) e \(d\mid ab\). Logo, pela última igualdade, obtemos que \(d\mid b\). Logo \(d\mid \mdc bc=1\); ou seja \(d=\mdc{ab}c=1\).
Seja \(d=\mdc ab\). Existem inteiros \(q_1,q_2\in\Z\) tais que \[
a=q_1d\quad\mbox{e}\quad b=q_2d.
\] Além disso existem \(u,v\in\Z\) tais que \[
d=ua+vb=uq_1d+vq_2d.
\] Dividindo os dois lados por \(d\), obtemos que \[
1=uq_1+vq_2.
\] Note que se \(d_1=\mdc{q_1}{q_2}\), então \(d_1\mid 1\), logo \(d_1=1\). Portanto \[
\mdc{a/d}{b/d}=\mdc{q_1}{q_2}=1.
\]
Seja \(d=\mdc ab\). Existem \(u,v\in\Z\) tais que \[
d=ua+vb.
\] Multiplicando por \(c\), \[
cd=uac+vbc.
\] Pelas condições, existem inteiros \(q_1\), \(q_2\) tais que \(c=aq_1=bq_2\) e assim \[
dc=uabq_2+vbaq_1=ab(uq_2+vq_1);
\] ou seja \[
c=\frac{ab}d(uq_2+vq_1).
\] Isso implica que \(ab/d\mid c\).