FANDOM


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.

PropriedadesEditar

(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 Editar

Se $ a>b $, então $ \operatorname{mdc}(a,b)=\operatorname{mdc}(a-b,b) $.

Algoritmo de Euclides EstendidoEditar

É 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 Editar

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) Editar

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) Editar

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.

BibliografiaEditar

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