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.

Observação Editar

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.

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

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

Prove que se $ \operatorname{mdc}(a,b)=1 $, então $ \operatorname{mdc}(a^m,b^n)=1 $, para quaisquer $ m $ e $ n $ inteiros positivos.

Solução: Suponha, por absurdo, que $ \operatorname{mdc}(a^m,b^n)=d $ e $ d>1 $. Então existe um primo $ p $ tal que $ p|d $. Pela definição de máximo divisor comum, $ d|a^m $ e $ d|b^n $. Com isso, $ p|a^m $ e $ p|b^n $. Desta forma, $ p|a $ e $ p|b $, de onde segue que $ p|\operatorname{mdc}(a,b)=1 $. Absurdo. Logo, $ \operatorname{mdc}(a,b)=1 $.

Exemplo (Cone Sul 1999) Editar

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