Sejam $a,b\in \Z$. Dizemos que $b$ divide $a$ ou que $a$ é um múltiplo de $b$ se existe $q\in\Z$, tal que $bq=a$. Usamos a notação $b|a$ para indicar que $b$ divide $a$.
- $\pm a|a$ e $\pm 1|a$ para todo inteiro $a$.
- $a|0$ para todo inteiro $a$, mas se $0|a$ então $a=0$. Em particular $0|0$.
As seguintes propriedades são válidas.
- Se $a|b$ e $b|a$ então $b=\pm a$.
- Se $a|b$ e $b|c$ então $a|c$.
- Se $a|b$ e $a|c$ então $a|(b\pm c)$.
- Se $a|b$ e $c$ é um inteiro então $a|bc$.
Exercício.
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. No entanto, segue da definição que se ele existir, então ele deve ser único. Isso porque se $d_1$ e $d_2$ são mdcs de $a$ e $b$, então a definição implica que $d_1|d_2$ e $d_2|d_1$. Ora temos pelo 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$ será denotado por $\mdc ab$.
É claro que $\mdc ab=\mdc ba$ e que $\mdc ab=\mdc{\pm a}{\pm b}$. A definição também implica que $\mdc a0=|a|$ para todo $a\neq 0$.
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.
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 $\mdc ab=\mdc br$ (assumindo que existem estes mdcs).
Seja $d=\mdc ab$. Afirmamos que $\mdc br=d$. Primeiro, $d\geq 0$ pela definição de mdc (propriedade 1. do mdc). Como $d=\mdc ab$, temos que $d|a$ e $d|b$. Pelo lema anterior, isto implica que $d|(a-qb)=r$. Logo $d|b$ e $d|r$ (propriedade 2. do mdc).
Assuma que $c|b$ e $c|r$. Então, $c|(bq+r)=a$, então $c|a$ e $c|b$. Pela definição de mdc, temos que $c|d$ (propriedade 3. do mdc). Portanto $d=\mdc br$.
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+10
\]
para concluir que $\mdc {115}{25}=\mdc{25}{10}$. Depois escreva
\[
25=2\cdot 10+5
\]
e obtenha que $\mdc{25}{10}=\mdc{10}{5}$.
Depois
\[
10=2\cdot 5+0
\]
que implica que $\mdc{10}5=\mdc 50=5$. Logo
\[
\mdc {115}{25}=\mdc{25}{10}=\mdc{10}{5}=\mdc 50=5.
\]
Esta conta segue essencialmente o Algoritmo de Euclídes que será o conteúdo da semana seguinte.
\[
115=4\cdot 25+10
\]
para concluir que $\mdc {115}{25}=\mdc{25}{10}$. Depois escreva
\[
25=2\cdot 10+5
\]
e obtenha que $\mdc{25}{10}=\mdc{10}{5}$.
Depois
\[
10=2\cdot 5+0
\]
que implica que $\mdc{10}5=\mdc 50=5$. Logo
\[
\mdc {115}{25}=\mdc{25}{10}=\mdc{10}{5}=\mdc 50=5.
\]
Esta conta segue essencialmente o Algoritmo de Euclídes que será o conteúdo da semana seguinte.