Máximo Divisor Comum

Sejam $a$ e $b$ inteiros, com algum deles diferente de zero. O máximo divisor comum entre $a$ e $b$ será o maior número natural $d$ tal que $d | a$ e $d|b$ . Este número pode ser representado por $\operatorname{mdc}(a,b)$ ou simplesmente por $(a,b)$ .

Se $\operatorname{mdc}(a,b)=1$ , diremos que a e b são primos entre si ou que eles são relativamente primos.

Observação

A expressão $\operatorname{mdc}(0,0)$ não está bem definida. Por isso que não definição é necessário que algum dos inteiros seja diferente de zero.

Propriedades

(i) Se $a|b$ e $a|c$ , então $a|\operatorname {mdc} (b,c)$ .

(ii) $\operatorname{mdc}(a,b)=\operatorname{mdc}(-a,b)=\operatorname{mdc}(a,-b)=\operatorname{mdc}(-a,-b)$ .

(iii) Se $a$ é diferente de zero, então $\operatorname{mdc}(a,a)=|a|$ .

(iv) Se $a$ é diferente de zero, então $\operatorname{mdc}(a,0)=|a|$ .

(v) Se $c$ é diferente de zero, então $\operatorname{mdc}(ca,cb)=|c|\operatorname{mdc}(a,b)$ .

(vi) Se $p$ é primo, então $\operatorname{mdc}(a,p)=1$ ou $\operatorname{mdc}(a,p)=p$ .

(vii) Se $ab=c^2$ e $\operatorname{mdc}(a,b)=1$ , então $a$ e $b$ são quadrados perfeitos.

Lema de Euclides

Sejam $a$ e $b$ inteiros, com algum deles diferente de zero. Então $\operatorname{mdc}(a,b)=\operatorname{mdc}(a-b,b)$ .

Algoritmo de Euclides Estendido

É um método de calcularmos o máximo divisor comum entre dois números. Ele se baseia no seguinte resultado:

Proposição: Sejam $a$ e $b$ inteiros positivos com $a > b$ . Se o resto da divisão de $a$ por $b$ for igual a $r$ , então

$\operatorname{mdc}(a,b)=\operatorname{mdc}(a,r).$

Exemplo

Prove que se $b|c$ , então $\operatorname{mdc}(a,b)|\operatorname{mdc}(a,c)$ .

Solução: Considere $x=\operatorname{mdc}(a,b)$ e $y=\operatorname{mdc}(a,c).$ Observe que, pela definição de máximo divisor comum, $x|a$ e $x|b$ . Mas, por hipótese, $b|c$ , de onde segue, pela transitividade, $x|c$ . Com isso, $x|\operatorname{mdc}(a,c)$ .

Exemplo (Cone Sul 1999)

Achar o menor inteiro positivo $n$ tal que as $73$ frações

$\frac{19}{n+21},\frac{20}{n+22},\frac{21}{n+23},\dots,\frac{91}{n+93}$

sejam todas irredutíveis.

Solução: Uma fração $\frac{a}{b}$ é irredutível se, e somente se, $\operatorname{mdc}(a,b)=1$ .

Desta forma, $\frac{a}{b}$ é irredutível se, e somente se, $\frac{a}{b-a}$ (pois os lema de Euclides nos diz que $\operatorname{mdc}(a,b)=\operatorname{mdc}(a,b-a)$ ). Se aplicarmos isto em todas as frações, o problema se transforma em encontrar o menor $n$ inteiro positivo tal que

$\frac{19}{n+2},\frac{20}{n+2},\frac{21}{n+2},\dots,\frac{91}{n+2}$

sejam todas irredutíveis. Conseguimos pelo menos algum valor de $n$ que satisfaça isso? Se tomarmos $n$ de tal forma que $n+2$ seja primo e maior que $91$ , então ele faz com que todas as frações sejam irredutíveis. Um número nessas condições é $n=95$ . Vejamos que ele é o menor possível, isto é, para todo $n \leq 94$ , alguma das frações acima é redutível.

Um caso é quando alguma delas é $1$ . Isto acontece para $19 \leq n+2 \leq 91$ , isto é, $17 \leq n \leq 89$ .

