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.

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 $ab=c^2$ e $\operatorname{mdc}(a,b)=1$, então $a$ e $b$ são quadrados perfeitos.

Lema de Euclides

Se $a > b$, 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 (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

$(p+q)|(p+q) \Rightarrow (p+q)|(p+q)(p-q)=p^2-q^2$.

Com isso,

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

Analogamente, $(p+q)|2q^2$. Com isso,

$(p+q)|\operatorname{mdc}(2p^2,2q^2)=2\operatorname{mdc}(p^2,q^2)$.

E como lidar com $\operatorname{mdc}(p^2,q^2)$? Vamos dividir em casos?

1° Caso: $p$ e $q$ são diferentes.

Aqui, $\operatorname{mdc}(p^2,q^2)=1$. Desta maneira,

$(p+q)|2 \Rightarrow p+q \leq 2$.

Absurdo, pois $p,q \geq 2$, já que eles são primos. Com isso, este caso não nos dá nenhum $r$ inteiro.

2° Caso: $p$ e $q$ são iguais.

Neste caso, $\operatorname{mdc}(p^2,q^2)=p^2=q^2$. Assim, $r=p=q$, ou seja, $r$ é primo.

Bibliografia

• E. Lozansky, C. Rousseau : Winning Solutions, Springer-Verlag, New York, 1996.