Question

(4) Prove que mdc(n, 2n + 1) = 1, qualquer que seja o inteiro n.​

Answer 1

Em matemática, o maior número que divide exatamente dois ou mais números ao mesmo tempo é chamado de máximo divisor comum ou mdc. Como estamos falando do maior número, levaremos em consideração apenas os divisores positivos. Também podemos dizer que o máximo divisor comum de dois números "A" e "B", é o maior número que divide ambos, tanto o número A quanto o número B.

Para encontrar o máximo divisor comum (mdc), dividimos cada número em fatores primos. A seguir, destacamos os fatores comuns. A seguir, em cada um dos comuns, escolhemos o fator com o menor expoente e, por fim, multiplicamos os fatores escolhidos.

Outra forma de calcular o máximo divisor comum (mdc) é pelo método do algoritmo de Euclides porque em Elementos, Euclides explica que o máximo divisor comum de dois números pode ser encontrado dividindo o maior número pelo menor. Se a divisão for exata, o mdc. é o menor número. Se a divisão não for exata, o resto é tomado e dividido quantas vezes forem necessárias para chegar a uma divisão sem resto. O mdc é o último número pelo qual pode ser dividido.

Para provar que o máximo divisor comum (mdc) entre n e 2n +1 é igual a 1 (um) ou seja, $\red{\displaystyle mdc\left(n,~2n+1\right) = 1}$ podemos confiar em alguns desses dois métodos e algumas propriedades que o mdc também possui.

Para a prova desta propriedade, vamos usar o método do algoritmo de Euclides, porque dê uma boa olhada, quebrar cada parte dessa expressão em fatores primos é impossível. Para aplicar o algoritmo de Euclides vamos lembrar do algoritmo da divisão.

$\\\begin{array}{l|l}~~~Dividendo&\underline{ Divisor}\\~~~ Resto&~ Quociente\end{array}\\\\\\ \boxed{Dividendo=Divisor\cdot Quociente + Resto}$

O divisor é o menor número entre a e b enquanto o dividendo é o maior número entre a e b. Sabemos que por definição "n" é um inteiro ($\mathbb{Z}$) então é não há muito o que pensar que é maior que n ou 2n+1, é apenas pura lógica, pois é óbvio que 2n+1 é maior que n. Dividindo 2n+1 por n temos a seguinte expressão:

$\\\begin{array}{l|l}~~~2n+1&\underline{~~~n~~~}\\~~~ &~ \end{array}$

Para o primeiro termo do quociente, faremos a seguinte pergunta: qual o termo que multiplicado por $n$ resulta ou está próximo de $n+1$?$2$ pois $2\cdot n =2n$. Então:

$\\\begin{array}{l|l}~~~\quad2n+1&\underline{~~~n~~~}\\~~~ \underline{-\,2n +0~}&~ { 2}\\~~~ \qquad \quad {1}&\end{array}\\\\\\\begin{array}{l|l}~~~\quad2n+1&\underline{~~~n~~~}\\~~~ \qquad \quad \underbrace{1}_{\text{ Resto}}&~ \underbrace{ 2}_{\text{Quociente}}&\end{array}$

Fazendo essa divisão podemos ver que 2n+1 pode ser escrito como 2n+1 (somente para gênios haha), já que estamos aplicando o método do algoritmo de Euclides vamos trocar 2n+1 pelo resto que sobra quando dividido por n. Observe que seu resto é igual a 1 (um), então é o mesmo que escrever $2n +1=2n +1~~\qquad\iff\qquad~~ 2n+1-2n=1$, então o mdc que devemos agora calcular seria:

$\red{mdc\left(n,~2n+1-2n\right)=mdc\left(n,~1\right)}$

Observe que agora calcular o máximo divisor comum entre n e 1 é muito mais simples, pois 1 não pode ser dividido em fatores primos. Como 1 não pode ser decomposto em fatores primos, o máximo divisor comum entre n e 1 é o próprio 1, pois 1 é divisível por n e 1. Portanto, chegamos à seguinte conclusão:

$\green{\boxed{\displaystyle \sf \boldsymbol{mdc\left(n,~2n+1\right)=1}}}\qquad \texttt{Como~queriamos~demonstrar~(c.q.d)}$

Bons estudos e espero que te ajude :-)

Duvidas? Comente