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

Referências BibliográficasEditar

[1] E. Lozansky, C. Rousseau : Winning Solutions, Springer-Verlag, New York, 1996.