FANDOM


Sejam $ a_1,a_2,...,a_n $ inteiros não nulos. O menor número natural que é divisível por todos eles é chamado de mínimo múltiplo comum de $ a_1,a_2,...,a_n $. Denotaremos ele por $ \operatorname{mmc}(a_1,a_2,...,a_n) $ ou $ [a_1,a_2,...,a_n] $.

Propriedades Editar

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

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

Esmeralda e Jade participam de um jogo: Esmeralda faz uma lista de $ 2011 $ inteiros positivos, mas não mostra para Jade. Jade deve descobrir o produto dos números. Para isso, ela deve perguntar qual é o $ \operatorname{mdc} $ ou o $ \operatorname{mmc} $ dos números de qualquer subconjunto com mais de um elemento dos $ 2011 $ (por exemplo, qual é o $ \operatorname{mdc} $ do $ 1^{\circ} $, $ 2^{\circ} $, $ 10^{\circ} $ e $ 2000^{\circ} $ números da sua lista?" ou "qual é o $ \operatorname{mmc} $ de todos os números da lista?"). Jade pode fazer quantas perguntas quiser, mas só obtém as respostas (corretas) de Esmeralda após fazer todas as perguntas (Esmeralda é generosa e também e diz qual é a resposta de cada pergunta). Jade então pode fazer qualquer uma das quatro operações fundamentais (soma, subtração, multiplicação e divisão) com os números que obtiver de Esmeralda. Jade consegue uma estratégia para obter o produto dos $ 2011 $ números de Esmeralda? Justifique sua resposta.

Solução: Como conseguir $ ab $ a partir de $ \operatorname{mdc}(a,b) $ e $ \operatorname{mmc}(a,b) $? Basta usarmos que $ \operatorname{mdc}(a,b).\operatorname{mmc}(a,b)=a.b $. Mas e quando não conseguimos juntar pares? Precisamos saber lidar com essa pergunta com três números.

Lema:

$ abc=\frac{\operatorname{mmc}(a,b,c).\operatorname{mdc}(a,b).\operatorname{mdc}(a,c).\operatorname{mdc}(b,c)}{\operatorname{mdc}(a,b,c)} $.

Prova: Seja $ e_p(x) $ o maior expoente natural do número primo $ p $ tal que $ p^{e_p(x)}|x $. Precisamos provar que

$ \displaystyle{e_p(abc)=e_p(\frac{\operatorname{mmc}(a,b,c).\operatorname{mdc}(a,b).\operatorname{mdc}(a,c).\operatorname{mdc}(b,c)}{\operatorname{mdc}(a,b,c)})} (*) $,

para todo $ p $ primo. Considere $ \alpha_1=e_p(a) $, $ \alpha_2=e_p(b) $ e $ \alpha_3=e_p(c) $. Observe que

$ e_p(abc)=e_p(a)+e_p(b)+e_p(c)=\alpha_1+\alpha_2+\alpha_3 $.

Além disso, se supormos sem perda de generalidade que $ \alpha_1 \leq \alpha_2 \leq \alpha_3 $, então

$ e_p(\frac{\operatorname{mmc}(a,b,c).\operatorname{mdc}(a,b).\operatorname{mdc}(a,c).\operatorname{mdc}(b,c)}{\operatorname{mdc}(a,b,c)})= $

$ =e_p(\operatorname{mmc}(a,b,c))+e_p(\operatorname{mdc}(a,b))+e_p(\operatorname{mdc}(a,c))+e_p(\operatorname{mdc}(b,c))-e_p(\operatorname{mdc}(a,b,c))= $

$ =\max \{\alpha_1,\alpha_2,\alpha_3\}+\min \{\alpha_1,\alpha_2\}+\min \{\alpha_1,\alpha_3\}+\min\{\alpha_2,\alpha_3\}-\min\{\alpha_1,\alpha_2,\alpha_3\}= $

$ =\alpha_3+\alpha_1+\alpha_1+\alpha_2-\alpha_1= $

$ =\alpha_1+\alpha_2+\alpha_3. $

Isto prova $ (*) $ e, portanto, o lema.

$ \blacksquare $

Voltemos ao exercício em si. Sejam $ a_1,a_2,\dots,a_n $ os números. Vamos pegá-los aos pares. Como $ a_1 $ e $ a_2 $, como conseguir $ a_1a_2 $? Basta tomarmos $ \operatorname{mdc}(a_1,a_2) $ e $ \operatorname{mmc}(a_1,a_2) $ e multiplicarmos resultado.

Da mesma forma, podemos pegar $ \operatorname{mdc}(a_3,a_4),\dots \operatorname{mdc}(a_{2007},a_{2008}) $ e $ \operatorname{mmc}(a_3,a_4),\dots \operatorname{mmc}(a_{2007},a_{2008}) $ e com isso conseguimos obter $ a_3a_4,\dots,a_{2007}a_{2008} $. Ao multiplicarmos isto, teremos $ a_1a_2a_3a_4\dots a_{2007}a_{2008} $. E quanto a $ a_{2009},a_{2010},a_{2011} $? Basta usarmos aplicarmos o lema a eles:

$ abc=\frac{\operatorname{mmc}(a_{2009},a_{2010},c).\operatorname{mdc}(a_{2009},a_{2010}).\operatorname{mdc}(a_{2009},a_{2011}).\operatorname{mdc}(a_{2010},a_{2011})}{\operatorname{mdc}(a_{2009},a_{2010},a_{2011})} $.

Se Jade multiplicar este número com o resultado obtido anteriormente, ela obterá o resultado.