Já para o caso em que $n+2<19$ , isto é, $n<17$ , existirá algum múltiplo de $n+2$ entre $19$ e $91$ e com isso teremos pelo menos uma fração redutível para cada um desses valores de $n$ .

E quanto ao caso em que $90 \leq n \leq 94$ ? Observe que $n+2$ não pode ser par, pois isto implicaria $\frac{20}{n+2}$ redutível. Resta analisarmos as possibilidades $n=91$ ou $93$ .

$n=91$

Neste caso, $\frac{31}{n+2}$ será redutível.

$n=39$

Aqui, $\frac{20}{n+2}$ será redutível.

Portanto, $n=95$ é o menor valor que satisfaz as condições do enunciado.

Exemplo (OBM 2007 - 3ª Fase - Nível 2)

Mostre que existe um inteiro positivo $a$ tal que $\frac{a^{29}-1}{a-1}$ tem pelo menos $2007$ fatores primos distintos.

Solução: A estratégia aqui é conseguir alguma transformação de $a$ que aumente pelo menos um fator primo distinto dos que já existem. E qual transformação será essa? Trocaremos $a$ por $a^2$ . Repare também que nós podemos escolher o próprio $a$ . Então, podemos impor condições sobre ele, na hora que quisermos.

Observe que

$\frac{(a^2)^{29}-1}{a^2-1}=\frac{(a^{29})^2-1}{a^2-1}=\frac{(a^{29}+1)}{(a+1)}.\frac{(a^{29}-1)}{(a-1)}$ .

Se mostrarmos que $\operatorname{mdc}(\frac{(a^{29}+1)}{(a+1)},\frac{(a^{29}-1)}{(a-1)})=1$ , veremos que existe um fator primo a mais na expressão ao trocarmos $a$ por $a^2$ . Mas estes números são inteiros?

Sim, pois

$a^{29}+1=(a+1)(a^{28}-a^{27}+\dots-a+1)$

$a^{29}-1=(a-1)(a^{28}+a^{27}+\dots+a+1)$ ,

onde segue que $\frac{(a^{29}+1)}{(a+1)}$ e $\frac{(a^{29}-1)}{(a-1)}$ são inteiros. Se provarmos que $(a^{29}+1)$ e $(a^{29}-1)$ são primos entre si, isto é, não fatores primos em comum, então $\frac{(a^{29}+1)}{(a+1)}$ e $\frac{(a^{29}-1)}{(a-1)}$ também terão, pois $\frac{(a^{29}+1)}{(a+1)}$ e $\frac{(a^{29}-1)}{(a-1)}$ são divisores de $(a^{29}+1)$ e $(a^{29}-1)$ , respectivamente.

E pelo Lema de Euclides,

$\operatorname{mdc}(a^{29}+1,a^{29}-1)=\operatorname{mdc}(2,a^{29}-1)$ .

Lembre-se: podemos escolher o nosso próprio $a$ . E esse $\operatorname{mdc}$ é igual a $1$ se, e somente se, $a$ é par. Logo, podemos impor essa condição sobre $a$ . Neste caso, $(a^{29}+1)$ e $(a^{29}-1)$ serão primos entre si e o mesmo acontecerá com $\frac{(a^{29}+1)}{(a+1)}$ e $\frac{(a^{29}-1)}{(a-1)}$ .

Portanto, para $a$ é par, se trocarmos $a$ por $a^2$ , teremos pelo menos um fator primo a mais na nossa conta. Ao fazermos esta troca $2007$ vezes, teremos que o número obtido terá, pelo menos, $2007$ fatores a mais que o original.

Logo, se começarmos com $a=3$ , o número $3^{2^{2017}}$ irá satisfazer as condições do enunciado.

Exemplo (OBM 2008 - 3ª Fase - Nível 2)

Mostre que se $p,q$ são inteiros positivos primos tais que $r=\frac{p^2+q^2}{p+q}$ é inteiro, então $r$ é primo.

Solução: Vejamos os casos em que $\frac{p^2+q^2}{p+q}$ é inteiro. Para isto, vejamos quando

$(p+q)|(p^2+q^2)$ .

Façamos uma combinação linear para podermos ficar com um termo a menos. Neste caso, como podemos fazer aparecer de outra maneira $p^2$ ou $q^2$ ? Basta notarmos que